- 零基础学算法（第4版）
- 张昆 戴艳
- 5111字
- 2025-02-25 05:17:53
2.3 先进先出结构：队列
在程序设计中，队列是一种很常用的数据结构。队列在现实生活中就有对应的例子，可以认为是来源于生活。本节介绍队列的特点和操作队列的C语言代码。
2.3.1 什么是队列
队列是一种特殊的线性表，只允许在表的前端进行删除操作，而在表的后端进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。当队列中没有元素时，称为空队列。队列具有“先进先出”的特点。
在日常生活中，随处可见队列的例子。例如，去火车站买车票，每个窗口都有很多人排队买票，每个窗口就是一个队列。在这个队列中，新来的人总是排在队列的后面，排在最前面的人总是先购票，这就是“先来先服务”原则。
提示 队列这种数据结构与此相同，也是一种先进先出（First In First Out，FIFO）的结构。
对于队列这种结构，其操作比较简单，主要有以下几种常用操作。
·初始化队列：创建一个队列。
·进队列：将一个元素添加到队尾（相当于到队列最后排队等候）。
·出队列：将队头的元素取出，同时删除该元素，使下一个元素成为队头。
·获取队列第1个元素：将队头的元素取出，不删除该元素（队头仍然是该元素）。
·获取队列长度：根据队头、队尾计算出队列中元素的数量。
2.3.2 操作队列
队列是线性表的一种特殊表现形式（线性表可在表的中间部位插入或删除元素，而队列不允许这种操作），因此，其存储结构与线性表相同，也可采用顺序存储方式和链式存储方式。本节只介绍顺序存储队列的方式，有关用链式存储队列的方式可参见上节中链表的相关介绍。
将队列用顺序存储方式保存时，在内存中申请一片区域用来保存元素，如图2-17所示。当第一个元素A进入队列时，因是空列队，因此元素A将排在队头，接着B、C、D顺次进入队列，就得到如图所示的队列。其中head指向队头，以指示队头元素出队操作，tail指向队尾，以指示新增元素进入队列。
执行一次出队操作，元素A将出队，这时第2个元素B将成为队头，head指针将指向该元素，如图2-18所示。
图2-17 顺序队列
图2-18 元素A出队后的队列
如果要将元素E入队，则是将其放入tail指针指向元素的后一个位置（图2-18中序号为5的单元），并使tail指针指向序号为5的单元。
1．定义顺序队列结构
了解队列的操作后，接下来就可编写用C语言操作队列的相关函数。
【程序2-11】顺序队列操作函数“2-11 SeqQueue.h”
1 #define QUEUEMAX 15
2 typedef struct //定义队列结构体
3 {
4 DATA data[QUEUEMAX]; //队列数组
5 int head; //队头
6 int tail; //队尾
7 }SeqQueue;
【程序说明】
以上代码定义一个队列结构，其中第1行设置队列的大小（即可允许多少元素进入队列），第3行使用DATA类型定义一个数组，用来保存队列中各元素内容（数据类型DATA在主调程序中定义，以方便操作不同类型的数据），第5、6行定义的变量保存队头和队尾的序号。
提示 与顺序表对比，在队列的数据结构中增加了队头和队尾的两个指针，指示队列的队头和队尾，方便程序判断操作。
2．初始化队列
在使用队列之前，首先需从系统中申请一片内存，用来保存队列中的数据，并设置队头和队尾的序号。这些操作将在初始化时完成。具体代码如下；
8 SeqQueue *SeqQueueInit()
9 {
10 SeqQueue *q;
11 if(q=(SeqQueue *)malloc(sizeof(SeqQueue))) //申请保存队列的内存
12 {
13 q->head = 0; //设置队头
14 q->tail = 0; //设置队尾
15 return q;
16 }else
17 return NULL; //返回空
18 }
【程序说明】
该函数不需要参数，但要返回一个指向列队的指针，后续代码将使用该指针操作队列。第11行申请内存，若分配内存成功，执行第13、14行设置队头队尾的序号都为0，然后返回分配的内存首地址。
由于队列由malloc函数申请内存块来保存元素的值，因此，在不使用队列时，应调用free函数显式地释放对该内存块的使用，编写以下函数用来释放队列：
19 void SeqQueueFree(SeqQueue *q) //释放队列所占内存
20 {
21 if (q!=NULL)
22 free(q);
23 }
编程经验 使用malloc函数申请的内存，都应在程序中显式地调用free函数将其释放。
3．获取队列状态
根据队列结构的性质，对队列的操作只能在队头（出队）或队尾（入队）进行，在进行出队/入队操作时应检查队列的状态，如进行出队操作时，应检查队列是否为空，进行入队操作时，应检查队列是否已满，这些函数的代码都很简单，具体如下：
24 int SeqQueueIsEmpty(SeqQueue *q) //队列是否为空
25 {
26 return (q->head==q->tail);
27 }
28 int SeqQueueIsFull(SeqQueue *q) //队列是否已满
29 {
30 return (q->tail==QUEUEMAX);
31 }
32 int SeqQueueLen(SeqQueue *q) //获取队列长度
33 {
34 return(q->tail-q->head);
35 }
【程序说明】
·第24~27行判断队列是否为空，当队头head和队尾tail的序号相等时，则队列为空。
·第28~31行判断队列是否已满，当队尾tail序号等于常量QUEUEMAX，则表示队列已满，无法再进行入队操作。
·第32~35行返回队列长度，将队尾tail序号减去队头head序号即可得到队列的长度。
技巧 在队列的数据结构中定义的head和tail可方便地判断队列的状态。
4．入队操作
入队操作是队列最常用的操作，就是将元素添加到队列的尾部（由队尾tail序号决定），然后将队尾序号增加1，使其指向新增的元素。具体代码如下：
36 int SeqQueueIn(SeqQueue *q,DATA data) //顺序队列的入队函数
37 {
38 if(q->tail==QUEUEMAX) //判断队列是否已满
39 {
40 printf("队列已满!\n");
41 return(0);
42 }else{ //队列未满
43 q->data[q->tail++]=data; //加入队列, 修改队尾序号
44 return(1);
45 }
46 }
该函数有两个参数，其中q为指向队列的指针，data为要添加到队列中的元素。
编程经验 在入队操作时，必须判断队列是否已满，如果未进行判断就入队，可能会造成数据保存到未知内存区域。
5．出队操作
与入队操作相反，出队操作就是将队头元素取出。出队操作从队列首部取出队头元素（实际是返回队头元素的指针），然后修改队头head的序号，使其指向后一个元素（这样，原来指针指向的元素就不能被访问了，相当于被删除）。具体代码如下：
47 DATA *SeqQueueOut(SeqQueue *q) //顺序队列的出队操作
48 {
49 if(q->head==q->tail) //判断队列是否已空
50 {
51 printf("\n队列已空!\n");
52 return NULL;
53 }else{ //队列未空
54 return &(q->data[q->head++]); //返回指向队头的元素指针, 修改队头序号
55 }
56 }
该函数的返回值为一个指向队列中的元素DATA的指针。
6．获取队头元素
与出队操作不同，获取队头元素只是查看队头元素的内容，并不使其出队（即不从队列中删除该元素，也就是不修改队头指针head的值），具体代码如下：
47 DATA *SeqQueuePeek(SeqQueue *q) //获取队头元素
48 {
49 if(SeqQueueIsEmpty(q)) //判断队列是否为空
50 {
51 printf("\n队列为空!\n");
52 return NULL;
53 }else{ //队列不为空
54 return &(q->data[q->head]); //返回队头元素指针
55 }
56 }
以上就是对顺序表队列的常用操作。采用这种方式操作队列将出现一个问题，就是队列的假溢出。什么是假溢出？看下面的情况：假如有如图2-19所示的情况，tail已指向队列的最后，这时如果使用SeqQueueIn函数进行入队操作，虽然队列前面有5个空位置，但仍将显示队列已满。
为了解决这种假溢出，可有多种解决方案。
例如，可以在出队函数SeqQueueOut中增加移动元素的操作，即每次进行完出队操作后，就将队列中后面的元素向前移动，始终保持队列的第1个位置有元素，每次都从第1个位置进行出队操作。但是，这种操作由于需要移动大量数据，效率很低。
另一种方法就是将队列的首尾相连，构成一个环形，下面将介绍这种环形队列的操作。
2.3.3 循环队列的操作
将队列的首尾相连构成一个环形区域，当在第n个位置进行元素的入队操作后，下一个地址就“翻转”为1。采用这种方式的队列称为循环队列，而前面介绍的队列形式称为顺序队列。
循环队列实际存储结构仍然与顺序队列相同，只是在逻辑上将其形成如图2-20所示的环形。当第n个元素位置入队数据后，后面再进行入队操作，则又从第1个位置开始。
图2-19 队列的假溢出
图2-20 循环队列的结构
编程经验 在循环队列中，主要需要计算队尾tail和队头head的序号。
以入队操作为例，当需要将元素入队操作时可按以下步骤进行：
（1）将队尾序号tail增加1，即tail=tail+1。
（2）若tail=n+1，则tail=1。
其实，前两步可使用表达式tail=（tail+1）%n计算，即计算tail时，按n取余即可。
（3）若head=tail，即尾指针与头指针重合了，表示队列中元素已装满，则应提示溢出处理。
（4）若未溢出，则将元素入队即可。
下面列出循环队列的操作函数，其中大部分函数与顺序队列的操作相同。
【程序2-12】循环队列操作函数“2-12 CycQueue.h”
1 #define QUEUEMAX 15
2 typedef struct //定义循环队列结构体
3 {
4 DATA data[QUEUEMAX]; //队列数组
5 int head; //队头
6 int tail; //队尾
7 }CycQueue;
8 CycQueue *CycQueueInit() //循环队列初始化
9 {
10 CycQueue *q;
11 if(q=(CycQueue *)malloc(sizeof(CycQueue))) //申请保存队列的内存
12 {
13 q->head = 0; //设置队头
14 q->tail = 0; //设置队尾
15 return q;
16 }else
17 return NULL; //返回空
18 }
19 void CycQueueFree(CycQueue *q) //释放队列
20 {
21 if (q!=NULL)
22 free(q);
23 }
24 int CycQueueIsEmpty(CycQueue *q) //队列是否为空
25 {
26 return (q->head==q->tail);
27 }
28 int CycQueueIsFull(CycQueue *q) //队列是否已满
29 {
30 return ((q->tail+1)%QUEUEMAX==q->head);
31 }
32 int CycQueueIn(CycQueue *q,DATA data) //入队操作
33 {
34 if((q->tail+1)%QUEUEMAX == q->head )
35 {
36 printf("队列已满!\n");
37 return 0;
38 }else{
39 q->tail=(q->tail+1)%QUEUEMAX; //求列尾序号
40 q->data[q->tail]=data;
41 return 1;
42 }
43 }
44 DATA *CycQueueOut(CycQueue *q) //循环队列的出队函数
45 {
46 if(q->head==q->tail) //队列为空
47 {
48 printf("队列已空!\n");
49 return NULL;
50 }else{
51 q->head=(q->head+1)%QUEUEMAX;
52 return &(q->data[q->head]);
53 }
54 }
55 int CycQueueLen(CycQueue *q) //获取队列长度
56 {
57 int n;
58 n=q->tail-q->head;
59 if(n<0)
60 n=QUEUEMAX+n;
61 return n;
62 }
63 DATA *CycQueuePeek(CycQueue *q) //获取队列中第1个位置的数据
64 {
65 if(q->head==q->tail)
66 {
67 printf("队列已经为空!\n");
68 return NULL;
69 }else{
70 return &(q->data[(q->head+1)%QUEUEMAX]);
71 }
72 }
【程序说明】
从以上代码可看出，大部分代码与顺序队列中的代码相同，如队列的结构、队列初始化等函数。下面只介绍不同部分的代码。
·第28~31行判断队列是否已满，第30行判断tail的下一元素是否与head相同，若相同，则表示队列已满。若不理解可参见图2-15的示意图。
·第32~43行进行循环队列的入队操作，第34行判断队列是否已满，第39行计算tail队尾的序号（用求模运算），然后执行第40行将元素保存到队列序号为tail处。
·第44~54行进行循环队列的出队操作，第51行计算head队头的序号（用求模运算），然后执行第52行取出head所指向的元素（队头）。
·第55~62行根据tail减head后的值计算得出队列的长度。
·第63~72行获取循环队列中队头head的元素。
2.3.4 实例：银行排号程序
随着银行业务的扩展，到银行办理业务的人越来越多，经常可以见到银行营业大厅中排着长队。为了改善服务，很多银行都设置了排号系统，顾客去办理业务时，通过排号机生成一个号码，然后可坐在休息区等候排号系统按号码进行呼叫，从而不需要用户站在柜台前等候，缓解用户等候时的烦躁情绪。要求编写程序，模拟该排号系统。
提示 其实这就是一个队列的操作，可首先创建一个队列，每一位顾客通过该系统得到一个序号，程序将该序号添加到队列中（入队操作）。银行柜台工作人员处理完一个顾客的业务后，可选择办理下一顾客的业务，程序将从队列的头部获取下一位顾客的序号（出队操作）。
按此编写具体的代码如下：
【程序2-13】银行排号程序“2-13 BankQueue.c”
首先编写代码定义DATA数据类型。
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <time.h> //引入时间头文件
4 typedef struct
5 {
6 int num; //顾客编号
7 long time; //进入队列时间
8 }DATA;
9 #include "2-12 CycQueue.h"
10 int num; //顾客序号
【程序说明】
·第4~8行定义类型DATA，用来表示进入队列的数据，其中num为顾客序号，time为顾客取号的时间。
·第9行包含循环队列的头文件，表示本例通过循环队列来进行操作。
·第10行定义一个全局变量，用来保存顾客的序号，该序号将保存到DATA类型的num变量中。
提示 在该排号程序中，将有两种操作，一是顾客排队（入队），另外一个操作就是工作人员从队列中呼叫一个顾客去办理业务（出队）。
下面先编写新增顾客的函数，该函数为新到的顾客生成一个序号，并添加到队列中，具体代码如下：
11 void add(CycQueue *q) //新增顾客排列
12 {
13 DATA data;
14 if(!CycQueueIsFull(q)) //如果队列未满
15 {
16 data.num=++num; //保存顾客序号
17 data.time=time(NULL); //保存顾客排号时间
18 CycQueueIn(q,data); //调用入队函数
19 }
20 else //若队列已满
21 printf("\n排队的人太多, 请稍候再排队!\n"); //显示提示信息
22 }
【程序说明】
在Add函数中，第14行判断若队列未满，则在第18行调用CycQueueIn函数将新顾客的编号等信息入队等候，否则就提示排队人太多。
下面是柜台工作人员呼叫下一顾客的函数：
23 void next(CycQueue *q) //通知下一顾客准备
24 {
25 DATA *data;
26 if(!CycQueueIsEmpty(q)) //若队列不为空
27 {
28 data=CycQueueOut(q); //取队列头部的数据（出队）
29 printf("\n请编号为%d的顾客办理业务!\n",data->num);
30 }
31 if(!CycQueueIsEmpty(q)) //若队列不为空
32 {
33 data=CycQueuePeek(q); //取队列中指定位置的数据
34 printf("请编号为%d的顾客准备, 马上将为您办理业务!\n",data->num);
35 }
36 }
【程序说明】
在next函数中，第26行判断若队列不为空，则在第28行调用CycQueueOut函数获取队列首部顾客的信息，通过第29行呼叫该编号的顾客前去办理业务。此时，该编号的顾客将从队列中被删除，接着在第31行再次判断队列若不为空，第33行调用CycQueuePeek函数获取队列首部顾客（已经是下一顾客了）的信息，并提醒该编号的顾客做好准备，下一次为其办理业务。
接下来编写主函数，根据不同的选择分别调用add或next函数来进行工作。具体代码如下：
37 int main()
38 {
39 CycQueue *queue1;
40 int i,n;
41 char select;
42 num=0; //顾客序号
43 queue1=CycQueueInit(); //初始化队列
44 if(queue1==NULL)
45 {
46 printf("创建队列时出错!\n");
47 getch();
48 return 0;
49 }
50 do{
51 printf("\n请选择具体操作:\n");
52 printf("1.新到顾客\n");
53 printf("2.下一个顾客\n");
54 printf("0.退出\n") ;
55 fflush(stdin);
56 select=getch();
57 switch(select)
58 {
59 case '1':
60 add(queue1);
61 printf("\n现在共有%d位顾客在等候!\n",CycQueueLen(queue1));
62 break;
63 case '2':
64 next(queue1);
65 printf("\n现在共有%d位顾客在等候!\n",CycQueueLen(queue1));
66 break;
67 case '0':
68 break;
69 }
70 }while(select!='0');
71 CycQueueFree(queue1); //释放队列
72 getch();
73 return 0;
74 }
【程序说明】
主函数代码较多，不过逻辑很简单，首先在第43行初始化一个队列；接着在第51~54行显示一个菜单，用来模拟顾客排列或工作人员处理下一顾客业务；第57~68行根据用户的模拟选择，分别调用不同的函数进行操作；第50~70行为一个循环，当退出该循环后，表示操作完成；第71行调用CyeQueueFree函数释放队列所占用的内存空间。
编译执行以上代码，在菜单提示下输入1，表示有1位新顾客到来排队，再输入一次1，表示又有1位新顾客到来排队（这时已有2位顾客在排队等候）。这时，输入一次2，表示银行柜台开始办理业务，将显示呼叫1号顾客办理业务，并提示2号顾客做准备，执行结果如图2-21所示。
图2-21 【程序2-13】执行结果