栈

在数据结构的学习中，我们已经掌握了数组和链表等线性结构，它们支持在任意位置进行插入和删除操作。现在，我们将探讨一种具有特定约束的线性数据结构——栈（Stack）。这种约束性并非缺陷，而是栈的核心特征，使其在特定场景下展现出卓越的性能和简洁性。

栈是一种遵循后进先出（Last-In, First-Out, LIFO）原则的抽象数据类型。在栈中，元素的插入和删除操作都只能在同一个端点进行，这个端点称为栈顶（Top）。与栈顶相对的另一端称为栈底（Bottom）。栈的这种特性可以形式化地定义为：对于任意元素序列，最后插入的元素将最先被移除。

从形式化角度来看，栈可以定义为一个有序对 (S, op)，其中 S 是元素的集合，op 是定义在 S 上的操作集合。栈的核心约束在于：所有修改操作（插入和删除）都必须在栈顶执行，这确保了元素访问顺序的严格性。这种设计使得栈在函数调用管理、表达式求值、回溯算法等场景中具有不可替代的作用。

栈的基本操作

栈作为抽象数据类型，定义了以下基本操作接口。每个操作都有明确的前置条件和后置条件，以及确定的时间复杂度。

• 推入（Push）：操作将一个元素添加到栈顶。该操作的前置条件是栈已初始化，后置条件是栈的大小增加1，新元素成为栈顶元素。推入操作的时间复杂度为 O(1)。
• 弹出（Pop）：操作移除并返回栈顶元素。该操作的前置条件是栈非空，后置条件是栈的大小减少1，原栈顶的下一个元素成为新的栈顶。如果对空栈执行弹出操作，将引发下溢（Underflow）异常。弹出操作的时间复杂度为 O(1)。
• 查看栈顶（Top 或 Peek）：操作返回栈顶元素的值，但不移除该元素。该操作的前置条件是栈非空，后置条件是栈的状态不变。查看操作的时间复杂度为 O(1)。
• 判空（isEmpty）：操作检查栈是否为空，返回布尔值。该操作的时间复杂度为 O(1)。
• 获取大小（Size）：操作返回栈中当前元素的数量。该操作的时间复杂度为 O(1)，具体实现取决于底层数据结构的选择。

下面的流程图展示了栈操作的基本执行序列，栈顶元素用 C 表示：

这些基本操作构成了栈的完整接口。虽然操作集合简单，但通过它们的组合可以解决许多复杂的计算问题。

栈实验室

栈的实现

栈作为抽象数据类型，可以通过多种底层数据结构实现。不同的实现方式在时间复杂度、空间复杂度、缓存性能等方面存在差异。下面我们探讨两种主要的实现方式。

基于动态数组的栈

使用动态数组（在C++中为 std::vector）实现栈是最常见且高效的方式。在这种实现中，我们将数组的末尾作为栈顶，利用数组的连续内存布局和高效的尾部操作。

• 内存布局特性：动态数组在内存中连续存储元素，这种布局具有优秀的空间局部性（Spatial Locality）。当CPU访问栈顶元素时，相邻元素很可能已经被加载到缓存中，从而显著提升访问速度。每个元素的内存地址可以通过基址加上索引偏移量直接计算得出，访问时间为 O(1)。
• 扩容机制与摊销分析：当数组容量不足时，std::vector 会执行扩容操作。典型的扩容策略是分配原容量两倍的新空间，然后将所有元素复制到新空间。虽然单次扩容的时间复杂度为 O(n)，但通过摊销分析（Amortized Analysis）可以证明，n 次推入操作的总时间复杂度为 O(n)，因此单次推入操作的摊销时间复杂度为 O(1)。
• 时间复杂度分析：基于动态数组的栈实现中，所有基本操作的时间复杂度如下：推入操作在最坏情况下为 O(n)（需要扩容），摊销时间复杂度为 O(1)；弹出操作为 O(1)；查看栈顶为 O(1)；判空和获取大小均为 O(1)。

让我们来看一个具体的C++实现：

|
#include <vector>
#include <stdexcept>
 
template <typename T>
class VectorStack {
private:
    // 使用 std::vector 作为底层容器
    // vector 的末尾索引对应栈顶位置
    // 这种设计充分利用了连续内存的缓存优势
    std::vector<T> elements;
 
public:
    // 推入操作：将元素添加到栈顶
    // 时间复杂度：摊销 O(1)，最坏情况 O(n)（扩容时）
    void push(const T& item) {
        // vector::push_back 在末尾添加元素
        // 利用连续内存布局，访问效率高

基于链表的栈

链表实现栈的方式是将链表的头部作为栈顶。每次推入操作在链表头部插入新节点，弹出操作删除头部节点。这种实现方式的所有操作都保证在严格的 O(1) 时间内完成，不存在性能波动。

• 内存分配特性：链表节点通过动态内存分配创建，每个节点在堆内存中独立存在。节点之间通过指针连接，内存布局是非连续的。每个节点除了存储数据外，还需要额外的指针空间（在64位系统上通常为8字节）。
• 内存开销分析：假设存储类型 T 的大小为 sizeof(T)，每个节点需要 sizeof(T) + sizeof(Node*) 的内存空间。对于小数据类型（如 int），指针开销可能占比较大比例。此外，动态分配可能导致内存碎片化，降低内存利用率。
• 缓存性能：由于节点在内存中非连续分布，访问模式缺乏空间局部性。当访问栈顶节点时，下一个节点很可能不在同一缓存行中，需要额外的内存访问。这种跳跃式访问模式对CPU缓存不友好，实际运行速度通常低于数组实现。

|
#include <stdexcept>
 
// 链表节点结构体
template <typename T>
struct Node {
    T data;                    // 节点存储的数据
    Node* next;                // 指向下一个节点的指针
 
    // 构造函数：初始化节点数据，next 指针设为 nullptr
    Node(const T& data) : data(data), next(nullptr) {}
};
 
template <typename T>

实现方式对比与选择

两种实现方式在多个维度上存在显著差异，选择时需要根据具体应用场景进行权衡。

• 时间复杂度对比：基于动态数组的实现中，推入操作的摊销时间复杂度为 O(1)，但在扩容时会出现 O(n) 的峰值。基于链表的实现中，所有操作都严格保证 O(1) 时间复杂度，不存在性能波动。
• 空间复杂度分析：动态数组实现的空间复杂度为 O(n)，其中 n 为元素数量。由于扩容策略，实际分配的空间可能略大于 n，但空间利用率通常较高。链表实现的空间复杂度也为 O(n)，但每个节点需要额外的指针开销，且可能存在内存碎片，实际空间利用率较低。
• 缓存性能差异：动态数组的连续内存布局具有优秀的缓存局部性。当访问栈顶元素时，相邻元素很可能在同一缓存行中，减少了缓存未命中的概率。链表的非连续内存布局导致缓存性能较差，每次访问都可能触发缓存未命中，需要从主内存加载数据。
• 适用场景：对于大多数应用场景，基于动态数组的实现是首选。它在平均情况下具有更好的性能，且实现简单。C++ 标准库中的 std::stack 默认使用 std::deque 作为底层容器，这是一种结合了数组和链表优点的数据结构。只有在需要严格保证每次操作都是 O(1) 且对性能波动极其敏感的场景（如实时系统、嵌入式系统）中，才考虑使用链表实现。
• 标准库使用：在实际开发中，推荐直接使用 C++ 标准库提供的 std::stack，它已经过充分优化和测试。std::stack 是一个容器适配器，默认使用 std::deque 作为底层容器，也可以指定使用 std::vector 或 std::list。

|
#include <stack>
#include <vector>
 
// 使用默认底层容器（std::deque）
std::stack<int> defaultStack;
 
// 指定使用 std::vector 作为底层容器
std::stack<int, std::vector<int>> vectorStack;
 
// 基本操作示例
vectorStack.push(10);
vectorStack.push(20);
int topValue = vectorStack.top();  // 20
vectorStack.

栈的应用

栈的 LIFO 特性使其在计算机科学的多个领域具有重要应用。下面我们探讨几个典型的应用场景。

函数调用与调用栈

在程序执行过程中，函数调用和返回的管理依赖于调用栈（Call Stack） 机制。调用栈是栈数据结构在运行时系统中的应用，用于维护函数调用的执行上下文。

栈帧（Stack Frame） 是调用栈中的基本单元，也称为活动记录（Activation Record）。每个栈帧包含以下信息：局部变量、函数参数、返回地址、调用者的栈帧指针、以及可能的临时计算结果。当函数被调用时，系统为其创建一个新的栈帧并推入调用栈；当函数返回时，对应的栈帧被弹出，控制权返回到调用者。

调用序列示例：假设 main 函数调用 functionA，functionA 又调用 functionB。调用栈的状态变化如下：首先 main 的栈帧被推入；然后 functionA 的栈帧被推入，位于 main 之上；接着 functionB 的栈帧被推入，位于栈顶。当 functionB 执行完毕返回时，其栈帧被弹出，控制权回到 functionA；functionA 返回时，其栈帧被弹出，控制权回到 main。

栈溢出（Stack Overflow）：调用栈的大小是有限的，通常由操作系统或编译器设置。当递归深度过大或局部变量占用空间过多时，可能耗尽栈空间，导致栈溢出错误。这是无限递归或深度递归算法中常见的问题。

后缀表达式求值

后缀表达式（Postfix Notation），也称为逆波兰表示法（Reverse Polish Notation），是一种不需要括号的数学表达式表示方法。在后缀表达式中，运算符位于其操作数之后。例如，中缀表达式 (3 + 4) * 5 对应的后缀表达式为 3 4 + 5 *。

算法描述：后缀表达式求值算法使用栈作为辅助数据结构。算法从左到右扫描表达式，遇到操作数时将其推入栈，遇到运算符时从栈中弹出所需数量的操作数，执行运算后将结果推入栈。算法的时间复杂度为 O(n)，其中 n 为表达式长度，空间复杂度为 O(n)。

执行过程示例：对于后缀表达式 3 4 + 5 *，执行过程如下：扫描到 3，推入栈，栈状态为 [3]；扫描到 4，推入栈，栈状态为 [3, 4]；扫描到 +，弹出 4 和 3，计算 3 + 4 = 7，将 7 推入栈，栈状态为 [7]；扫描到 5，推入栈，栈状态为 [7, 5]；扫描到 *，弹出 5 和 7，计算 7 * 5 = 35，将 35 推入栈，栈状态为 [35]。表达式扫描完毕，栈顶元素 35 即为最终结果。

中缀转后缀算法：将中缀表达式转换为后缀表达式同样可以使用栈实现。算法维护一个运算符栈，根据运算符优先级和结合性规则处理运算符。该算法的时间复杂度为 O(n)，空间复杂度为 O(n)。

括号匹配

括号匹配是栈的经典应用之一。给定一个包含多种括号（圆括号、方括号、花括号）的字符串，判断其中的括号是否匹配。算法使用栈存储未匹配的左括号，遇到右括号时检查栈顶是否是对应的左括号。算法的时间复杂度和空间复杂度均为 O(n)，其中 n 为字符串长度。

深度优先搜索

在图的遍历算法中，深度优先搜索（Depth-First Search, DFS） 可以使用栈来实现。算法从起始顶点开始，将未访问的相邻顶点推入栈，然后从栈中弹出顶点进行访问，重复此过程直到栈为空。使用栈实现的 DFS 与递归实现等价，但提供了更明确的控制流程。

复杂度分析总结

下表总结了基于不同底层数据结构的栈操作的时间复杂度：

空间复杂度方面，两种实现均为 O(n)，其中 n 为栈中元素数量。动态数组实现的空间利用率通常更高，而链表实现存在指针开销和内存碎片问题。

小练习

4. 栈操作序列追踪练习

给定一个初始状态为空的栈，执行以下操作序列：push(10), push(20), top(), push(30), pop(), pop(), push(40), isEmpty(), pop(), pop(), isEmpty(), pop()。

请完整追踪整个操作序列的执行过程，并回答：

• 每次调用 top() 操作时，返回的元素值是什么？
• 每次执行 pop() 操作后，栈的内部状态如何变化？
• 每次调用 isEmpty() 操作时，返回值是 true 还是 false？
• 最后一次 pop() 操作会产生什么结果？

|
#include <iostream>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
using namespace std;
 
// 辅助函数：打印栈的内容（从栈顶到栈底）
string stackToString(stack<int> s)
{
    if (s.empty()) return "[]";
    
    vector<int> vec;
    while

5. 最小栈数据结构设计练习

设计并实现一个扩展的栈数据结构，在支持标准栈操作（push(x)、pop()、top()）的基础上，额外提供 getMin() 操作，该操作需要在 O(1) 时间复杂度内返回栈中的最小元素。

要求：所有操作（push、pop、top、getMin）的时间复杂度均为 O(1)。

|
#include <iostream>
#include <stack>
#include <stdexcept>
using namespace std;
 
class MinStack
{
private:
    // 主栈：存储所有元素
    stack<int> mainStack;
    // 辅助栈：存储每个状态下的最小值
    // 辅助栈的栈顶元素始终等于主栈当前状态下的最小值
    stack<int> minStack;
 
public:
    MinStack()
    {
        // 栈会自动初始化
    }
 
    // 入栈操作 - O(1)
    void push

6. 每日温度问题练习

给定一个整数数组 temperatures，其中 temperatures[i] 表示第 i 天的温度值。对于数组中的每个元素，计算需要等待多少天才能遇到一个更高的温度值。如果之后没有更高的温度，则结果为 0。

要求：返回一个整数数组 result，其中 result[i] 表示第 i 天需要等待的天数。使用单调栈方法解决，时间复杂度为 O(n)。

|
#include <iostream>
#include <vector>
#include <stack>
#include <sstream>
using namespace std;
 
// 辅助函数：打印数组
string arrayToString(const vector<int>& arr)
{
    if (arr.empty()) return "[]";
    stringstream ss;
    ss << "[";
    for

说明：

• top() 操作：返回栈顶元素 20，不改变栈的状态
• pop() 操作：依次弹出 30, 20, 40, 10，每次弹出后栈的状态都会改变
• isEmpty() 操作：
  • 第一次调用时栈中有元素，返回 False
  • 第二次调用时栈为空，返回 True
• 最后一次 pop()：当栈为空时执行 pop() 会抛出 InvalidOperationException 异常
• 栈的 LIFO 特性：最后入栈的元素（30）最先出栈，体现了后进先出的特性

说明：

• 设计思路：使用辅助栈存储每个状态下的最小值
• Push 操作：
  • 将元素推入主栈
  • 如果辅助栈为空或新元素 ≤ 辅助栈栈顶，将新元素也推入辅助栈
• Pop 操作：
  • 如果主栈栈顶等于辅助栈栈顶（即当前最小值），同时弹出辅助栈
  • 弹出主栈栈顶
• GetMin 操作：直接返回辅助栈栈顶，时间复杂度 O(1)
• 时间复杂度：所有操作均为 O(1)
• 空间复杂度：O(n)，辅助栈在最坏情况下需要存储 n 个元素

说明：

• 单调栈方法：使用单调递减栈存储索引，栈中索引对应的温度值保持单调递减
• 算法步骤：
  1. 初始化结果数组，所有元素设为 0
  2. 从左到右遍历温度数组
  3. 当栈非空且当前温度大于栈顶索引对应的温度时：
     • 弹出栈顶索引 j
     • 计算 result[j] = i - j
  4. 将当前索引推入栈
• 时间复杂度：O(n)，每个索引最多被推入和弹出栈各一次
• 空间复杂度：O(n)，最坏情况下所有索引都在栈中
• 关键思想：单调栈保证了当我们处理索引 i 时，栈中存储的是所有尚未找到下一个更高温度的索引