外观
3.11 链队
队头放在哪一头
3.10节的循环队列,格子数要事先定好,最多只能放MAXSIZE−1个。银行不知道一天会来多少人,格子定少了不够,定多了浪费。
3.4节用链表存栈,要多少结点就申请多少。队列也可以这样存:每个元素一个结点,用地址连起来。
和链栈一样,先要定队头放在哪一头。还是存1、2、3,1号在队头,有两种放法。
放法一:第一个结点是队头。
text
L = 100
│
▼
┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐
│ 1 │ 109 │────►│ 2 │ 105 │────►│ 3 │ 0 │
└───┴─────┘ └───┴─────┘ └───┴─────┘
100 109 105出队删的是第一个结点:把L改成1结点地址格里的109,一步就到。入队就麻烦了:4号要接在3结点后面,可3结点在哪?链表只记着第一个结点的地址,只能从L出发一个一个走过去。队里有n个元素,就要走n−1步。
放法二:第一个结点是队尾。
text
L = 105
│
▼
┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐
│ 3 │ 109 │────►│ 2 │ 100 │────►│ 1 │ 0 │
└───┴─────┘ └───┴─────┘ └───┴─────┘
105 109 100入队插在最前面,一步都不用走。出队要删1结点,就得把2结点的地址格改成0,又得从L走过去找2结点。
链栈的进和出在同一头,放在表头就都是一步。队列的进和出分在两头,不管怎么放,总有一个操作要从头走一遍。
本节问题用链表存队列,能不能让入队、出队都不用从头走?
记住队尾
看放法一。出队已经是一步了,毛病只在入队:要接在最后一个结点后面,可链表只记着第一个结点,只好从头找。
那就多记一个:最后一个结点的地址。
text
front = 100 rear = 105
│ │
▼ ▼
┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐
│ 1 │ 109 │────►│ 2 │ 105 │────►│ 3 │ 0 │
└───┴─────┘ └───┴─────┘ └───┴─────┘
100 109 105入队时,新结点直接接在rear指着的结点后面,再让rear改指新结点。这就是2.16节的按结点操作:给了一个结点,在它后面插入,一步都不用走,是O(1)。
放法二也多记一个最后的结点,行不行?不行。放法二出队删的就是最后一个结点,要改的却是它前一个结点的地址格。单链表只能往后走,从最后一个结点退不回前一个,还得从头找。2.16节说过,单链表上只有找前一个结点是O(n)。
所以链表存队列,用放法一,再多记一个队尾。
用链式存储的队列叫链队。记着队头的叫队头指针,记作front;记着队尾的叫队尾指针,记作rear。3.10节的front和rear是下标,这里是真正的C语言指针。
结点和3.4节的一样,只是换了名字。链栈只要一个S,链队要两个指针,就把它们放进一个结构体:
c
typedef struct QNode {
int data; /* 数据格 */
struct QNode *next; /* 地址格:后面一个结点的地址 */
} QNode;
typedef struct {
QNode *front; /* 队头指针 */
QNode *rear; /* 队尾指针 */
} LinkQueue;LinkQueue和3.10节的SqQueue一样,是一个结构体。操作的参数也一样用LinkQueue *Q,用Q->front、Q->rear取到两个指针。
要不要头结点
先像链栈那样,不要头结点。空队列一个结点都没有,front和rear都是NULL:
现在1号取号。新结点要接在rear指着的结点后面,可rear是NULL,没有结点可接。只能另写一种情形:队空时,让front和rear都指向新结点。
出队也一样。删掉最后一个元素,front变成NULL,rear也得跟着改成NULL。入队、出队,都要多分一种情形。
2.14节遇到过同样的事:第0个结点前面没有结点,插入、删除要分情形。办法是加一个头结点。链队也加:
左边是空队列:只有一个头结点,地址格是0,front和rear都指着它。右边放了1、2、3:front还指着头结点,队头元素是头结点后面那个;rear指着队尾3结点。头结点的数据格不用,画成灰色。
空队列时rear指着头结点,1号入队就是接在头结点后面,和接在3结点后面是同一件事,不用再分情形。
链栈为什么不加?链栈只在第0个结点进出,从来不用找前一个结点(3.4节)。链队入队要接在rear指着的结点后面,rear得一直指着一个结点,队空的时候也一样,头结点给了它一个去处。
由此马上得到两个操作。初始化就是申请一个头结点,让front和rear都指向它。判空就是看front和rear是不是指着同一个结点:
c
int InitQueue(LinkQueue *Q) {
Q->front = Q->rear = (QNode *)malloc(sizeof(QNode)); /* 头结点 */
if (Q->front == NULL) return 0;
Q->front->next = NULL;
return 1;
}
int QueueEmpty(LinkQueue *Q) {
return Q->front == Q->rear;
}判空的条件还是front等于rear,和3.10节一样,意思却不同:这里是两个指针指着同一个结点,也就是只剩头结点。
链队没有"队满":只要还申请得到结点,就能入队。
不带头结点的链队
王道等教材也讲不带头结点的写法。初始化时front和rear都是NULL,判空看front是不是NULL。入队要分两种情形:队空时,front和rear都指向新结点;不空时接在rear后面。出队删到最后一个时,front和rear都要改回NULL。
EnQueue:放到队尾
队里是1、2,rear指着2结点。现在EnQueue(Q, 3)。
第一步:申请结点q,放3。它将是最后一个结点,地址格填NULL。假设申请到的是112号:
c
QNode *q = (QNode *)malloc(sizeof(QNode));
q->data = 3;
q->next = NULL;第二步:接在队尾后面。rear指着的2结点,地址格改成q的地址:
c
Q->rear->next = q; /* 2结点的地址格 = 112 */第三步:rear指向q。3结点成了新的队尾:
c
Q->rear = q; /* rear = 112 */先接上,再移rear,顺序不能反。先移rear,rear就指着q了。接下来的Q->rear->next = q写进的是q自己的地址格,q指向了自己;2结点的地址格还是0,3结点根本没接上。
写成函数。申请不到结点返回0,放好了返回1:
c
int EnQueue(LinkQueue *Q, int x) {
QNode *q = (QNode *)malloc(sizeof(QNode)); /* 第一步:申请结点放x */
if (q == NULL) return 0;
q->data = x;
q->next = NULL;
Q->rear->next = q; /* 第二步:接在队尾后面 */
Q->rear = q; /* 第三步:rear指向新结点 */
return 1;
}前两步就是2.16节的InsertAfter:在rear指着的结点后面插入。队空时rear指着头结点,新结点照样接在头结点后面,不用另写。
DeQueue:删除队头,用x带回
队里是1、2、3。现在DeQueue(Q, &x)。
第一步:判断队空。front和rear指着不同的结点,有东西可删。
第二步:p记下队头结点,用x带回它的值。队头是头结点后面那个:
c
QNode *p = Q->front->next; /* p = 109 */
*x = p->data; /* x = 1 */第三步:把p从链上摘下来。p的地址格是105,抄给头结点,2结点成了队头:
c
Q->front->next = p->next; /* 头结点的地址格 = 105 */第四步:删的是最后一个吗。rear指着3结点,不是p,rear不用动。下面专门看是的时候。
第五步:释放p。1结点已经不在队里了,还给系统:
c
free(p);只剩一个元素的时候。队里只有1,它既是队头,也是队尾,rear也指着它。照第二、三、五步做:
头结点的地址格成了0,队列已经空了。可rear还指着刚释放的那个结点,front不等于rear,QueueEmpty会说不空。下一次入队,Q->rear->next = q会写进一块已经不归你的内存,新结点也接不到头结点后面。
所以要有第四步:删的正是rear指着的结点,就让rear退回头结点:
c
if (Q->rear == p) Q->rear = Q->front;这一步是链队多出来的。rear是链队自己多记的指针,删到它头上,就得把它也改好。入队、出队里,只有这一处要看情形。
写成函数。队空返回0,删好了返回1:
c
int DeQueue(LinkQueue *Q, int *x) {
if (Q->front == Q->rear) return 0; /* 第一步:队空,没有可删的 */
QNode *p = Q->front->next; /* 第二步:p记下队头结点,用x带回它的值 */
*x = p->data;
Q->front->next = p->next; /* 第三步:把p从链上摘下来 */
if (Q->rear == p) Q->rear = Q->front; /* 第四步:删的是最后一个,rear退回头结点 */
free(p); /* 第五步:还给系统 */
return 1;
}第二、三步就是2.16节的DeleteAfter:删头结点后面那个结点。
GetHead只读队头,不摘也不释放:
c
int GetHead(LinkQueue *Q, int *x) {
if (Q->front == Q->rear) return 0; /* 队空,没有队头 */
*x = Q->front->next->data; /* 队头是头结点后面那个 */
return 1;
}五个操作都不用走,都是O(1)。开头的问题解决了:入队靠rear,出队靠头结点,谁都不用从头走。
把五个操作合起来
五个函数都写好了,还要写main。先预测一下:3.10节的main要改多少?
3.10节的main只调用了五个操作,没有碰过data、front和rear。链队的五个操作,名字和用法都和循环队列一样。所以预测:main只改一处,把SqQueue换成LinkQueue。
c
int main(void) {
LinkQueue Q; /* 原来是 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>和#include <stdlib.h>,运行结果:
text
1 2 3
4 5 6 7 8 9main确实只改了一处,可结果和3.10节有一处不同:8号、9号放进去了,也没有打印"放不进"。循环队列只有5格,最多放4个;链队每来一个号就申请一个结点,没有队满。EnQueue只有在申请不到内存时才返回0。
前三次叫号,1、2、3都对,这正是只依赖"能做什么"的好处。换掉的是存法,变的只有存法本身的限制。
两种队列的五个操作都是O(1)。循环队列要事先定好MAXSIZE,还要空一格;链队要多少申请多少,但每个元素多占一个地址格,每次入队、出队都要申请、释放一次结点。
完整的程序放在下面,可以直接复制运行:
c
#include <stdio.h>
#include <stdlib.h>
typedef struct QNode {
int data;
struct QNode *next;
} QNode;
typedef struct {
QNode *front;
QNode *rear;
} LinkQueue;
int InitQueue(LinkQueue *Q) {
Q->front = Q->rear = (QNode *)malloc(sizeof(QNode)); /* 头结点 */
if (Q->front == NULL) return 0;
Q->front->next = NULL;
return 1;
}
int QueueEmpty(LinkQueue *Q) {
return Q->front == Q->rear;
}
int EnQueue(LinkQueue *Q, int x) {
QNode *q = (QNode *)malloc(sizeof(QNode)); /* 第一步:申请结点放x */
if (q == NULL) return 0;
q->data = x;
q->next = NULL;
Q->rear->next = q; /* 第二步:接在队尾后面 */
Q->rear = q; /* 第三步:rear指向新结点 */
return 1;
}
int DeQueue(LinkQueue *Q, int *x) {
if (Q->front == Q->rear) return 0; /* 第一步:队空,没有可删的 */
QNode *p = Q->front->next; /* 第二步:p记下队头结点,用x带回它的值 */
*x = p->data;
Q->front->next = p->next; /* 第三步:把p从链上摘下来 */
if (Q->rear == p) Q->rear = Q->front; /* 第四步:删的是最后一个,rear退回头结点 */
free(p); /* 第五步:还给系统 */
return 1;
}
int GetHead(LinkQueue *Q, int *x) {
if (Q->front == Q->rear) return 0; /* 队空,没有队头 */
*x = Q->front->next->data; /* 队头是头结点后面那个 */
return 1;
}
int main(void) {
LinkQueue 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和地址格里是什么?
填空
有头结点的链队,头结点的地址是100。从空队列开始,依次调用:
EnQueue(&Q, 5),EnQueue(&Q, 8),DeQueue(&Q, &x),EnQueue(&Q, 6)
5结点的地址是109,8结点是105,6结点是112。
- 全部做完,front是
- rear是
- 头结点的地址格是
- x是
front一直指着头结点,是100。5、8入队后,链是头结点 → 5 → 8。DeQueue删的是头结点后面的5,x是5,头结点的地址格改成8结点的105。6入队接在8后面,rear改成6结点的112。
练习2:DeQueue漏了第四步会怎样?
单选
有人写DeQueue时漏了第四步,没有让rear退回头结点。从空队列开始,依次调用:
EnQueue(&Q, 1),DeQueue(&Q, &x),QueueEmpty(&Q)
QueueEmpty返回几?
A
返回1,和原来一样
判空看的是front等于rear。rear没有退回来,两个不相等。
B
返回0:队列明明空了,却说不空
删掉的1结点正是rear指着的结点。rear还指着它,front指着头结点,两个不相等。
C
程序在DeQueue里就出错停下
DeQueue的每一步都照常做完,错要到后面才露出来。
只剩一个元素时,删掉的正是rear指着的结点。不把rear退回头结点,rear就指着一块已经还给系统的内存:判空出错,下一次EnQueue还会往那块内存里写。
到这里你有了链队:队头在链表头,多记一个队尾指针rear,加头结点。front一直指着头结点,空是front等于rear;删到最后一个时,rear要退回头结点。五个操作都是O(1),换成链队时main只改了类型名,只是不再有队满。下一步队列能用来解决哪些问题?