外观
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,左边一列记着每一步调用了什么、改了什么:
出队之后,格子里的旧号码还在,画成灰色。和3.3节的Pop一样,不用擦,它已经不算在队里了。
三次叫号之后,队列空了。看最后一行:front和rear都是3,不是0。所以判断队空,不能看front是不是0,要看front等于rear:队头追上了下一个空格,中间一个元素也没有。开始时两个都是0,也是front等于rear。
接着往下走。4号、5号、6号先后来取号:
5号放进第4格,rear变成5。可是数组只有第0格到第4格,没有第5格,6号放不进去了。
本节问题数组只有5格,银行一天要取几百个号。怎样用这5格,一直取号、叫号下去?
假溢出
再看上一页最后一张图的第0、1、2格:都是灰的,空着。队里只有4、5两个号码,5个格子却放不下第3个。
这种情况叫假溢出:数组里明明还有空格,队列却放不进了。它和栈满不一样,栈满是格子真的用完了。
毛病出在front和rear只往右走,从不回头。把能想到的出路逐条看一遍。
把元素挪回开头。把4、5挪到第0、1格,rear就回到2,又能接着放了。干脆每次出队都把后面的元素往前挪一格,让队头一直待在第0格,就永远不会走到头。
text
0 1 2 3 4
┌───┬───┬───┬───┬───┐
出队前 │ 1 │ 2 │ 3 │ │ │
├───┼───┼───┼───┼───┤
出队后 │ 2 │ 3 │ │ │ │
└───┴───┴───┴───┴───┘可是挪一次就要搬动队里的n个元素,出队变成了O(n)。这正是2.7节的结论:在顺序表的开头删除,要挪n个。front往后走,本来就是为了一个都不挪,挪回去等于前功尽弃。
把数组开大一些。这只是晚一点到头。rear只往右走,银行一天要取几百个号,开多大都会走到末尾。
rear走到末尾后,回到第0格接着放。第0格早就空出来了,6号可以放进去,谁都不用挪。
前两条都不行,只剩第三条。rear怎么回到第0格?
首尾接起来
回到5号取号那一步,重新做。5号放进第4格以后,rear不再变成5,而是回到0:
6号放进了第0格。现在队头4号在第3格,队尾6号在第0格。从front开始往后数,数到末尾,再从第0格接着数,就是4、5、6。
这就好比把数组的末尾和开头接起来,围成一圈,第4格的下一格就是第0格:
这样用的数组,叫循环队列。
rear加1,到了5就回到0。写成C,用的是取余:
c
Q->rear = (Q->rear + 1) % MAXSIZE;MAXSIZE是5。rear是0到3时,rear加1不到5,除以5的余数就是它自己。rear是4时,4加1等于5,除以5余0,正好回到第0格。
front也一样。出队时front走到末尾,也要回到第0格。接着叫两次号:
第二次叫号叫到5号,它在第4格,front加1回到了0。现在队里只剩6号,它在第0格,front正好指着它。
满和空分不清
接着往下走。7号、8号、9号、10号先后来取号:
10号放进第4格,rear回到0。5个格子全满了,front和rear都是0。
可是开门时队列是空的,front和rear也都是0。把两张图放在一起:
只看front和rear,分不出队列是空的还是满的。QueueEmpty会把满的队列当成空的,EnQueue也不知道还能不能放。
为什么会撞在一起?5个格子,队里的元素可以有0个到5个,一共6种情况。可rear比front多走几格,绕着圈算只有0到4这5种。6种情况挤进5种样子,总有两种撞在一起,撞的正好是空和满。
办法是空一格不用:队里最多放MAXSIZE−1个元素。rear的下一格就是front时,就算满了,不再往里放。
重做9号、10号取号:
9号放进第3格,rear变成4。这时rear的下一格是第0格,正是front,所以队满,10号放不进。第4格空着不用。
满的条件写成C:
c
(Q->rear + 1) % MAXSIZE == Q->front空的条件不变,还是front等于rear。满的时候,rear和front之间总隔着一个空格,两种样子就分开了。
代价是少用一个格子:MAXSIZE是5,最多放4个。
另外两种办法
不想空着一格,也可以在结构体里多记一个数。一种是记队里有几个元素:空是个数为0,满是个数等于MAXSIZE。另一种是记最近一次做的是入队还是出队:front等于rear时,刚入过队就是满,刚出过队就是空。本书用空一格的办法,和大多数教材一样。
队里有几个元素
队里的元素个数是(rear − front + MAXSIZE) % MAXSIZE。比如上一页6号刚入队时,front是3,rear是1,算出来是(1 − 3 + 5) % 5,等于3,正好是4、5、6三个。rear绕回来以后会比front小,加上MAXSIZE再取余,就不会算出负数。
用C语言表示循环队列
循环队列是一段连续的格子,再加front和rear两个数:
c
#define MAXSIZE 5
typedef struct {
int data[MAXSIZE]; /* 存放元素的连续空间 */
int front; /* 队头元素所在的格子 */
int rear; /* 队尾的下一个空格 */
} SqQueue;MAXSIZE取5,是为了和前面的图一样,程序跑起来看得见绕回。真用的时候可以开大一些。元素是整数,因为要放的是号码。
初始化就是让front和rear都为0。判空就是看front是不是等于rear:
c
void InitQueue(SqQueue *Q) {
Q->front = Q->rear = 0;
}
int QueueEmpty(SqQueue *Q) {
return Q->front == Q->rear;
}EnQueue:放到队尾
拿5号取号那一步来看。队里只有4号,front是3,rear是4。现在EnQueue(Q, 5)。
第一步:判断队满。rear的下一格是(4 + 1) % 5,等于0,不是front的3,放得下。
第二步:5放进第rear格,也就是第4格:
c
Q->data[Q->rear] = 5; /* data[4] = 5 */第三步:rear往后走一格。4加1到了末尾,回到0:
c
Q->rear = (Q->rear + 1) % MAXSIZE; /* rear = 0 */写成函数。和3.3节的Push一样是三步,只有两处变化:满的条件换成空一格的写法;rear往后走要能绕回,用取余。放不下返回0,放好了返回1:
c
int EnQueue(SqQueue *Q, int x) {
if ((Q->rear + 1) % MAXSIZE == Q->front) return 0; /* 第一步:队满,放不进 */
Q->data[Q->rear] = x; /* 第二步:x放进第rear格 */
Q->rear = (Q->rear + 1) % MAXSIZE; /* 第三步:rear往后走一格 */
return 1;
}DeQueue:删除队头,用x带回
拿第一次叫4号来看。队里是4、5、6,front是3,rear是1。现在DeQueue(Q, &x)。
第一步:判断队空。front是3,rear是1,不相等,有东西可删。
第二步:用x带回第front格,也就是第3格里的4:
c
*x = Q->data[Q->front]; /* x = data[3],也就是4 */第三步:front往后走一格:
c
Q->front = (Q->front + 1) % MAXSIZE; /* front = 4 */先取,再走,顺序不能反。front指着的就是队头元素本身,要先把它取出来,再往后走。要是先走,front就到了第4格,取到的是5,4号就被跳过去了。
3.3节的Pop正好相反,先减再取。因为top指着的是空格,栈顶在它下面一格。
写成函数。队空返回0,删好了返回1:
c
int DeQueue(SqQueue *Q, int *x) {
if (Q->front == Q->rear) return 0; /* 第一步:队空,没有可删的 */
*x = Q->data[Q->front]; /* 第二步:用x带回第front格 */
Q->front = (Q->front + 1) % MAXSIZE; /* 第三步:front往后走一格 */
return 1;
}GetHead和DeQueue只差一点:只看,不删,所以front不动。队头元素就在第front格:
c
int GetHead(SqQueue *Q, int *x) {
if (Q->front == Q->rear) return 0; /* 队空,没有队头 */
*x = Q->data[Q->front]; /* 队头就在第front格 */
return 1;
}五个操作都只碰一个格子和一两个数,一个元素都不挪,时间复杂度都是O(1)。开头的问题解决了:5个格子绕着圈用,front和rear走到末尾就回到第0格,取号、叫号可以一直进行下去,只要同时在等的不超过4个人。
换来这一点,付出的是一个格子。还有一点和顺序栈一样:格子数事先定好,真放满了就放不进。
把五个操作合起来
再写一个main。前半段就是3.9节的例题;后半段接着让4号到9号连着取号,rear会绕回第0格,放满以后再取号就放不进了。最后把队里的号码全部叫完:
c
int main(void) {
SqQueue Q;
int x, i;
InitQueue(&Q);
EnQueue(&Q, 1);
EnQueue(&Q, 2);
DeQueue(&Q, &x); printf("%d ", x);
EnQueue(&Q, 3);
DeQueue(&Q, &x); printf("%d ", x);
DeQueue(&Q, &x); printf("%d\n", x);
for (i = 4; i <= 9; i++)
if (!EnQueue(&Q, i)) printf("%d号放不进,队满\n", i);
while (!QueueEmpty(&Q)) {
DeQueue(&Q, &x); printf("%d ", x);
}
printf("\n");
return 0;
}把这个main接在前面五个函数后面,再在开头加上#include <stdio.h>,就是完整的程序。运行结果:
text
1 2 3
8号放不进,队满
9号放不进,队满
4 5 6 7三次叫号之后,front和rear都是3。4号到7号依次放进第3、4、0、1格,rear绕回来走到2。这时rear的下一格是front,满了,8号、9号都放不进。最大能放4个,正好是MAXSIZE−1。
main从头到尾只调用了五个操作,没有碰过data、front和rear。
完整的程序放在下面,可以直接复制运行:
c
#include <stdio.h>
#define MAXSIZE 5
typedef struct {
int data[MAXSIZE];
int front;
int rear;
} SqQueue;
void InitQueue(SqQueue *Q) {
Q->front = Q->rear = 0;
}
int QueueEmpty(SqQueue *Q) {
return Q->front == Q->rear;
}
int EnQueue(SqQueue *Q, int x) {
if ((Q->rear + 1) % MAXSIZE == Q->front) return 0; /* 第一步:队满,放不进 */
Q->data[Q->rear] = x; /* 第二步:x放进第rear格 */
Q->rear = (Q->rear + 1) % MAXSIZE; /* 第三步:rear往后走一格 */
return 1;
}
int DeQueue(SqQueue *Q, int *x) {
if (Q->front == Q->rear) return 0; /* 第一步:队空,没有可删的 */
*x = Q->data[Q->front]; /* 第二步:用x带回第front格 */
Q->front = (Q->front + 1) % MAXSIZE; /* 第三步:front往后走一格 */
return 1;
}
int GetHead(SqQueue *Q, int *x) {
if (Q->front == Q->rear) return 0; /* 队空,没有队头 */
*x = Q->data[Q->front]; /* 队头就在第front格 */
return 1;
}
int main(void) {
SqQueue Q;
int x, i;
InitQueue(&Q);
EnQueue(&Q, 1);
EnQueue(&Q, 2);
DeQueue(&Q, &x); printf("%d ", x);
EnQueue(&Q, 3);
DeQueue(&Q, &x); printf("%d ", x);
DeQueue(&Q, &x); printf("%d\n", x);
for (i = 4; i <= 9; i++)
if (!EnQueue(&Q, i)) printf("%d号放不进,队满\n", i);
while (!QueueEmpty(&Q)) {
DeQueue(&Q, &x); printf("%d ", x);
}
printf("\n");
return 0;
}练习1:front和rear是几?
填空
循环队列,MAXSIZE是5,空一格不用。从空队列开始,依次调用:
EnQueue(&Q, 1),EnQueue(&Q, 2),EnQueue(&Q, 3),EnQueue(&Q, 4),DeQueue(&Q, &x),DeQueue(&Q, &x),DeQueue(&Q, &x),EnQueue(&Q, 5),EnQueue(&Q, 6)
- 全部做完,front是
- rear是
- data[0]里是
- 队头元素是
四次入队之后,1到4在第0到第3格,front是0,rear是4,已经满了。三次出队,front走到3,队里只剩4。5放进第4格,rear绕回0;6放进第0格,rear变成1。这时队里是4、5、6,队头4在第3格。
练习2:判满写成front等于rear会怎样?
单选
有人图省事,把EnQueue里判满的那一行写成了:
c
if (Q->front == Q->rear) return 0;从空队列开始,调用EnQueue(&Q, 1),会怎样?
A
和原来一样,1放进第0格,rear变成1
空队列时front和rear都是0,条件成立,函数在第一行就返回了。
B
返回0,1放不进去,以后也一个都放不进
front等于rear本来是队空的条件。空队列一开始就满足它,EnQueue把空当成了满。
C
能放满5个格子,比空一格多放一个
第一个都放不进,更放不满。
满和空必须用两个不同的条件。空一格不用,就是为了让满的样子和空的样子不一样。
到这里你有了循环队列:一段连续的格子加front和rear,front指着队头元素,rear指着下一个空格,走到末尾用取余回到第0格。空是front等于rear,满是rear的下一格是front,空一格不用。五个操作都是O(1)。下一步用链表存队列。