浅谈栈和队列的应用

《浅谈栈和队列的应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、浅谈栈与队列的应用摘要：数据结构是计-算机中一个非常重要的分支，它是现实世界数据与计算机世界数据连接的关键，它主要涵盖两方血的内容：逻辑层面的数据结构和计算机存储数据物理层的数据结构。关于数据结构中的线性表、栈、队列，将上述两方面的内容进行介绍，进行横向的比较，从而更清楚地看到它们之I'可的联系与区别，并分析它们在现实计算中的应用。关键词：线性表；堆栈；队列；应用开发DiscussionontheApplicationofStackandQueueAbstract:Datastructureisaveryimportantbranchofacomputer,itisthekeyofth

2、econnectionofrealworlddataandcomputerworlddata,itmainlycoversthefollowingtwocontents:logicleveldatastructureandcomputerdatastoragephysicallayerdatastructure.Aboutthedatastructureofthelinearlist,stack,queuejtintroducesthecontentoftheabove-mentionedtwoaspects,carriesonthehorizontalcomparison,thusm

3、oreclearlyseetherelationshipanddifferencebetweenthem.Andanalyzestheminrealinthecalculationoftheapplication.Keywords:LinearList;Stack;Queue;ApplicationDevelopment0引言栈和队列可以看作线性表的特例，它们都具有和线性表相同的存储方式,顺序存储和链式存储，栈有顺序栈和链式栈，队列有顺序队列和链式队列。但从数据类型角度看，它们是和线性表大不相同的两类重要的抽彖数据类型。由于它们被广泛应用在各种软件系统屮，因此在面向对象的程序设计屮，它

4、们是多型数据类型:啟。1基本概念1.1线性表的概念和特性线性表是有限元素（al,a2,a3--->an）有序序列的集合，al,a2…,an都是完全相同结构的数据类型，同时它们Z间的排列严格有序，其屮任何元素都对应唯一的前驱以及唯一的后继。这样一个序列可以有查询、删除、插入队列任何位置的数据操作⑶。1.2栈的概念和特性栈作为一种限定性线性表，它限定插入和删除操作都在表的同一端进行。允许插入和删除元索的一端称为栈顶，另一端为栈底；栈底固定，栈顶浮动。栈的插入操作被形彖地称为进栈或入栈，删除操作称为出栈或退栈。我们只能从一端取出放入数据，即压入栈和弹出栈，所以它的顺序是“后进先出”，如图1。

5、作者简介:刘碧霞（1993年一），女,本科,1063384634@qq.com。1.3队列的概念和特性队列与栈类似，是另一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素。允许插入元素的一端称为队尾，允许删除元素的一端称为队头。它的操作不同的地方是两端存、収数据，且仅仅是一端収（队头）一端存（队尾），所以它的顺序是“先进先出”,如图2。进校出核栈顶图1栈图2队列2存储结构2.1顺序结构线性表是用一圧大小的数据来存放线性表，数组反度代表线性表的反度，元素在数组的位置代表元素在线性表的位置。但对数组屮元素不能跳跃插入，因为线性表中元素是顺序且连接着的，不像数组屮间可以空元素

6、。同时删除元素时，必须大量移动剩下的元素，因为必须实现其连续性。插入元素同样需要人量移动数据。因此这样存储的运行效率并不够高。所以对于有着频繁插入和删除运算的线性表，是不适合采用顺序存储的。堆栈是类似于线性表，利用数组存储，只从这个数组的一端插入和删除数据，不存在从屮间“挖”数据，故不存在人量数据移动的问题，唯一不足的是数组人小是有限的，会存在栈满的现象。如果数组大小圧义过大，则乂有大量存储空间没有被利用，会有资源浪费。队列是初始存储类似于线性表，但由于只能从一边进入另一边出，所以数据会随着数据操作而不断“前进使队列像一条“蠕虫”一样慢慢“爬过”队列定义的全部空间，而且“爬过”的空间就

7、无法再次得到运用。“蠕虫”爬到数组尽头Z后则无法前进，而此时很可能数组前端还有大量的数据未得到使用。因此我们将一个数组看作是“相连”的，即将整个数组看做一个环形，而队列“蠕虫”则会在这个环形轨道中持续“爬动”，直到数据装满整个数据空间。但这里还有第二个问题，这样的定义Z后队列空与满，指向队头的front与指向队尾的rear所处的相对位置是完全一样的。这样一个类似于“活塞”的工具，它总是紧邻队列中第一个数据元素，是可以移动的，但它本身不存放任何数