[大话数据结构-读书笔记] 栈

栈

1 栈的定义

1.1 栈的定义

在我们软件应用中，栈这种后进先出数据结构的应用是非常普遍的。比如Word、 Photoshop 等文档或图像编辑软件中， 都有撤销

(undo)的操作，也是用栈这种方式来实现的。

我们把允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)，不含任何数据元素的栈称为空栈。栈又称为后进先出（Last In Filrst Out) 的线性表，简称LlFO结构。

理解栈的定义需要注意：

首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。它的特殊之处就在于限制了这个线性表的插入和删除位置，它始终只在栈顶进行。这也就使得栈底是固定的，最先进栈的只能在栈底。

栈的插入操作，叫作进栈，也称压栈、入栈。类似子弹入弹夹，如下图-左所示。栈的删除操作，叫作出栈，也有的叫作弹栈。

1.2 进栈出栈变化方式

现在我要问问大家，这个最先进栈的元素，是不是就只能是最后出栈呢?

答案是不一定，要看什么情况。栈对线性表的插入和删除的位置进行了限制，并没有对元素进出的时间进行限制，也就是说，在不是所有元素都进栈的情况下，事先进去的元素也可以出栈，只要保证是栈顶元素出栈就可以。

举例来说，如果我们现在是有3个整型数字元素1、2、3依次进栈，会有哪些出栈次序呢？

第一种：1、2、3进，再3、2、1出。这是最简单的最好理解的一种，出栈次序为321。第二种：1进，1出，2进，2出，3进，3出。也就是进一个就出一个，出 栈次序为123。第三种：1进，2进，2出，1出，3进，3出。出栈次序为213。第四种：1进，1出，2进，3进，3出，2出。出栈次序为132。第五种：1进，2进，2出，3进，3出，1出。出栈次序为231。

有没有可能是312这样的次序出栈呢？答案是肯定不会。因为3先出栈，就意味着，3曾经进栈，既然3都进栈了，那也就意味着，1和2已经进栈了，此时，2—定是在1的上面，就是更接近栈顶，那么出栈只可能是321,不然不满足123依次进栈的要求，所以此时不会发生1比2先出栈的情况。

2 栈的抽象数据类型

对于栈来讲，理论上线性表的操作特性它都具备，可由于它的特殊性，所以对它在操作上会有些变化，特别是插入和删除操作，我们改名为push和pop，不过一般叫进栈和出栈。

3 栈的顺序存储结构及实现

栈的顺序存储结构，简称为顺序栈。

由于篇幅原因，顺序栈的实现程序不在这里贴出，详细请看我的另一篇博客：数据结构 - 顺序栈的实行（C语言）。

4 栈的链式存储结构及实现

栈的链式存储结构，简称为链栈。

由于篇幅原因，链栈的实现程序不在这里贴出，详细请看我的另一篇博客：数据结构 - 链栈的实行（C语言）。

5 顺序栈与链栈的区别

两者在时间复杂度上是一样的，均为O(1)。对于空间性能，顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，但它的优势是存取时定位很方便，而链栈则要求每个元素都有指针域，这同时也增加了一些内存开销，但对于栈的长度无限制。所以它们的区别和线性表中讨论的一样，如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。