论坛 › 数据结构与算法 › 数据结构30讲循环队列实现的另一种方法（以标志域tag的0与1判断队列是空还是满）

圣狄雅哥 发表于 2018-2-8 21:06:56

数据结构30讲循环队列实现的另一种方法（以标志域tag的0与1判断队列是空还是满）

本帖最后由 圣狄雅哥 于 2018-2-8 21:13 编辑

#define MaxQsize 10
typedef int Status
typedef int ElemType;
typedef struct{
       ElemType *base;
       int front;
       int rear;
       Status tag;
}Queue;

Status InitQueue(Queue*q)
{
    q->base=(ElemType*)malloc(MaxQsize*sizeof(ElemType));
    if(!q->base)   return FALSE;
    q->front=q->rear=0;
    q->tag=0;
    return OK;
}

Status EnQueue(Queue *q,ElemType e)
{
    if(q->front==q->rear&&q->tag)    return FALSE;
    else{
            q->base=e;
            q->rear=(q->rear+1)%MaxQsize;
            if(q->rear==q->front)
                  q->tag=1;
          }
   return OK;
}

Status DeQueue(Queue *q,ElemType *e)
{
    if(q->front==q->rear&&!q-.tag)    return FALSE;
    else{
            *e=q->base;
            q->front=(q->front+1)%MaxQsize;
            if(q->front==q->rear)
                  q->tag=0;
          }
          return OK;
}

圣狄雅哥 发表于 2018-2-8 21:09:14

小甲鱼视频教程里面的那个队列“满”时其实还有一个存储空间没有利用，这段代码通过引入tag标志来节省存储空间，但运行时间稍微加长了。

查看完整版本: 数据结构30讲循环队列实现的另一种方法（以标志域tag的0与1判断队列是空还是满）