西南科技大学：《数据结构》课程教学资源（PPT课件讲稿）队列的表示和实现

队列的表示和实现 循环队列结构 把队列视为一个循环表,即cqe1em[ maxsize-1]之后是数组 的第一个元素cqe1em[0] 可采用mod运算(取余数)来实行循环队列的运算 入队时: cq. rear=(cq. rear+1)% maxsize 出队时: cq. front=(cq. front+1) o maxsize

队列的表示和实现 循环队列结构 把队列视为一个循环表，即cq.elem[maxsize-1]之后是数组 的第一个元素cq.elem[0] 。 可采用mod运算（取余数）来实行循环队列的运算: 入队时： cq.rear =(cq.rear+1)% maxsize； 出队时： cq.front =(cq.front+1) % maxsize

队列的表示和实现 例. 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,初始状态和操作过程如下: 队列的表示和实现 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 再出队

队列的表示和实现 队满和队空时,均有 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还无法区分是满还是空。 如何判定队满还是空？是循环队列要解决的新问题。 队列的表示和实现 方法一 ：用一个计数变量来记载队列中的元素个数。 • 初始化队列时c:=0; • 当入队时，计数变量＋1（ c:=c+1 ） • 当出队时，计数变量－1 （c:=c-1） • 当计数变量＝maxsize时，队满 • 当计数变量＝0时，队空

队列的表示和实现 方法二:设一个标志位用来区别队列是空还是满。 初始化队列时: 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时，队空。 • 其他为非空非满。 队列的表示和实现

队列的表示和实现 方法三:牺牲一个元素空间,来区别队空或队满。 入队前,先判( cg. rear+1)% maxsize是否等于 cq. front,若是则为队满。 °而当 cq. front== cq. rear时,为队空 前例:当E入队后,就认为队已满, 而当F再要入队时,就拒绝入队

方法三：牺牲一个元素空间，来区别队空或队满。 • 入队前，先判(cq.rear+1)% maxsize是否等于 cq.front，若是则为队满。 • 而当cq.front==cq.rear时，为队空。 前例：当E入队后，就认为队已满， 而当F再要入队时，就拒绝入队。 队列的表示和实现

队列的表示和实现 方法四:扩大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 队列的表示和实现