3.3 队列的表示和实现
2,循环队列结构把队列视为一个循环表，即 cq.elem[maxsize-1]之后是数组的第一个元素 cq.elem[0] 。
#define maxsize 队列的最大容量；
Typedef struct cyclicquetp {
datatype elem[maxsize];
int rear,front;
}
可采用 mod运算 （ 取余数 ） 来实行循环队列的运算,
入队时,cq.rear =(cq.rear+1)% maxsize；
cq.elem[cq.rear] =x；
出队时：
cq.front =(cq.front+1) % maxsize
IF cq.rear+1=maxsize
THEN cq.rear,=0
ELSE cq.rear,=cq.rear+1
此时,队空,有
cq.front=cq.rear
此时,队满,有
cq.front=cq.rear
例,maxsize=6,初始状态和操作过程如下,
3.3 队列的表示和实现
A
B
C
E
D
cq.front
cq.rear A
B
C
E
D
cq.front
cq.rear
F
将 F入队
E
cq.front
cq.rear
连续 4次出队
cq.frontcq.rear
再出队队满和队空时，均有 cq.front=cq.rear。
因此，只凭 cq.front=cq.rear还无法区分是满还是空。
如何判定队满还是空？是循环队列要解决的新问题。
3.3 队列的表示和实现方法一,用一个计数变量来记载队列中的元素个数。
初始化队列时 c:=0;
当入队时，计数变量＋ 1（ c:=c+1 ）
当出队时，计数变量－ 1 （ c:=c-1）
当计数变量＝ maxsize时，队满
当计数变量＝ 0时，队空方法二,设一个标志位用来区别队列是空还是满。
初始化队列时,cq.front==cq.rear,标志位为 false
入队后，使 cq.front==cq.rear,则置标志位为 true
出队后，将标志位置为 false
当 cq.front==cq.rear,且标志位为 true时,队满 。
当 cq.front==cq.rear,但标志位为 false时,队空 。
其他为非空非满。
3.3 队列的表示和实现方法三,牺牲一个元素空间，来区别队空或队满。
入队前，先判 (cq.rear+1)% maxsize是否等于
cq.front，若是则为队满。
而当 cq.front==cq.rear时，为队空。
前例：当 E入队后,就认为队已满,
而当 F再要入队时,就拒绝入队 。
3.3 队列的表示和实现方法四,扩大 rear和 front的 定义域为 0..maxsize。
初值 rear=0； front=maxsize
入队前，先判 rear是否 =maxsize,是则为对满。
当入队后,使得 cq.rear=cq.front，
则令 cq.rear=maxsize,表示队满。
若 cq.front=maxsize,则 cq.front:=cq.rear-1
出队前，先判 front是否 =maxsize,是则为队空。
当出队后,使得 cq.front=cq.rear,
则令 cq.front:=maxsize,表示队空 。
若 cq.rear=maxsize,则 cq.rear:=cq.front-1
3.3 队列的表示和实现