下载掌阅APP，畅读海量书库
立即打开
栈的示意图如图3.1所示，栈中保存一个数据序列[ a 0 ， a 1 ，…， a n -1 ]，共有两个端点，栈底的一端（ a 0 端）不动，栈顶的一端（ a n -1 端）是动态的，可以插入（进栈）和删除（出栈）元素。栈元素遵循“先进后出”的原则，即最先进栈的元素最后出栈。注意，不能直接对栈中的元素进行顺序遍历。
图3.1 栈的示意图
在算法设计中，栈通常用于存储临时数据。在一般情况下，若先存储的元素后处理，则使用栈数据结构存储这些元素。
n
个不同的元素经过一个栈产生不同出栈序列的个数为
，这称为第
n
个Catalan（卡特兰）数。
栈可以使用数组和链表存储结构实现，使用数组实现的栈称为顺序栈，使用链表实现的栈称为链栈。
在C++STL中提供了stack类模板，实现了栈的基本运算，而且在使用时不必考虑栈满上溢出的情况，但不能顺序遍历栈中的元素。其主要的成员函数如下。
· empty（）：判断栈是否为空，当栈中没有元素时返回true，否则返回false。
· size（）：返回栈中当前元素的个数。
· top（）：返回栈顶的元素。
· push（x）：将元素 x 进栈。
· pop（）：出栈元素，只是删除栈顶元素，并不返回该元素。
例如，以下代码定义一个整数栈st，依次进栈1、2、3，再依次出栈所有元素，出栈结果是3，2，1。
C++：
另外，由于C++STL中的vector容器提供了empty（）、push_back（）、pop_back（）和back（）等成员函数，也可以将vector容器用作栈。
在Python中没有直接提供栈，可以将列表作为栈。当定义一个作为栈的st列表后，其主要的栈操作如下。
· st，len（st）==0：判断栈是否为空，当栈中没有元素时返回True，否则返回False。
· len（st）：返回栈中当前元素的个数。
· st[-1]：返回栈顶的元素。
· st.append（ x ）：将元素 x 进栈。
· st.pop（）：出栈元素，只是删除栈顶元素，并不返回该元素。
说明： 在Python中提供了双端队列deque，可以通过限制deque在同一端插入和删除将其作为栈使用。
例如，以下代码用列表st作为一个整数栈，依次进栈1、2、3，再依次出栈所有元素，出栈结果是3，2，1。
Python：
将一个从栈底元素到栈顶元素有序的栈称为单调栈，如果从栈底元素到栈顶元素是递增的（栈顶元素最大），称该栈为单调递增栈或者大顶栈，例如[1，2，3]（栈底为1，栈顶为3）就是一个单调递增栈；如果从栈底元素到栈顶元素是递减的（栈顶元素最小），称该栈为单调递减栈或者小顶栈，例如[3，2，1]就是一个单调递减栈。
维护单调栈的操作是在向栈中插入元素时可能需要出栈元素，以保持栈中元素的单调性。这里以单调递增栈（大顶栈）为例，假设要插入的元素是 x ：
（1）如果栈顶元素小于（或者等于） x ，说明插入 x 后仍然保持单调性。直接进栈 x 即可。
（2）如果栈顶元素大于 x ，说明插入 x 后不再满足单调性，需要出栈栈顶元素，直到栈为空或者满足（1）的条件，再将 x 进栈。
例如，以下代码中定义的单调栈st是一个单调递增栈，执行后st从栈底到栈顶的元素为[1，2，3]。
C++：
单调栈的主要用途是寻找下/上一个更大/更小元素，例如给定一个整数数组 a ，求每个元素的下一个更大元素，可以使用单调递减栈实现。由于在单调栈应用中通常每个元素仅进栈和出栈一次，所以时间复杂度为 O （ n ）。