队列的表示和实现循环队列结构把队列视为一个循环表,即 cq.elem[maxsize-1]之后是数组的第一个元素 cq.elem[0] 。
可采用 mod运算 ( 取余数 ) 来实行循环队列的运算,
入队时:
cq.rear =(cq.rear+1)% maxsize;
出队时:
cq.front =(cq.front+1) % maxsize
此时,队空,有
cq.front=cq.rear
此时,队满,有
cq.front=cq.rear
例,maxsize=6,初始状态和操作过程如下,
队列的表示和实现
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还无法区分是满还是空。
如何判定队满还是空?是循环队列要解决的新问题。
队列的表示和实现方法一,用一个计数变量来记载队列中的元素个数。
初始化队列时 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时,队空 。
其他为非空非满。
队列的表示和实现方法三,牺牲一个元素空间,来区别队空或队满。
入队前,先判 (cq.rear+1)% maxsize是否等于
cq.front,若是则为队满。
而当 cq.front==cq.rear时,为队空。
前例:当 E入队后,就认为队已满,
而当 F再要入队时,就拒绝入队 。
队列的表示和实现方法四,扩大 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
队列的表示和实现