栈和队列教学实例在数据结构中的应用研究

洪新华 洪新建 /湖南生物机电职业技术学院

栈和队列教学实例在数据结构中的应用研究

洪新华 洪新建 /湖南生物机电职业技术学院

栈和队列是一种特殊的线性结构，从数据结构的角度看它们是线性表，从操作的角度上看它们是操作受限制的线性表。在日常生活中栈和队列也有广泛的应用，如铁路调度、民航机票订购等。在停车场管理系统的应用研究中，狭长的停车通道符合栈的后进先出、便道的管理符合队列的先进先出操作特性，基于此特性研究如何利用栈和队列来模拟停车场管理的问题。

数据结构；线性表；栈；队列

一、数据结构概述

数据结构课程是计算机相关专业学生必修的重要专业基础课，同时也是专业基础课中具有一定难度的课程。它的主要研究的内容就是数据在计算机中的逻辑结构、存储结构以及设计相应的算法对数据进行各种操作。简而言之就是数据结构=逻辑结构+存储结构+算法，其中以算法为中心，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是软件开发类课程的最重要的先修课程之一，学好数据结构是参加计算机各类考试的必备要求，是培养变成能力的必由之路，同时为计算机各门专业课程学习提供良好的基础。数据结构的研究不仅涉及到计算机硬件的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。数据结构中的逻辑结构研究主要有线性结构和非线性结构，线性结构中线性表是一种最常用的线性结构，其中栈和队列是两种典型的线性表。栈被广泛应用于编译软件和程序设计中，而队列在计算机操作系统和事务管理中得到广泛的应用。

二、栈和队列在模拟停车场管理中的应用

停车场管理系统一般都采用栈+队列来模拟管理程序设计。假设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。车辆按到达停车场时间的先后顺序从停车场最里面向门口处停放（最先到达的第一辆车停在停车场最里面）。如果停车场已经停满了n辆车，则后来的车辆只能在停车场大门外的便道上等待。如果停车场内有车要开走，则排在便道上的第一辆车就可以进入停车场。当某辆车要离开时，在他之后进入的车辆必须先退出停车场为它让路，待其开出停车场后，其他车辆再按原次序进入停车场。停车场的管理是最先进去的车辆在最前面，符合栈的后进先出操作特性。在停车场内有空余车位的时候便道上的车辆按到达顺序先行停放则符合队列的特征。该问题便可以采用栈+队列加以实现。

三、任务分析

（一）数据结构描述

由于停车场只有一个大门，因此可以用一个栈来模拟。在便道停车的问题上，因为先排队的车辆先离开便道进入停车场，可以采用一个队列来模拟。又因为该停车场是狭长的停车场，停在中间的车辆是可以提前离开的，为了解决这个问题，我们还需要一个临时地方（车辆规避所）保留为了让路离开停车场的车辆，很显然这个问题也需要用一个栈来实现，在程序中可以采用两个顺序栈s1和s2来表示停车场和车辆规避所，设置一个链队q表示便道，栈和队列定义如下：

（二）系统主要功能设计与实现

1.车辆到达。

void Arrive(SqStack *s1,LQueue *q,ElemType x);

此函数用以表示当车辆x到达时，判断栈s1是否满，若未满就将车辆x进栈s1,若栈已满，就将车辆x入队列q，表示车辆x在便道上等待进入停车场。

此函数用以表示当车辆x要离去时，就在栈s1中寻找此车牌号的车辆，如果找到则让其离开停车场，且根据其停车时间收费，此车离开后将队列q的队头元素进栈s1,如果没找到，则在队列q中去寻找此车牌号码的车，如果找到，则允许离开队列，但不收费，如找不到则显示错误信息，在车辆离开停车场时，如果该车辆位于栈s1的中间位置时，需将此位置到栈顶之间的所有车辆退到栈s2，然后该车辆出栈，然后将栈s2中的车辆倒回栈s1。

2.信息查询。

可以查询车位空闲数目、车位停车情况等。如果车位未满，提示便道上等待的车辆可以进入停车场；如果车位己满，不允许车辆进入停车场，只能在便道上等待。

3.停车场车辆信息。

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

四、结束语

栈和队列是一种常见的数据结构模型，在日常工作生活中有很广泛的应用，真正的把握好这两个数据结构模型对于程序设计来说有很重要的现实意义。

[1]韦斯.数据结构与算法分析:Java语言描述(第2版)[M].机械出版社，2009（1）

[2]陈雁.数据结构[M].北京：高等教育出版社，2010(12)

[3]梅因.数据结构与面向对象程序设计(C++版) [M].北京：清华大学出版社,2012（5）