数据结构中队列的应用研究

陈竹云++叶雯

摘要：队列是一种特殊的线性表，是计算机科学中非常重要的、有用的数据结构，在计算机操作系统和事务管理中得到广泛的应用。在对停车场管理系统的研究中，便道的管理符合队列的先进先出操作特性，基于此特性研究了如何利用队列来模拟管理的方法。

关键词：数据结构；线性表；栈；队列

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）03-0005-03

1数据结构概述

数据结构被称为计算机科学的两大支柱之一，因此数据结构课程被列为计算机专业的一门专业基础必修课程。我们研究数据结构的目的是为了学会如何更好地编写出效率更高的程序。

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。数据结构的研究不仅涉及计算机硬件的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及数据元素在存储器中的分配问题。

数据的逻辑结构分为集合、线性、树形和图形4种结构。线性表是最简单、最常用的一种数据结构，栈和队列是两种特殊的线性表，是计算机科学中非常重要的、有用的数据结构。栈被广泛应用于编译软件和程序设计中，而队列在计算机操作系统和事务管理中得到广泛的应用。

2 队列的基本知识

队列是一种特殊的线性表，特殊之处在于，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。允许插入操作的一端称为队尾，允许删除操作的一端称为队头。队列中没有元素时，称为空队列。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素成为出队。因为队列只允许在一段插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

3 队列在停车场管理中的应用

数据结构课程设计中的停车场管理系统一般都采用栈+队列来模拟管理程序。

假设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。车辆按到达停车场时间的先后，依次从停车场最里面向大门口处停放，最先到达的第一辆车停放在停车场的最里面。如果停车场已经放满n辆车，那么后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车离开，则排在便道上的第一辆车就可以进入停车场。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出停车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入停车场。每辆停放在停车场的车，在它离开停车场时，必须按它停留的时间长短交纳费用，在便道上停车不收费。

停车场的管理是最先进去的车辆在最前面，符合栈的后进先出操作特性。但是，实际的停车场并不一定是狭长的通道，若某车辆到达，只要有空闲车位就可以停车，不一定先到的停在最里面，后到的停在最外面；若某辆车离开，只需按它停留的时间长短交纳费用，便可以离开，不必让它之后进入的车辆为它让路。所以，我认为采用有序链表+队列来模拟停车场管理更符合实际情况。

3.1系统结构分析

该问题包含两方面的信息。一方面是车辆的信息，可包含车牌号、汽车种类等；另一方面是停车记录信息，可包含车牌号、停车位置、到达时间、离开时间等。两方面信息通过车牌号关联起来。使用顺序存储结构、链式存储结构或树形存储结构都可以存储这些信息，但其中各有利弊。

顺序存储结构设计简单，但容量固定，插入和删除需要进行记录的移动。停车记录信息存储不易连续，导致列举时需要对全部停车记录进行完整遍历。对已排序顺序表查找某一记录时，可以采用特定算法（如二分法）提高效率，总体上说实用性和整体效率相对较差。

链式存储结构设计略复杂，容量不设上限，插入和删除较方便，采用链式存储结构的停车记录形式上连续，列举时很方便，但在查找某一记录时需要遍历整个链表效率较低，总体上说实用性和整体效率中上。

树形存储结构相对最复杂，容量也不设上限，插入和删除算法也相对复杂，采用特殊树形结构（如二叉排序树）能够提高查找记录时的效率，停车记录仍可以采用链式结构存储，总体来说实用性和整体效率较好，现实中的数据庫管理系统多是用树形结构来实现的。

从实现难度上来说，顺序存储最简单，链式存储次之，树形存储最难。因此，对学生而言，一般要求采用链式存储来实现。

车辆信息和停车记录信息之间是通过车牌号来关联的，在链式存储结构中可以用指针来表示两者的关联。每辆车的数据域可包含车牌号、汽车种类等，两个指针域，一个指针指向下一个停车位置节点，另一个指针指向该车辆的停车记录链表，该节点的数据域可包含离开时间、到达时间等。

从功能上分析，车辆到达、车辆离开就是在停车记录链表中进行插入和删除操作；信息查询就是遍历停车记录链表，显示该车辆对应的停车记录。

3.2 系统设计及实现

3.2.1 车辆到达

先输入到达车辆的车牌号，若停车场未满，则车进停车场，输入到达时间，记录该车辆在停车场的位置。若停车场已满，则车进便道，记录该车在便道的位置。便道的管理是最先到达的车辆在最前面，一旦停车场有空位，最前面的车辆最先进入停车场，符合队列的先进先出操作特性。可以用一个链队来实现，此时只需要改变便道上车辆结点的连接方式，将模拟便道的链队头结点连到原来的第二辆车上就可以了。

3.2.2 车辆离开

当车库为空时，提示没有车，结束；否则车辆离开。离开时，首先输入离开车辆的车牌号以及离开时间，计算其停放时间并收取相应的停车费用，然后记录要离开车辆在停车场的位置，该位置置空。之后，再检查便道上是否有车等候，如果便道上有等待的车辆，让便道上的第一辆车进入停车场，接着输入要进去停车场的车辆信息，以现在的时间作为车辆到达的时间。便道队列的头结点指向刚进入停车场的车辆结点的后继结点，即原队列中第二辆车的结点。

3.2.3 信息查询

可以查询车位空闲数目、车位停车情况等。如果车位未满，提示便道上等待的车辆可以进入停车场，进入停车场时需要输入车辆的各种信息；如果车位已满，系统会输出排队信息，不允许车辆进入停车场，只能在便道上等待，但是仍然需要信息登记才可以进入便道。

3.2.3.1 停车场车辆信息

显示停车场内每一停车位上是否有车，若有，则显示该车的车牌号、到达时间等信息。统计停车场内车辆数目以及空车位数目。

3.2.3.2 便道车辆信息

显示便道上等待车辆的车牌号以及位置号，统计便道上等待车辆数目。

3.3模拟状态变化图

假设停车场最多能停放车辆：MAX=2。按照从终端读入数据的序列进行模拟管理，汽车的模拟输入信息格式可设定为（到达/离开，车牌号，到达/离开的时刻）。例如，（A，3，10）表示3号牌照车在10点到达，而（L，8，17）表示8号牌照车在17点离开。便道上车辆信息可表示为（位置号，车牌号，指针），停车场内车辆信息可表示为（车牌号，到达时间，指针），停车记录信息可表示为（车位号，指向下一车位节点的指针，指向停车场内车辆信息的指针）。当输入数据项为（E， 0， 0），程序会跳出循环，同时程序结束。模拟程序从第一辆车到达开始运行。

初始状态如图所示：

说明：先后到达了四辆车，因为停车场最多只能停放两辆车，所以最先到达的两辆车依次停放在车位号为1和2的位置上，记录下他们的车牌号和到达时间。由于中间没有离开的车辆，所以后到达的两辆车只能依次停放在便道上。因为停放在便道上的车辆是不需要收费的，所以不需要记录他们的到达时间，只需要记录他们的车牌号就行了。

说明：由于3号牌照车先离开了，所以1号停车位为空。原来便道上等待的第一辆车15号牌照车进入停车场1号停车位，第二辆车2号牌照车成为现在便道上的第一辆车。因为停车时间是从进入停车场开始计算的，所以此刻的时间为15号牌照车的到达时间。在14点的时候又来了一辆20号牌照车，因为此时停车场为满，便道上已有一辆车，所以20号牌照车只能依次排在便道上第二辆车的位置等待。

3.4系统相关问题说明

对于进出停车场的时间，简化了操作，只输入当时的时刻，没有具体到小时和分钟。对于停车费率的设定，可以根据不同的汽车种类分别设定停车费率，如小汽车每小时收费5元，客车每小时收费8元，卡车每小时收费10元。系统根据不同种类的车辆计算出停车费用。当用户输入的车牌号不在停车场时，系统会提示输入错误，请重新输入。

对程序进行操作运行时，可以采用菜单的方式进行。设置欢迎界面、主界面、帮助界面、退出界面、停车场管理主菜单和信息查询子菜单等。使用菜单时，可以利用清屏：system（“cls”）；暂停：system（“pause”）等命令。

4 结束语

从保存信息角度来看，定义队列数据结构是为了保存遍历所经过的路径，亦即保存遍历过程中的每一个结点的信息，而不仅仅只是终结点的信息。而之所以要用队列保存每个遍历节点信息，是因为在確定下一次的遍历节点时，可能需要利用已经遍历过的节点的信息。从次序角度来看，定义队列是为了对序列实行一种顺序操作。

在日常生活中，我们经常会遇到许多为了维护社会正常秩序而需要排队的情境。在现实生活中，队列的应用也很广泛，特别是在计算机科学领域中所起的作用很大。比如我们播放器上的播放列表，我们的数据流对象，异步的数据传输结构（文件IO、管道通讯、套接字等）。还有一些解决对共享资源的冲突访问，比如打印机的打印队列，消息队列，交通状况模拟，呼叫中心用户等待时间的模拟等等。另外在解决主机与外部设备之间速度不匹配问题，解决多用户引起的资源竞争问题等都运用了队列这样的数据结构算法。

参考文献：

[1] 严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，2012.

[2] 朱战立.数据结构——使用C语言[M].北京：电子工业出版社，2014.

[3] 沈华，文志诚，杨晓艳，张明武.数据结构与算法：C语言描述[M].北京：机械工业出版社，2015.

[4] 耿国华，张德同，周明全，等.数据结构——用C语言描述[M].北京：高等教育出版社，2015.

[5] 沈华.数据结构课程中栈和队列实验教学方案设计[J].教育教学论坛，2016（6）.