栈

栈（stack）是限制插入和删除只能在一个位置上进行的有序表，该位置是表的末端，即最后插入的元素的位置，叫做栈的顶（top）。栈的修改是按先进后出的原则进行的，因此，栈又叫LIFO（Last In First Out）表。由于栈是一个表，因此任何实现表的方法都能实现栈，通常是用线性表，包括顺序表、链表、块状链表等。

操作

栈有三种基本操作：

进栈

在栈顶增加一个元素。

出栈

把栈顶元素删除。

取栈顶元素

在不删除的情况下得到栈顶元素的值。

另外很多实现可以完成一些其他的操作：

清空

清空一个栈。

求元素个数

判空

判断一个栈是否为空。

求栈顶开始的第k个元素

这种操作在有的线性表实现中无法保证复杂度。

相关的操作通常可以在其所用的表的结构中直接找到。

用链表实现的栈，由于不容易直接访问表的末端，通常用相反的顺序表示，即把链表首节点作为栈的顶。这时候栈的顶仍然是最后插入的元素。如果使用块状链表，链表本身和每个块内部也都是一个栈，其性质分别符合链表和顺序表实现的栈的性质。其中链表部分也用和链表一样的方法表示。

栈可以加入一些所用的表支持的其他的操作。但是加入其他修改操作之后通常就不会再被叫做栈了，例如可以访问和修改栈底的结构通常叫做双端队列。

栈的实现本身通常就是一个线性表。“栈”通常用来描述在具体操作中这个线性表表示的逻辑结构。

分析

在线性表中，由于关于栈的顶的操作都不会影响整个表的结构，所以基本操作都可以用O(1)的时间完成。

如果栈被储存在一块独立的内存中，往往可以用O(1)的时间清空，即重新初始化这个栈。这种情况通常发生在顺序表实现的栈，由于栈只会在最后插入的位置修改，用独立内存的链表实现栈是没什么意义的。但是如果只是多个链表实现的栈共享内存，快速的同时清空所有的栈也是可以的。不过也要分别重设所有的栈，或者清空内存，复杂度是O(栈的个数)。另外如果链表实现的栈存储在有独立的内存回收机制的部分，有时候也可以将这个链表直接整个合并到未分配内存的表中，对每个栈的复杂度也是O(1)。

有很多栈的实现并不需要储存元素个数。这时候需要另外储存元素的个数，求元素个数时才能达到O(1)的复杂度。对于判空，顺序表的实现通常有专门的标志记录（例如元素个数或者虚拟节点），而栈的这个操作类似于取栈顶元素（顺序表中作为保护，判空操作也经常会被取栈顶元素操作引用）。求第k个元素的操作依赖于所用表的结构的复杂度，顺序表是O(1)，链表是O(k)，块状链表是O(k/块大小)。作为纯栈的目的的实现，k通常不会很大，例如2或者3，这时候复杂度可以看作O(1)。

改进和优化

<showhide>

• 提高空间利用率 __HIDER__

<hide> 在一些问题中，可能需要同时使用多个同类型的栈。为了使每个栈在算法运行过程中不会溢出，要为每个栈顶置一个较大的栈空间。这样做往往造成空间的浪费。实际上，在有些算法的运行的过程中，各个栈不会同时满，经常会有的满而有的空。因此，如果我们让多个栈共享同一个数组，动态地互相调剂，将会提高空间的利用率，并减少发生栈上溢的可能性。 假设我们让程序中的两个栈共享一个数组S[1..n]。利用栈底位置不变的特性，我们可以将两个栈的栈底分别设在数组S的两端，然后各自向中间伸展，如图所示。这两个S栈的栈顶初值分别为0和n+1。只有当两个栈的栈顶相遇时才可能发生上溢。由于两个栈之间可以余缺互补，因此每个栈实际可用的最大空间往往大于n/2。

文件:Stack1.jpg </hide> </showhide>

实现

Pascal

C

C++ (#include <stack>)

应用

逆波兰表示

(Reverse Polish Notation, 简称RPN)

引用

• 《数据结构》，严蔚敏 吴伟民 著，清华大学出版社。
• 《C++数据结构导引》，(美）Larry R.Nyhoff 著，清华大学出版社。
• 《数据结构与算法分析》，(美）Mark Allen Weiss 著，机械工业出版社。