CC++ & Algorithm

栈的概念与实现——像叠盘子一样存放数据

中等4
语言版本：通用
概述：栈是一种“后进先出”的数据结构，就像一摞盘子，后放上去的盘子先被拿走。本文用生活例子讲解栈的原理，并给出C++和Python的完整实现。

栈的概念与实现——像叠盘子一样存放数据

栈是什么？用来干什么？

栈（Stack）是一种后进先出（Last In First Out，简称LIFO）的数据结构。你可以把它想象成一摞盘子：你总是把新洗好的盘子放在最上面，拿盘子时也总是先拿走最上面的那一个。栈只允许在一端（称为栈顶）进行插入和删除操作，另一端（称为栈底）是封闭的。这种简单的规则却有着非常广泛的应用，比如程序中的函数调用、浏览器后退按钮、撤销操作、括号匹配、表达式求值等等。学会栈，你就掌握了一种组织数据的基本方法。

生活中的例子：从叠盘子到代码撤销

叠盘子

食堂阿姨叠盘子的场景是最经典的例子。假设有三个盘子依次叠放：第一个放上去，然后第二个，第三个。现在你要拿一个盘子，只能拿到最上面的第三个。如果先拿掉第三个，第二个就露出来了，再拿第二个……这就是后进先出。

撤销操作

在写作文或者画图时，你每点击一次“撤销”（Undo），程序就会撤销最近的一次操作。比如你先输入“Hello”，再输入“World”，最后输入“!”。点击撤销会删除“!”，再点击撤销会删除“World”。这背后就是一个栈：每次操作压入栈，撤销时从栈顶弹出。

浏览器后退按钮

当你浏览网页时，每点开一个新的链接，浏览器就把这个页面地址压入一个“前进-后退”栈。点击“后退”按钮，当前页面出栈，回到上一个页面。这就是栈的典型应用。

游戏中的技能释放

很多游戏里，释放技能的顺序会影响后续连招。比如你按顺序按下技能A、B、C，游戏角色会依次释放C、B、A（如果设计成栈的话）。虽然实际游戏更复杂，但栈的思想随处可见。

生活中的其他例子

  • 超市里最后一包零食被最先买走（如果顾客是后放上去的）。
  • 停车场里最后进来的车往往最先出去（假设是死胡同式停车场）。
  • 老师批改试卷，先交的卷子压在最下面，后交的在上面，批改时从上往下拿。

栈的原理与核心操作

栈的操作非常简单，所有动作都发生在栈顶。下面用一个表格来总结：

操作英文名说明生活中的比喻
入栈Push把一个新元素放到栈顶在盘子堆上叠一个新盘子
出栈Pop移除栈顶元素（不返回它的值，或者可以返回值）拿走最上面的盘子
查看栈顶Top / Peek只看一眼最上面的盘子，不拿走瞄一眼最上面的盘子
判空IsEmpty判断栈里有没有元素看看盘子堆是不是空的
获取大小Size数一数栈里有多少个元素数数一共有几个盘子

后进先出的本质

栈的核心特性就是“后进先出”。这意味着最后一个进入栈的元素总是第一个被取出。这个特性非常适合处理具有“嵌套”或“递归”关系的问题。例如：

  • 函数调用：程序调用函数时，系统会把函数的返回地址和局部变量压入调用栈，函数执行完毕后再弹出。这就是为什么函数可以嵌套调用，并且总能正确返回。
  • 括号匹配：检查表达式 ((a+b)*(c-d)) 中的括号是否成对。遇到左括号就入栈，遇到右括号就从栈顶弹出一个左括号，如果最后栈为空则匹配成功。
  • 逆序输出：把一组数据依次入栈，再依次出栈，就得到了逆序顺序。
  • 深度优先搜索 (DFS)：在图或树中遍历时，使用栈来记录路径，回头探索分支。

时间复杂度

所有基本操作（Push、Pop、Top、IsEmpty、Size）的时间复杂度都是 O(1)，也就是常数时间，不管栈里有多少元素，操作速度都一样快。这一点非常重要，因为很多算法依靠栈的快速操作来提升效率。

栈的实现方式：数组 vs 链表

栈可以用两种底层数据结构来实现：

  1. 数组实现：用一个数组（静态或动态）和一个“栈顶指针”（整数下标）来模拟。优点是访问速度快、内存紧凑；缺点是如果使用静态数组，大小固定（可用动态数组解决）。
  2. 链表实现：用链表，每次插入和删除都在链表头部进行，天然符合栈的LIFO。优点是不受固定大小限制；缺点是需要额外的指针存储，占用更多内存。

在竞赛和实际开发中，数组实现更常用，因为简单高效。下面我们分别给出C++和Python的完整实现，并且代码中每一行变量定义都加上中文注释，方便理解。

C++完整代码实现（数组方式 + 动态扩容）

下面的C++代码定义了一个Stack类，内部使用动态数组，并且支持自动扩容（当栈满时容量翻倍）。每个成员函数的用途都写在注释里。

#include <iostream>
using namespace std;

class Stack {
private:
    int* data;          // 指向动态数组的指针，存储栈元素
    int capacity;       // 栈的当前容量（最多能容纳的元素数）
    int topIndex;       // 栈顶元素的下标，-1表示空栈

public:
    // 构造函数：初始化一个容量为size的空栈
    Stack(int size = 10) {
        capacity = size;
        data = new int[capacity];   // 动态分配数组内存
        topIndex = -1;              // 初始时栈是空的
    }

    // 析构函数：释放动态分配的内存，防止内存泄漏
    ~Stack() {
        delete[] data;
    }

    // 入栈操作：将元素x压入栈顶
    void push(int x) {
        // 如果栈已满，就扩容为原来的两倍
        if (topIndex == capacity - 1) {
            resize(capacity * 2);
        }
        data[++topIndex] = x;   // 先移动栈顶指针，再存入元素
    }

    // 出栈操作：移除栈顶元素（不返回它）
    void pop() {
        if (isEmpty()) {
            cout << "错误：栈为空，不能出栈！" << endl;
            return;
        }
        topIndex--;   // 栈顶指针下移，逻辑上删除了元素
    }

    // 获取栈顶元素（不删除）
    int top() {
        if (isEmpty()) {
            cout << "错误：栈为空，没有栈顶元素！" << endl;
            return -1;  // 返回一个特殊值，更好的做法是抛出异常
        }
        return data[topIndex];
    }

    // 判断栈是否为空
    bool isEmpty() {
        return topIndex == -1;
    }

    // 获取栈中元素个数
    int size() {
        return topIndex + 1;
    }

private:
    // 内部函数：调整栈的容量（重新分配更大的内存）
    void resize(int newCapacity) {
        int* newData = new int[newCapacity];
        // 将旧数据复制到新数组中
        for (int i = 0; i <= topIndex; i++) {
            newData[i] = data[i];
        }
        delete[] data;          // 释放旧的内存
        data = newData;         // 指向新的数组
        capacity = newCapacity; // 更新容量
    }
};

// 测试代码
int main() {
    Stack s;  // 创建一个默认容量为10的栈

    // 入栈3个元素
    s.push(10);
    s.push(20);
    s.push(30);

    cout << "栈顶元素: " << s.top() << endl; // 输出30
    s.pop();                                  // 弹出30
    cout << "弹出后栈顶元素: " << s.top() << endl; // 输出20
    cout << "栈的大小: " << s.size() << endl;      // 输出2

    // 再入栈一个元素
    s.push(40);
    cout << "栈是否为空? " << (s.isEmpty() ? "是" : "否") << endl; // 否

    // 依次弹出所有元素（出栈并输出）
    while (!s.isEmpty()) {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;  // 输出 40 20

    return 0;
}

C++代码要点解释

  • data是一个动态数组，capacity记录数组容量，topIndex始终指向栈顶元素（-1表示空）。
  • push：先检查是否已满，是则调用resize扩容；然后++topIndex，再赋值。注意顺序不能反。
  • pop：只需topIndex--，原数据不必清除（后续入栈会覆盖）。
  • top：返回data[topIndex]，必须先判空。
  • resize：重新分配更大的数组，复制旧数据，释放旧内存。这里简单扩容为两倍。

新手容易犯的错误（C++）

  1. 忘记判空：在pop和top之前不检查isEmpty()，如果栈为空，topIndex是-1，访问data[-1]会导致严重错误（越界）。
  2. 入栈时忘记扩容：如果栈满了还继续push，数组下标会越界。必须提前检测并处理。
  3. 析构函数忘记释放内存：如果Stack对象被销毁时没有delete[] data，会造成内存泄漏。
  4. 混淆栈顶指针的初始值：有时初学者把topIndex初始化为0，但这样空栈时指向位置0是不对的，因为栈中还没有元素。常见做法是初始化为-1。

Python完整代码实现

Python的列表（list）本身就是一个动态数组，支持在末尾添加（append）和删除（pop），恰好符合栈的LIFO特性。我们可以直接使用列表来模拟栈，但为了清晰展示栈的抽象概念，我们封装一个简单的Stack类。

class Stack:
    """用Python列表实现的栈类"""
    def __init__(self):
        # 初始化一个空列表作为栈的底层存储
        self.items = []

    def push(self, item):
        """入栈：将元素添加到列表末尾（栈顶）"""
        self.items.append(item)

    def pop(self):
        """出栈：移除并返回栈顶元素（列表最后一个元素）"""
        if self.is_empty():
            raise IndexError("错误：从空栈中出栈！")
        return self.items.pop()

    def top(self):
        """返回栈顶元素但不删除它"""
        if self.is_empty():
            raise IndexError("错误：空栈没有栈顶元素！")
        return self.items[-1]  # 列表的最后一个元素

    def is_empty(self):
        """判断栈是否为空"""
        return len(self.items) == 0

    def size(self):
        """返回栈中元素个数"""
        return len(self.items)

# 测试代码
if __name__ == "__main__":
    s = Stack()

    # 入栈3个元素
    s.push(10)
    s.push(20)
    s.push(30)

    print("栈顶元素:", s.top())      # 输出30
    s.pop()                          # 弹出30
    print("弹出后栈顶元素:", s.top()) # 输出20
    print("栈的大小:", s.size())      # 输出2

    # 再入栈一个元素
    s.push(40)
    print("栈是否为空?", s.is_empty()) # 输出False

    # 依次弹出所有元素
    while not s.is_empty():
        print(s.pop(), end=" ")       # 输出 40 20
    print()

Python代码要点解释

  • self.items是一个列表，push调用append在末尾添加元素，pop调用列表的pop()移除末尾元素。
  • top利用列表索引-1直接获取最后一个元素，不改变列表。
  • 判空和大小计算都很直观。
  • 注意：我们在pop和top中使用了raise IndexError来抛出异常，而不是简单地打印错误。这样更符合Python的规范，调用方可以捕获异常进行处理。

新手容易犯的错误（Python）

  1. 忘记判空：直接调用pop()或top()可能会引发IndexError（因为空列表pop()也会报错）。但为了明确语义，最好还是手动检查。
  2. 混淆append和insert：有些人可能想用insert(0, item)在列表头部插入，但这样不是栈操作（变成了队列），而且效率很低。
  3. 误解出栈的顺序：栈是后进先出，所以pop总是弹出最后加入的元素，不是第一个。

完整示例：用栈实现括号匹配

括号匹配是栈的经典应用，也经常出现在编程题目中。比如判断一个表达式中的括号是否成对且正确嵌套：({[]})合法，([)]不合法。我们可以用栈来解决：

  • 遍历字符串中的每个字符。
  • 如果是左括号（(, [, {），将其入栈。
  • 如果是右括号（), ], }），先检查栈是否为空：空则说明没有对应的左括号，匹配失败；非空则弹出栈顶元素，检查是否与当前右括号匹配。
  • 遍历结束后，如果栈为空，则所有括号匹配成功；否则有左括号未被闭合。

下面给出Python和C++两种语言的完整实现。

Python实现：括号匹配

def is_valid_brackets(expr: str) -> bool:
    """检查表达式expr中的括号是否匹配，返回True或False"""
    # 使用列表作为栈
    stack = []
    # 定义括号配对映射：右括号 -> 左括号
    pairs = {')': '(', ']': '[', '}': '{'}

    for ch in expr:
        # 如果是左括号，入栈
        if ch in '([{':
            stack.append(ch)
        # 如果是右括号
        elif ch in ')]}':
            # 栈为空或栈顶不是对应的左括号，匹配失败
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()   # 匹配成功，弹出左括号

    # 遍历结束后，栈应为空
    return len(stack) == 0

# 测试
test_cases = [
    "()",          # 合法
    "({[]})",      # 合法
    "([)]",        # 不合法
    "((())",       # 不合法
    "({})",        # 合法
    "{[}",         # 不合法
]

for expr in test_cases:
    result = is_valid_brackets(expr)
    print(f"{expr:15} -> {'合法' if result else '不合法'}")

C++实现：括号匹配

#include <iostream>
#include <stack>   // 使用STL中的stack，省去自己写栈的麻烦
#include <string>
using namespace std;

// 检查括号是否匹配
bool isValidBrackets(const string& expr) {
    stack<char> st;   // 存放左括号的栈

    for (char ch : expr) {
        if (ch == '(' || ch == '[' || ch == '{') {
            st.push(ch);   // 左括号入栈
        } else if (ch == ')' || ch == ']' || ch == '}') {
            // 右括号：栈为空或栈顶不匹配则失败
            if (st.empty()) return false;

            char top = st.top();   // 查看栈顶元素
            st.pop();              // 弹出栈顶

            // 检查是否配对
            if ((ch == ')' && top != '(') ||
                (ch == ']' && top != '[') ||
                (ch == '}' && top != '{')) {
                return false;
            }
        }
    }
    // 所有括号都处理完，栈应该为空
    return st.empty();
}

int main() {
    string testCases[] = {"()", "({[]})", "([)]", "((())", "({})", "{[}"};

    for (string expr : testCases) {
        bool result = isValidBrackets(expr);
        cout << expr << " -> " << (result ? "合法" : "不合法") << endl;
    }
    return 0;
}

运行结果

()             -> 合法
({[]})         -> 合法
([)]           -> 不合法
((())          -> 不合法
({})           -> 合法
{[}            -> 不合法

新手常见错误汇总

  1. 忘记初始化栈顶指针：如果用数组实现且topIndex初始化为0，空栈时topIndex=0，但这时并没有元素，容易误判；更好的初始值是-1。
  2. 出栈或查看栈顶前不判空：这是最常见的bug，会导致程序崩溃或返回错误结果。
  3. 混淆push和pop的指针移动顺序：push时要先移动指针再赋值；pop时先取元素再移动指针（但通常pop不返回值，所以只需移动指针）。如果顺序反了，会覆盖或丢失数据。
  4. 静态数组栈溢出：如果用固定数组且不处理满栈的情况，入栈过多会越界。解决方法：使用动态数组（如C++的vector、Python的list）或预先分配足够空间。
  5. 忽略内存管理：在C++中，自己管理动态数组时要注意new和delete成对出现，避免内存泄漏。
  6. 误以为栈可以随机访问：栈只能访问栈顶元素，不能直接访问中间或底部的元素。如果需要随机访问，应选用数组或列表。

相关知识点指引

栈是一种基础但强大的数据结构，学会它之后，你可以继续探索以下内容：

  • 队列：先进先出（FIFO），与栈正好相反，常用于排队系统、广度优先搜索。
  • 递归：函数调用本身使用系统栈，理解栈有助于理解递归的返回过程。
  • 深度优先搜索（DFS）：在图或树中探索时，常常使用栈（显式或隐式）来控制遍历顺序。
  • 表达式求值：如中缀表达式转后缀表达式，栈是核心工具。
  • 单调栈：一种特殊的栈应用，用于解决“下一个更大元素”等问题。

栈的思想简单却无处不在，从操作系统到游戏开发，从编译器到网页浏览器。希望你能举一反三，用栈解决更多实际问题！

例题精讲

1单选题

栈是一种遵循____原则的数据结构。

A先进先出(FIFO)
B后进先出(LIFO)
C随机存取
D优先级调度
2单选题

在栈的基本操作中，从栈顶移除元素的操作通常称为____。

Apush
Bpop
Ctop
Dpeek
3判断题

栈和队列都是线性结构，但栈只能在栈顶进行操作，而队列可以在两端进行操作。

4填空题
以下是用数组实现栈的部分代码，请补全push函数的实现（假设栈的容量为MAX_SIZE，top初始值为-1）。

class Stack {
private:
    int data[MAX_SIZE];
    int top;
public:
    Stack() { top = -1; }
    bool push(int value) {
        if (top == MAX_SIZE - 1) return false;
        data[___] = value;
        return true;
    }
};
5填空题
以下是用链表实现栈的部分代码（节点定义已给出），请补全pop函数的实现。

struct Node {
    int data;
    Node* next;
};
class Stack {
private:
    Node* topNode;
public:
    Stack() { topNode = nullptr; }
    int pop() {
        if (isEmpty()) throw "Stack empty";
        Node* temp = topNode;
        int value = temp->data;
        topNode = ___;
        delete temp;
        return value;
    }
};