栈（Stack）

栈（Stack）是一种特殊的线性表，它只能在表尾进行插入和删除操作，这一端被称为栈顶（Top），另一端被称为栈底（Bottom）。栈中元素的插入和删除操作，称为入栈（Push）和出栈（Pop）。

栈最核心的性质是后进先出（LIFO，Last In First Out）：最后放进去的元素，最先被取出来。可以把它想象成一摞盘子，你只能从最上面放盘子，也只能从最上面取盘子；想拿最底下那只，必须先把上面的都搬走。

栈的操作

非常简单的两种操作，入栈和出栈。将元素放到栈顶，或者从栈顶取下元素。

除了这两个核心操作，栈通常还提供几个辅助操作：

操作	含义
Push	入栈，把一个元素放到栈顶
Pop	出栈，取出并移除栈顶元素
Peek / Top	查看栈顶元素，但不移除它
isEmpty	判断栈是否为空
Size	返回栈中元素个数

由于所有操作都只发生在栈顶，不涉及元素搬移，入栈和出栈的时间复杂度都是 O(1)。

这里有一个必须小心的细节：对空栈执行 Pop 或 Peek 是非法的，会导致下溢（Underflow）；如果栈的容量固定（比如用定长数组实现），入栈超过容量则会上溢（Overflow）。实际实现中，这两种情况都需要检查并处理。

栈的实现

栈是一种抽象的逻辑结构，它并不规定底层怎么存，常见的实现有两种。

用数组实现

用一个 数组 加一个记录栈顶位置的下标 top 即可。入栈就是 arr[++top] = x，出栈就是 return arr[top--]。

class Stack {
    int data[N];
    int top = -1;   // -1 表示空栈
public:
    void push(int x) { data[++top] = x; }
    int  pop()       { return data[top--]; }
    int  peek()      { return data[top]; }
    bool empty()     { return top == -1; }
};

数组实现的优点是内存连续、常数小、缓存友好；缺点是容量往往需要预先确定，或者在写满时进行扩容（成倍扩容可以让均摊复杂度仍为 O(1)）。

用链表实现

用 链表 实现时，把链表头当作栈顶：入栈就是头插，出栈就是删头节点。这样天然没有容量上限，缺点是每个节点都要额外存一个指针，且节点分散在内存各处，缓存不如数组友好。

无论用哪种方式，对使用者来说，栈暴露的都只是 push / pop / peek 这几个接口——这正是抽象数据类型的意义：逻辑行为固定，底层实现可换。

栈的应用

栈虽然操作简单，却是计算机系统中最重要的结构之一。

• 函数调用栈：程序运行时，每次函数调用都会把返回地址、参数、局部变量打包成一个**栈帧（Stack Frame）**压入调用栈，函数返回时再弹出。递归能够正确回溯，靠的就是这套后进先出的机制。相关内容可参考 运行时内存布局。
• 表达式求值与括号匹配：编译器在处理表达式、检查括号是否配对时，常用栈来暂存运算符或左括号。遇到右括号就弹栈匹配，一旦对不上就说明括号非法。
• 表达式转换：中缀表达式转后缀（逆波兰）表达式、后缀表达式求值，都是栈的经典用途。
• 撤销（Undo）操作：编辑器把每一步操作压栈，按下撤销时弹出最近一步，正是 LIFO 的直观体现。
• 深度优先遍历：无论是树还是图，深度优先都依赖栈来记录“还没走完的分支”。

深度遍历时栈的变化

树 和 图 的深度优先遍历（DFS），本质就是一个不断压栈、弹栈的过程。它的思路是“一条路走到黑”：沿着某个分支尽量往深处走，走不动了再回退到上一个岔路口，尝试另一条没走过的路。

以遍历一棵树为例，用栈来实现的过程大致是：

1. 把根节点压入栈。
2. 从栈顶弹出一个节点，访问它。
3. 把它尚未访问的子节点依次压入栈。
4. 重复第 2、3 步，直到栈为空。

因为后压入的节点会先被弹出，所以遍历会优先深入最近压入的那个分支——这正好实现了“深度优先”。

举个例子，假设有这样一棵树：

        A
       / \
      B   C
     / \
    D   E

若每次先压右孩子、再压左孩子（保证左孩子先被弹出），栈的变化过程如下：

步骤	动作	栈内容（栈顶在右）	已访问
1	压入 A	[A]
2	弹出 A，压入 C、B	[C, B]	A
3	弹出 B，压入 E、D	[C, E, D]	A B
4	弹出 D（叶子）	[C, E]	A B D
5	弹出 E（叶子）	[C]	A B D E
6	弹出 C（叶子）	[]	A B D E C

最终访问顺序是 A B D E C，正是这棵树的前序遍历结果。

值得一提的是，递归写法看似没有显式用到栈，实际上是借用了函数调用栈：每次递归调用相当于一次入栈，函数返回相当于一次出栈。所以递归版 DFS 和显式用栈的迭代版 DFS，底层是同一回事——只是一个用系统的栈，一个用你自己维护的栈。当递归层数过深时会导致栈溢出（Stack Overflow），此时改用显式栈的迭代写法，往往能规避这个问题。