小菜一步一步学数据结构之(六)队列

队列是一种先进先出的线性表,它只允许在表的一段进行插入，而在另外一端删除元素。

队列的顺序表示—用一维数组base[M]

       #define M 100//最大队列长度
       Typedef struct{
        QElemType *base;
        int front;
        int rear;
        }SqQueue;

空队标志:front==rear
入队:base[rear++]=x;
出队:x=base[front++];

但是这样做存在一个问题，如下：

front=0 front≠0
rear=M时 rear=M时
再入队—真溢出 再入队—假溢出
该怎样解决呢？
—-循环队列

          base[0]接在base[M-1]之后
          若rear+1==M
          则令rear=0;
          实现:利用“模”运算
          入队:
          base[rear]=x;
          rear=(rear+1)%M;
          出队:
          x=base[front];
          front=(front+1)%M;

又出现另外一个问题

解决方案:
1.另外设一个标志以区别队空、队满
2.少用一个元素空间:
队空:front==rear
队满:(rear+1)%M==front

循环队列

#define MAXQSIZE 100
Typedef struct{
 QElemType *base;//初始化的动态分配存储空间
 int front;//头指针
 int rear;//尾指针
}SqQueue;

循环队列初始化

Status InitQueue(SqQueue &Q)
{
 Q.base=new QElemType[MAXQSIZE]
  if(!Q.base)exit(OVERFLOW);
  Q.front=Q.rear=0;
  return OK;
}

循环队列的长度

int QueueLength(SqQueue Q){
 return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}

循环队列入队

Status EnQueue(SqQueue &Q,QElemType e){
 if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR;
 Q.base[Q.rear]=e;
 Q.rear=(Q.rear+1)%MAXQSIZE;
 return OK;
}

顺环队列出队

Status DeQueue(LinkQueue &Q,QElemType &e)
{
   if(Q.front==Q.rear)
   return ERROR;
   e=Q.base[Q.front];
   Q.front=(Q.front+1)%MAXQSIZE;
   return OK;
}