第三部分、栈(Stack)和队列(Queue)详解

栈和队列，严格意义上来说，也属于线性表，因为它们也都用于存储逻辑关系为 "一对一" 的数据，但由于它们比较特殊，因此将其单独作为一章，做重点讲解。

使用栈结构存储数据，讲究“先进后出”，即最先进栈的数据，最后出栈；使用队列存储数据，讲究 "先进先出"，即最先进队列的数据，也最先出队列。

既然栈和队列都属于线性表，根据线性表分为顺序表和链表的特点，栈也可分为顺序栈和链表，队列也分为顺序队列和链队列，这些内容都会在本章做详细讲解。

九、链式队列及基本操作（C语言实现）

链式队列，简称"链队列"，即使用链表实现的队列存储结构。

链式队列的实现思想同顺序队列类似，只需创建两个指针（命名为 top 和 rear）分别指向链表中队列的队头元素和队尾元素，如图 1 所示:

图 1 链式队列的初始状态

图 1 所示为链式队列的初始状态，此时队列中没有存储任何数据元素，因此 top 和 rear 指针都同时指向头节点。

在创建链式队列时，强烈建议初学者创建一个带有头节点的链表，这样实现链式队列会更简单。

由此，我们可以编写出创建链式队列的 C 语言实现代码为:

//链表中的节点结构

typedef struct QNode{

        int data;

        struct QNode * next;

}QNode;

//创建链式队列的函数

QNode * initQueue(){

        //创建一个头节点

        QNode * queue=(QNode*)malloc(sizeof(QNode));

        //对头节点进行初始化

        queue->next=NULL;

        return queue;

}

1、链式队列数据入队

链队队列中，当有新的数据元素入队，只需进行以下 3 步操作：

1. 将该数据元素用节点包裹，例如新节点名称为 elem；
2. 与 rear 指针指向的节点建立逻辑关系，即执行 rear->next=elem；
3. 最后移动 rear 指针指向该新节点，即 rear=elem；

由此，新节点就入队成功了。

例如，在图 1 的基础上，我们依次将 {1,2,3} 依次入队，各个数据元素入队的过程如图 2 所示:

图 2 {1,2,3} 入链式队列

数据元素入链式队列的 C 语言实现代码为：

QNode* enQueue(QNode * rear,int data){

        //1、用节点包裹入队元素

        QNode * enElem=(QNode*)malloc(sizeof(QNode));

        enElem->data=data;

        enElem->next=NULL;

        //2、新节点与rear节点建立逻辑关系

        rear->next=enElem;

        //3、rear指向新节点

        rear=enElem;

        //返回新的rear，为后续新元素入队做准备

        return rear;

}

2、链式队列数据出队

当链式队列中，有数据元素需要出队时，按照 "先进先出" 的原则，只需将存储该数据的节点以及它之前入队的元素节点按照原则依次出队即可。这里，我们先学习如何将队头元素出队。

链式队列中队头元素出队，需要做以下 3 步操作：

1. 通过 top 指针直接找到队头节点，创建一个新指针 p 指向此即将出队的节点；
2. 将 p 节点（即要出队的队头节点）从链表中摘除；
3. 释放节点 p，回收其所占的内存空间；

例如，在图 2b) 的基础上，我们将元素 1 和 2 出队，则操作过程如图 3 所示：

图 3 链式队列中数据元素出队

链式队列中队头元素出队的 C 语言实现代码为：

void DeQueue(QNode * top,QNode * rear){

        if (top->next==NULL) {

                printf("队列为空");

                return ;

        }

        // 1、

        QNode * p=top->next;

        printf("%d",p->data);

        top->next=p->next;

        if (rear==p) {

                rear=top;

        }

        free(p);

}

注意，将队头元素做出队操作时，需提前判断队列中是否还有元素，如果没有，要提示用户无法做出队操作，保证程序的健壮性。

3、总结

通过学习链式队列最基本的数据入队和出队操作，我们可以就实际问题，对以上代码做适当的修改。

前面在学习顺序队列时，由于顺序表的局限性，我们在顺序队列中实现数据入队和出队的基础上，又对实现代码做了改进，令其能够充分利用数组中的空间。链式队列就不需要考虑空间利用的问题，因为链式队列本身就是实时申请空间。因此，这可以算作是链式队列相比顺序队列的一个优势。

这里给出链式队列入队和出队的完整 C 语言代码为：

#include <stdio.h>

#include <stdlib.h>

typedef struct QNode{    

        int data;    

        struct QNode * next;

}QNode;

QNode * initQueue(){    

        QNode * queue=(QNode*)malloc(sizeof(QNode));    

        queue->next=NULL;    

        return queue;

}

QNode* enQueue(QNode * rear,int data){    

        QNode * enElem=(QNode*)malloc(sizeof(QNode));    

        enElem->data=data;    

        enElem->next=NULL;    

        //使用尾插法向链队列中添加数据元素    

        rear->next=enElem;    

        rear=enElem;    

        return rear;

}

QNode* DeQueue(QNode * top,QNode * rear){    

        if (top->next==NULL) {        

                printf("\n队列为空");        

                return rear;    

        }    

        QNode * p=top->next;    

        printf("%d ",p->data);    

        top->next=p->next;    

        if (rear==p) {        

                rear=top;    

        }    

        free(p);    

        return rear;

}

int main() {    

        QNode * queue,*top,*rear;    

        queue=top=rear=initQueue();//创建头结点    

        //向链队列中添加结点，使用尾插法添加的同时，队尾指针需要指向链表的最后一个元素    

        rear=enQueue(rear, 1);    

        rear=enQueue(rear, 2);    

        rear=enQueue(rear, 3);    

        rear=enQueue(rear, 4);    

        //入队完成，所有数据元素开始出队列    

        rear=DeQueue(top, rear);    

        rear=DeQueue(top, rear);    

        rear=DeQueue(top, rear);    

        rear=DeQueue(top, rear);    

        rear=DeQueue(top, rear);    

        return 0;

}

程序运行结果为：

1 2 3 4
队列为空

---

十、[数据结构实践项目]变态的停车场管理系统

实践是检验真理的唯一标准，学习也是如此。本章对栈和队列做了详细的讲解，为了让大家能够学以致用，特推出一个项目供大家练习（包含了本章所有的重要知识点）。

本项目比较烧脑，要求对栈和队列有一定深度的了解，虽有完整代码供大家参考，但是建议先自行完成，然后参照本节给出的完整代码。

1、项目简介

设停车场是一个可以停放 n 辆汽车的南北方向的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端）。

若车场内已停满 n 辆车，那么后来的车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。

项目要求：试为停车场编制按上述要求进行管理的模拟程序。要求程序输出每辆车到达后的停车位置（停车场或便道上），以及某辆车离开停车场时应缴纳的费用和它在停车场内停留的时间。

2、设计思路

停车场的管理流程如下：

1. 当车辆要进入停车场时，检查停车场是否已满，如果未满则车辆进入停车场；如果停车场已满，则车辆进入便道等候。
2. 当车辆要求出栈时，先让在它之后进入停车场的车辆退出停车场为它让路，再让该车退出停车场，让路的所有车辆再按其原来进入停车场的次序进入停车场。之后，再检查在便道上是否有车等候，有车则让最先等待的那辆车进入停车场。

3、项目中涉及到的数据结构

1. 由于停车场只有一个大门，当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，先进停车场的后退出，后进车场的先退出，符合栈的“后进先出，先进后出”的操作特点，因此，可以用一个栈来模拟停车场。
2. 而当停车场满后，继续来到的其它车辆只能停在便道上，根据便道停车的特点，先排队的车辆先离开便道进入停车场，符合队列的“先进先出，后进后出”的操作特点，因此，可以用一个队列来模拟便道。
3. 排在停车场中间的车辆可以提出离开停车场，并且停车场内在要离开的车辆之后到达的车辆都必须先离开停车场为它让路，然后这些车辆依原来到达停车场的次序进入停车场，因此在前面已设的一个栈和一个队列的基础上，还需要有一个地方保存为了让路离开停车场的车辆，由于先退出停车场的后进入停车场，所以很显然保存让路车辆的场地也应该用一个栈来模拟。

因此，本题求解过程中需用到两个栈和一个队列。栈和队列都既可以用顺序结构实现，也可以用链式结构实现。

4、程序清单

以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。

每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费，停车场费用按照 1 小时 1.5元）。

5、实现代码

#include <stdio.h>

#define MAX 3//模拟停车场最多可停的车辆数

//车的必要信息的结构体

typedef struct{

        int number;

        int arrive_time;

}zanInode;

//进入停车场的处理函数

int push(zanInode * park,int *parktop,zanInode car){

        //如果停车场已满，该车需进入便道等待（先返回 -1 ，在主程序中处理）

        if ((*parktop)>=MAX) {

                printf("停车场已停满！需停到便道上.\n");

                return -1;

        }else{//否则将该车入栈，同时进行输出

                park[(*parktop)]=car;

                printf("该车在停车场的第 %d 的位置上\n",(*parktop)+1);

                (*parktop)++;

                 return 1;

        }

}

//车从停车场中退出的处理函数

zanInode pop(zanInode *park,int *parktop,int carnumber,zanInode * location,int *locationtop){

        int i;

        //由于函数本身的返回值需要返回一辆车，所以需要先初始化一个

        zanInode thecar;

        thecar.number=-1;

        thecar.arrive_time=-1;

        //在停车场中找到要出去的车

        for (i=-1; i<(*parktop); i++) {

                if (park[i].number==carnumber) {

                        break;

                }

        }

        //如果遍历至最后一辆车，还没有找到，证明停车场中没有这辆车

        if (i==(*parktop)) {

                printf("停车场中没有该车\n");

        }else{//就将该车移出停车场

                //首先将在该车后进入停车场的车全部挪至另一个栈中

                while ((*parktop)>i+1) {

                        (*parktop)--;

                        location[*locationtop]=park[*parktop];

                        (*locationtop)++;

                }

                //通过以上的循环，可以上该车后的左右车辆全部移开，但是由于该车也要出栈，所以栈顶指针需要下移一个位置，当车进栈时，就直接覆盖掉了

                (*parktop)--;

                thecar=park[*parktop];

                //该车出栈后，还要将之前出栈的所有车，在全部进栈

                while ((*locationtop)>0) {

                        (*locationtop)--;

                        park[*parktop]=location[*locationtop];

                        (*parktop)++;

                }

        }

        return thecar;

}

int main(int argc, const char * argv[]) {

        //停车场的栈

        zanInode park[MAX];

        int parktop=0;//栈顶指针

        //辅助停车场进行挪车的栈

        zanInode location[MAX];

        int locationtop=0;//栈顶指针

        //模拟便道的队列

        zanInode accessroad[100];

        int front,rear;//队头和队尾指针

        front=rear=0;

        char order;//进出停车场的输入命令

        int carNumber;//车牌号

        int arriveTime;//到停车场的时间

        int leaveTime;//离开停车场的时间

        int time;//车在停车场中逗留的时间

        zanInode car;

        printf("有车辆进入停车场（A）;有车辆出停车场(D);程序停止（#）:\n");

        while (scanf("%c",&order)) {

                if (order=='#') {

                        break;

                }

                switch (order) {

                        case 'A':

                                printf("登记车牌号(车牌号不能为 -1)及车辆到达时间（按小时为准）：\n");

                                scanf("%d %d",&carNumber,&arriveTime);

                                car.number=carNumber;

                                car.arrive_time=arriveTime;

                                //当有车想要进入停车场时，首先试图将该车进入停车场

                                int result=push(park, &parktop, car);

                                //如果返回值为 -1 ，证明停车场已满，需要停在便道中

                                if (result==-1) {//停在便道上

                                        accessroad[rear]=car;

                                        printf("该车在便道的第 %d 的位置上\n",rear+1-front);

                                        rear++;

                                }

                                break;

                        case 'D':

                                printf("出停车场的车的车牌号以及离开的时间：\n");

                                scanf("%d %d",&carNumber,&leaveTime);

                                //当有车需要出停车场时，调用出栈函数

                                car=pop(park, &parktop, carNumber, location, &locationtop);

                                //如果返回的车的车牌号为-1 ，表明在停车场中没有查找到要查找的车

                                if (car.number!=-1) {

                                        //停留时间，等于进停车场的时间-

                                        time=leaveTime-car.arrive_time;

                                        printf("该车停留的时间为：%d 小时,应缴费用为：%f 元\n",time,time*1.5);

                                        //一旦有车离开停车场，则在便道中先等待的车就可以进入，进入时需设定车进入的时间

                                        if (front!=rear) {

                                                car=accessroad[front];

                                                printf("在便道上第1的位置上，车牌号为：%d 的车进停车场的时间为：\n",car.number);

                                                scanf("%d",&car.arrive_time);

                                                park[parktop]=car;

                                                front++;

                                                parktop++;

                                        }else{

                                                printf("便道上没有等待车辆，停车场不满！\n");

                                        }

                                }

                                break;

                        default:

                                break;

                }

                printf("\n有车辆进入停车场（A）;有车辆出停车场(D);程序停止（#）:\n");

                scanf("%*[^\n]"); scanf("%*c");//清空缓冲区

        }

        return 0;

}

运行结果:
有车辆进入停车场（A）;有车辆出停车场(D);程序停止（#）:
A
登记车牌号(车牌号不能为 -1)及车辆到达时间（按小时为准）：
633 6
该车在停车场的第 1 的位置上

有车辆进入停车场（A）;有车辆出停车场(D);程序停止（#）:
A
登记车牌号(车牌号不能为 -1)及车辆到达时间（按小时为准）：
634 7
该车在停车场的第 2 的位置上

有车辆进入停车场（A）;有车辆出停车场(D);程序停止（#）:
A
登记车牌号(车牌号不能为 -1)及车辆到达时间（按小时为准）：
635 8
该车在停车场的第 3 的位置上

有车辆进入停车场（A）;有车辆出停车场(D);程序停止（#）:
A
登记车牌号(车牌号不能为 -1)及车辆到达时间（按小时为准）：
636 9
停车场已停满！需停到便道上.
该车在便道的第 1 的位置上

有车辆进入停车场（A）;有车辆出停车场(D);程序停止（#）:
D
出停车场的车的车牌号以及离开的时间：
633 10
该车停留的时间为：4 小时,应缴费用为：6.000000 元
在便道上第1的位置上，车牌号为：636 的车进停车场的时间为：
10

有车辆进入停车场（A）;有车辆出停车场(D);程序停止（#）:
D
出停车场的车的车牌号以及离开的时间：
634 10
该车停留的时间为：3 小时,应缴费用为：4.500000 元
便道上没有等待车辆，停车场不满！

有车辆进入停车场（A）;有车辆出停车场(D);程序停止（#）:
A
登记车牌号(车牌号不能为 -1)及车辆到达时间（按小时为准）：
637 11
该车在停车场的第 3 的位置上

有车辆进入停车场（A）;有车辆出停车场(D);程序停止（#）:
#