当前位置：首页 > article >正文

C++ stack：数据结构的“叠盘子艺术”与“后进先出法则

article 2025/2/25 18:39:36

C++ stack：数据结构的“叠盘子艺术”与“后进先出法则”

开篇小故事：厨房里的“盘子魔法”

想象你在厨房洗碗时，将盘子一个个叠放起来：

放入盘子：你只能将新盘子放在最顶端。
取出盘子：你只能从最顶端拿起盘子。
查看盘子：你只能看到最顶端的那个，无法直接抽出底层的盘子。

这种“叠盘子”的规则正是**栈（Stack）**的核心思想！在C++中，std::stack就像是一个智能叠盘架，帮你高效管理数据，严格遵守“后进先出（LIFO）”的法则。

一、stack是什么？

std::stack是C++标准模板库（STL）提供的容器适配器，基于其他容器（如deque或list）实现，专门用于LIFO操作。

核心特性：后进先出（Last In, First Out）。
受限操作：只能访问、添加或移除顶部的元素。
高效操作：push（入栈）、pop（出栈）、top（查看栈顶）的时间复杂度均为O(1)。

与数组/链表的对比

操作	数组/链表	stack
插入位置	任意位置	只能栈顶
删除位置	任意位置	只能栈顶
访问方式	随机访问（下标/迭代器）	只能访问栈顶

二、stack的“基本招式”

1. 创建stack

#include <stack>
using namespace std;

stack<int> s1;                 // 默认基于deque的栈
stack<string, vector<string>> s2; // 基于vector的栈
stack<char> s3({ 'a', 'b' });  // 初始化栈（C++11起）

2. 入栈与出栈

s1.push(10);      // 栈顶添加元素：10 → 20 → 30
s1.push(20);
s1.push(30);

s1.pop();         // 移除栈顶元素（30被移除）
// 注意：pop()不返回栈顶值！需先通过top()获取

3. 访问栈顶

cout << s1.top(); // 输出20（当前栈顶元素）
// s1.top() = 100; // 可以修改栈顶元素

4. 查看信息

if (s1.empty()) { /* 栈是否为空 */ }
cout << s1.size();  // 栈中元素个数

三、stack的“实现原理”

std::stack是一个容器适配器，默认使用deque作为底层容器，但也可指定其他容器（需支持back()、push_back()、pop_back()操作）：

// 基于vector实现栈
stack<int, vector<int>> vecStack;
// 基于list实现栈
stack<string, list<string>> listStack;

为什么选择deque作为默认容器？

动态扩容：deque支持高效的前后插入/删除，内存分配比vector更均衡。
避免拷贝：扩容时不需要整体迁移数据。

四、stack的“实战场景”

1. 函数调用栈

程序执行函数时，系统栈用于保存函数返回地址、局部变量等：

void funcA() { funcB(); }  // funcA入栈 → funcB入栈 → funcB出栈 → funcA出栈
void funcB() { /* ... */ }

2. 括号匹配检查

bool isBalanced(string expr) {
    stack<char> s;
    for (char c : expr) {
        if (c == '(' || c == '[') s.push(c);
        else if (c == ')') {
            if (s.empty() || s.top() != '(') return false;
            s.pop();
        } else if (c == ']') {
            if (s.empty() || s.top() != '[') return false;
            s.pop();
        }
    }
    return s.empty();
}
// 示例：isBalanced("([()])") → true

3. 撤销操作（Undo）

文本编辑器中的撤销功能通常用栈实现：

stack<string> history;
history.push("Hello");     // 当前文本："Hello"
history.push("Hello World"); // 编辑后入栈
history.pop();             // 撤销到上一步："Hello"

4. 深度优先搜索（DFS）

图或树的DFS算法依赖栈结构：

stack<Node*> dfsStack;
dfsStack.push(rootNode);
while (!dfsStack.empty()) {
    Node* current = dfsStack.top();
    dfsStack.pop();
    // 处理当前节点，并将其子节点入栈
}

五、stack的“使用禁忌”

1. 禁止随机访问

// 错误示例：尝试访问中间元素
// cout << s1[1];      // 编译错误！stack没有[]运算符

2. 空栈操作

stack<int> s;
// cout << s.top();    // 未定义行为（崩溃！）
// s.pop();            // 同样危险！

3. 误用递归导致栈溢出

虽然与数据结构栈不同，但递归深度过大会导致系统调用栈溢出：

void infiniteRecursion() {
    infiniteRecursion(); // 最终引发栈溢出错误（Stack Overflow）
}

六、stack的“性能秘籍”

操作	时间复杂度	说明
`push()`	O(1)	添加元素到栈顶
`pop()`	O(1)	移除栈顶元素
`top()`	O(1)	访问栈顶元素
`size()`	O(1)	返回元素数量

最佳实践：

优先使用默认的deque作为底层容器。
避免在栈中存储过大对象（可能影响缓存性能）。

七、动手实验

1. 反转字符串

string reverseString(const string& str) {
    stack<char> s;
    for (char c : str) s.push(c);
    string reversed;
    while (!s.empty()) {
        reversed += s.top();
        s.pop();
    }
    return reversed;
}
// reverseString("hello") → "olleh"

2. 模拟浏览器历史记录

stack<string> backHistory, forwardHistory;
string currentPage = "home";

void visitPage(const string& url) {
    backHistory.push(currentPage);
    currentPage = url;
    while (!forwardHistory.empty()) forwardHistory.pop();
}

void goBack() {
    if (!backHistory.empty()) {
        forwardHistory.push(currentPage);
        currentPage = backHistory.top();
        backHistory.pop();
    }
}