从线性表谈到栈与队列

　　摘 要：数据结构是计算机中一个非常重要的分支，它是现实世界数据与计算机世界数据连接的关键，它主要涵盖两方面的内容：逻辑层面的数据结构及计算机存储数据物理层的数据结构。关于数据结构中的线性表、栈、队列，文章将上述两方面的内容进行介绍，进行横向的比较，从而更清楚地看到它们之间的联系与区别。并分析它们在现实计算中的应用。
　　关键词：线性表；堆栈；队列
　　中图分类号：tp311.12 文献标识码：a 文章编号：1006-8937（2012）17-0081-02
　　1 逻辑关系
　　①线性表。线性表是有限元素（a1,a2,a3…，an）有序序列的集合，a1,a2…，an都是完全相同结构的数据类型，同时它们之间的排列严格有序，其中任何元素都对应唯一的前驱以及唯一的后继。这样一个序列可以有查询、删除、插入队列任何位置的数据操作。
　　②堆栈。堆栈也是一个有序序列的集合，结构上与线性表规定一样。但它的运算受到严格的限制（故也叫限定性线性表）。这个序列中我们只能从一端取出放入数据，即压入栈和弹出栈，所以它的顺序是“先进先出”，如图1所示。
　　③队列。队列与栈类似，属于限定性线性表，它的操作不同的地方是两端存、取数据，且仅仅是一端取（队头）一端（队尾），所以它的数据是“先入先出”。
　　2 物理结构
　　2.1 顺序结构
　　{1}线性表。用一定大小的数据来存放线性表，数组长度代表线性表的长度，元素在数组的位置代表元素在线性表的位置。WWW.11665.COM但对数组中元素不能跳跃插入，因为线性表中元素是顺序且连接着的，不像数组中间可以空元素。同时删除元素时，必须大量移动剩下的元素，因为必须实现其连续性。插入元素同样需要大量移动数据。因此这样存储的运行效率并不够高。所以对于有着频繁插入和删除运算的线性表，是不适合采用顺序存储的。
　　{2}堆栈。类似于线性表，利用数组存储，只从这个数组的一端插入和删除数据，不存在从中间“挖”数据，故不存在大量数据移动的问题，唯一不足的是数组大小是有限的，会存在栈满的现象。如果数组大小定义过大，则又有大量存储空间没有被利用，会有资源浪费。
　　{3}队列。初始存储类似于线性表，但由于只能从一边进入另一边出，所以数据会随着数据操作而不断“前进”，使队列像一条“蠕虫”一样慢慢“爬过”队列定义的全部空间，而且“爬过”的空间就无法再次得到运用。“蠕虫”爬到数组尽头之后则无法前进，而此时很可能数组前端还有大量的数据未得到使用。因此我们将一个数组看作是“相连”的，即将整个数组看做一个环形，而队列“蠕虫”则会在这个环形轨道中持续“爬动”，直到数据装满整个数据空间。但这里还有第二个问题，这样的定义之后队列空与满，指向队头的front与指向队尾的rear所处的相对位置是完全一样的，如图2、图3所示。
　　这样一个类似于“活塞”的工具，它总是紧邻队列中第一个数据元素，是可以移动的，但它本身不存放任何数据。同时将队头指针指向这个“活塞”，那么队空与队满的冲突情况就得以避免，如图4、图5所示。
　　2.2 链 式
　　由于数组的静态分配、不易扩充、插入删除会有大量数据移动等种种局限性，我们引入链式存储方式。通过动态分配存储空间，最有效地利用空间。
　　线性表：通过动态分配，分配物理上不一定相邻的存储单元。为表示他们的连续性连接性，再在分配这个存储单元时，附加一部分存储单元——指针域（也叫链接域）来指出这个元素的后继元素的存储地址。这样前面出现的删除时间复杂度高算法效率低的问题就得到了解决。但凡事都有两面性，插入删除操作虽然高效，但它在查找上的效率却不如数组方式，它无法访问任意位置的元素，也无法根据现在所处的位置（current指针处）去访问它前面的数据。对于这些不足，我们也提出一些解决方案，通过循环链表（将尾部的链接指向线性表的头部）或通过双向链表（元素中增加指针，指针指向直接前驱元素）。这样的链式存储多节省了操作的时间，但需要更多的存储空间。
　　堆栈：类似于线性表的链式存储，并且它的操作更为简单。这种存储相对于顺序存储，链式的堆栈基本上没有栈满的情况，存储如图6所示。
　　栈头是最后进入的数据，栈尾是先进入的数据。
　　队列：与前面类似，具体存储如图7所示。
　　3 应用举例
　　①线性表。一个数据表使用

过后，可能下次还会再次被使用。比如输入某汉字，首屏一般是常用汉字，那么就需要通过翻屏找到用户需要的汉字，一般使用过一次后，接下来很大几率再次使用它。汉字可以以链表中结点存储，而第一屏仅显示链表前面若干汉字，故要将之前使用过的汉字移动到第一结点的位置，提高汉字录入效率。这是根据结点的使用（潜在）概率来决定存放的位置，如果不能取得每个结点的潜在使用概率，可以采用前移一个位置的方法，使用越多，前移越多。
　　②堆栈。首先是背包问题，假设有一个能容纳总体积为t的背包，另有n个体积分别是w1，w2…wn个物品，现要在这几件物品中选出若干件物品恰好装满背包，求满足条件的所有解。然后采用尝试回逆法，从0号物品开始顺序选取物品，如果可以装入背包（装入后不满），则将该物品的编号进栈。如果当前选定的物品k装不进去（装入后体积大于t）选择下一个物品（k+1）尝试装入。如果尚未求得解，又已无物品可选，则说明上一个装入的物品不合适，将堆栈退出一个背包编号，再从这个退出的编号的下一个编号物品尝试。每求出一组解，输出结果，再退出栈顶数据，再从当前退出的编号的下一个标号物品尝试，直到堆栈为空（无退栈数据）且达到最大编号
　　③队列。以列车重排进行分析，一列货运列车共有 n 节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1～n，即货运列车按照第n站至第1站的次序经过这些车站。为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只需卸掉最后一节车厢。所以，给定任意次序的车厢，必须重新排列他们。假定重排n个车厢，可使用k个缓冲轨，将每个缓冲轨看成是一个队列，用nowout表示下一个输出至出轨的车厢编号。火车车厢重排的算法用伪代码描述如下：分别对k个队列初始化；初始化下一个有爱输出的车厢编号nowout=1；依次取入轨中的每一个车厢编号。如果入轨中的车厢编号等于nowout，则输出该车厢：nowout++。否则，考虑每一个缓冲轨队列：for（j=1;j<=k;j++），取队列j的对头元素c。如果c=nowout，则将队列j的对头元素出队并输出：nowout++。如果入轨和缓冲轨的对头元素没有编号为nowout的车厢，则求小雨入轨中第一个车厢编号的最大队尾元素所在队列编号j。如果j存在，则把入轨中的第一个车厢移至缓冲轨j；如果j不存在，但有多余一个空缓冲轨，则把入轨第一个车厢移至一个空缓冲轨；否则车厢无法重排，算法结束。
　　参考文献：
　　[1] 曹玉锋.数据结构中线性表、栈与队列[j].网络科技时代(数字冲浪),2002,(1).

本文链接：http://www.qk112.com/lwfw/guanlilunwen/glxlw/128831.html