从线性表谈到栈与队列

从线性表谈到栈与队列

摘 要：数据结构是计算机中一个非常重要的分支，它是现实世界数据与计算机世界数据连接的关键，它主要涵盖两方面的内容：逻辑层面的数据结构及计算机存储数据物理层的数据结构。关于数据结构中的线性表、栈、队列，文章将上述两方面的内容进行介绍，进行横向的比较，从而更清楚地看到它们之间的联系与区别。并分析它们在现实计算中的应用。

关键词：线性表；堆栈；队列 1 逻辑关系

①线性表。线性表是有限元素（a1,a2,a3…，an ）有序序列的集合，a1,a2…，an 都是完全相同结构的数据类型，同时它们之间的排列严格有序，其中任何元素都对应唯一的前驱以及唯一的后继。这样一个序列可以有查询、删除、插入队列任何位置的数据操作。

②堆栈。堆栈也是一个有序序列的集合，结构上与线性表规定一样。但它的运算受到严格的限制（故也叫限定性线性表）。这个序列中我们只能从一端取出放入数据，即压入栈和弹出栈，所以它的顺序是“先进先出”，如图1所示。

③队列。队列与栈类似，属于限定性线性表，它的操作不同的地方是两端存、取数据，且仅仅是一端取（队头）一端（队尾），所以它的数据是“先入先出”。

2 物理结构

2.1 顺序结构

{1}线性表。用一定大小的数据来存放线性表，数组长度代表线性表的长度，元素在数组的位置代表元素在线性表的位置。但对数组中元素不能跳跃插入，因为线性表中元素是顺序且连接着的，不像数组中间可以空元素。同时删除元素时，必须大量移动剩下的元素，因为必须实现其连续性。插入元素同样需要大量移动数据。因此这样存储的运行效率并不够高。所以对于有着频繁插入和删除运算的线性表，是不适合采用顺序存储的。

{2}堆栈。类似于线性表，利用数组存储，只从这个数组的一端插入和删除数据，不存在从中间“挖”数据，故不存在大量数据移动的问题，唯一不足的是数组大小是有限的，会存在栈满的现象。如果数组大小定义过大，则又有大量存储空间没有被利用，会有资源浪费。

{3}队列。初始存储类似于线性表，但由于只能从一边进入另一边出，所以数据会随着数据操作而不断“前进”，使队列像一条“蠕虫”一样慢慢“爬过”队列定义的全部空间，而且“爬过”的空间就无法再次得到运用。“蠕虫”爬到数组尽头之后则无法前进，而此时很可能数组前端还有大量的数据未得到使用。因此我们将一个数组看作是“相连”的，即将整个数组看做一个环形，而队列“蠕虫”则会在这个环形轨道中持续“爬动”，直到数据装满整个数据空间。但这里还有第二个问题，这样的定义之后队列空与满，指向队头的front 与指向队尾的rear 所处的相对位置是完全一样的，如图2、图3所示。

这样一个类似于“活塞”的工具，它总是紧邻队列中第一个数据元素，是可以移动的，但它本身不存放任何数据。同时将队头指针指向这个“活塞”，那么队空与队满的冲突情况就得以避免，如图4、图5所示。

2.2 链 式

由于数组的静态分配、不易扩充、插入删除会有大量数据移动等种种局限性，我们引入链式存储方式。通过动态分配存储空间，最有效地利用空间。