Skip to content
第3章

3.10 循环队列 ​

数组里的叫号 ​

3.9节只说了队列能做什么,没说怎么存。现在把队列放进内存,先照3.3节的办法,用一段连续的格子来存。

3.3节存栈,只要记一个数top,因为栈只在栈顶这一头进出。队列两头都要动:取号排在队尾,叫号从队头叫。所以要记两个数,一个记队头在哪一格,一个记队尾在哪一格。

这两个数叫队头指针和队尾指针,记作front和rear。它们其实是下标,不是C语言里的指针,教材习惯这么叫。

  • front是队头元素所在的格子;
  • rear是队尾元素的下一格,也就是下一个空格,和3.3节的top一样。

入队,就是把x放进第rear格,rear加1。出队,就是取出第front格,front加1。两个操作都只改一个格子和一个数,谁都不用挪。

开始时队列是空的,front和rear都是0。

用3.9节银行的例子走一遍。数组只画5格,上面的箭头是front,下面的箭头是rear,左边一列记着每一步调用了什么、改了什么:

InitQueue(Q)front = rear = 0
01234frontrear
EnQueue(Q, 1)data[0] = 1rear = 1
101234frontrear
EnQueue(Q, 2)data[1] = 2rear = 2
1021234frontrear
DeQueue(Q, &x)x = data[0] = 1front = 1
1021234frontrear
EnQueue(Q, 3)data[2] = 3rear = 3
10213234frontrear
DeQueue(Q, &x)x = data[1] = 2front = 2
10213234frontrear
DeQueue(Q, &x)x = data[2] = 3front = 3
10213234frontrear

出队之后,格子里的旧号码还在,画成灰色。和3.3节的Pop一样,不用擦,它已经不算在队里了。

三次叫号之后,队列空了。看最后一行:front和rear都是3,不是0。所以判断队空,不能看front是不是0,要看front等于rear:队头追上了下一个空格,中间一个元素也没有。开始时两个都是0,也是front等于rear。

接着往下走。4号、5号、6号先后来取号:

调用前
102132345frontrear
EnQueue(Q, 4)data[3] = 4rear = 4
1021324345frontrear
EnQueue(Q, 5)data[4] = 5rear = 5
10213243545frontrear
EnQueue(Q, 6)没有第5格
10213243545frontrear

5号放进第4格,rear变成5。可是数组只有第0格到第4格,没有第5格,6号放不进去了。

本节问题
数组只有5格,银行一天要取几百个号。怎样用这5格,一直取号、叫号下去?
选中正文里的任意文字,就可以针对它发表评论