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 出队时: IF cq. rear+l-=maxsize THEN cq. rear: =0 cq. front=(cq. front+1)% maxsize ELSE cq. rear: =cq. rear+
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
3.3队列的表示和实现 例. maxsize=6,初始状态和操作过程如下: 将F入队 BA B E/ cq. rear A 此时,队满。有 cq front=cq. rear 连续4次出队 front ca rear ca front front 再出队 E/ cq.rear front 此时,队空.有 .rear cq.front=cq. rear
此时, 队空. 有 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.front cq.rear 再出队
3.3队列的表示和实现 队满和队空时,均有 cq. front=cq, rear 因此,只凭 cq. front=cq,rear还无法区分是满还是空 如何判定队满还是空?是循环队列要解决的新问题。 方法一:用一个计数变量来记载队列中的元素个数。 初始化队列时c:=0; 当入队时,计数变量+1(c:=c+1) 当出队时,计数变量-1(c:=c-1) 当计数变量= maxse时,队满 当计数变量=0时,队空
队满和队空时，均有cq.front=cq.rear。 因此，只凭cq.front=cq.rear还无法区分是满还是空。 如何判定队满还是空？是循环队列要解决的新问题。 3.3 队列的表示和实现 方法一 ：用一个计数变量来记载队列中的元素个数。 • 初始化队列时c:=0; • 当入队时，计数变量＋1（ c:=c+1 ） • 当出队时，计数变量－1 （c:=c-1） • 当计数变量＝maxsize时，队满 • 当计数变量＝0时，队空
3.3队列的表示和实现 方法二:设一个标志位用来区别队列是空还是满。 初始化队列时: cq. front== cq.rear,标志位为fale 入队后,使cq, front=cq,rear,则置标志位为true 出队后,将标志位置为 false 当 cq. front== cq.rear,且标志位为true时,队满。 当cq, front= cq. rear,但标志位为 false时,队空。 其他为非空非满
方法二：设一个标志位用来区别队列是空还是满。 • 初始化队列时：cq.front==cq.rear，标志位为false • 入队后，使cq.front==cq.rear，则置标志位为true • 出队后，将标志位置为false • 当cq.front==cq.rear, 且标志位为true时，队满。 • 当cq.front==cq.rear, 但标志位为false时，队空。 • 其他为非空非满。 3.3 队列的表示和实现
3.3队列的表示和实现 方法三:牺牲一个元素空间,来区别队空或队满。 入队前,先判( cg. rear+1)% maxsize是否等于 cq. front,若是则为队满。 °而当 cq. front== cq. rear时,为队空 前例:当E入队后,就认为队已满, 而当F再要入队时,就拒绝入队
方法三：牺牲一个元素空间，来区别队空或队满。 • 入队前，先判(cq.rear+1)% maxsize是否等于 cq.front，若是则为队满。 • 而当cq.front==cq.rear时，为队空。 前例：当E入队后，就认为队已满， 而当F再要入队时，就拒绝入队。 3.3 队列的表示和实现
3.3队列的表示和实现 方法四:扩大rear和 front的定义域为0.. maXslzeo 初值rear=0; front= maXsize 入队前,先判rear是否= maxsize,是则为对满。 当入队后,使得 cg. 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
方法四：扩大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 队列的表示和实现