队列的存储和循环队列

一、队列的存储结构

1、队列的物理存储可以用顺序存储结构，也可用链式存储结构。相应队列的存储方式也分为两种，即顺序队列和链式队列。

2、顺序队列可以用一维数组表示如下：

#define MAXQSIZE 100 //最大队列长度

Typedef struct {

QElemType *base; //初始化的动态分配存储空间

int front; //头指针

int rear； //尾指针

}SqQueue;

二、循环队列的基本操作语句

1、队列的初始：front=rear=0;

2、元素入队：base[rear]=x; rear++;

3、元素出队：x=base[front];front++;

4、空队标志：front==rear;

5、队满标志：为了防止队满标志和队空标志一样，则会少用一个元素空间，即队列空间大小为m时，有m-1个元素就认为是队满。这样判断队空的条件不变，即当头、尾指针的值相同时，则认为队空;而当尾指针在循环意义上加1后是等于头指针，则认为队满。因此，在循环队列中队满的条件是:(rear+1)%MAXQSIZE==front。

三、顺序队列的假上溢

1、定义：系统作为队列用的数组存储区还没有满,但队列却发生了溢出,我们把这种现象称为"假溢出"。

2、原因：由于元素入队时头指针前移和元素出队时尾指针也是前移，当头指针超出向量空间，这时整个向量空间及队列并没有满却产生了"上溢"现象。

3、解决方法：将队空间设想成一个循环的表，即分配给队列的m个存储单元可以循环使用，当rear为maxqsize时， 若向量的开始端空着，又可从头使用空着的空间。当front为maxqsize时 ,也是一样。

四、循环对列

1、循环队列的存储方式：base[0]接在base[MAXQSIZE -1]之后，若rear+1==M, 则令rear=0;

2、循环队列插入元素和删除

①插入元素: Q.base[Q.rear]=x;

                Q.rear= (Q.rear+ 1)% MAXQSIZE;

②删除元素: x= Q.base[s.front]

                Q.front=(Q.front+ 1)% MAXQSIZE