C++ stack容器[编辑 | 编辑源代码]

stack是C++标准模板库（STL）中的一种容器适配器，它基于其他容器（如deque或list）实现，遵循后进先出（LIFO）原则。stack不提供迭代器，仅允许在容器顶部进行插入和删除操作。

基本特性[编辑 | 编辑源代码]

时间复杂度：所有操作均为O(1)
底层容器：默认使用deque，也可指定vector或list
头文件：<stack>

成员函数[编辑 | 编辑源代码]

函数	描述
`push()`	在栈顶插入元素
`pop()`	移除栈顶元素（不返回）
`top()`	返回栈顶元素引用
`empty()`	检查栈是否为空
`size()`	返回元素数量

代码示例[编辑 | 编辑源代码]

基础用法[编辑 | 编辑源代码]

#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;

    // 压栈操作
    s.push(10);
    s.push(20);
    s.push(30);

    // 查看栈顶
    std::cout << "Top element: " << s.top() << "\n";

    // 弹栈操作
    s.pop();
    std::cout << "After pop, top element: " << s.top() << "\n";

    // 遍历栈（通过清空方式）
    std::cout << "Stack elements: ";
    while (!s.empty()) {
        std::cout << s.top() << " ";
        s.pop();
    }
    return 0;
}

输出结果：

Top element: 30
After pop, top element: 20
Stack elements: 20 10

自定义底层容器[编辑 | 编辑源代码]

#include <stack>
#include <vector>

int main() {
    // 使用vector作为底层容器
    std::stack<int, std::vector<int>> v_stack;
    v_stack.push(5);
    v_stack.push(10);
    // ...其他操作相同
}

实际应用案例[编辑 | 编辑源代码]

括号匹配检查[编辑 | 编辑源代码]

#include <stack>
#include <string>

bool isBalanced(const std::string& expr) {
    std::stack<char> s;
    for (char c : expr) {
        if (c == '(' || c == '[' || c == '{') {
            s.push(c);
        } else {
            if (s.empty()) return false;
            char top = s.top();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
            s.pop();
        }
    }
    return s.empty();
}

浏览器历史记录[编辑 | 编辑源代码]

数学表示[编辑 | 编辑源代码]

栈操作可以形式化为：

初始化： $S = \emptyset$
压栈： $S^{'} = S \cup {x}$
弹栈： $x = t o p (S), S^{'} = S ∖ {x}$

常见问题[编辑 | 编辑源代码]

为什么stack没有迭代器？[编辑 | 编辑源代码]

由于LIFO原则的限制，直接访问非栈顶元素会破坏栈的设计初衷。如需遍历，可临时复制到其他容器。

如何清空stack？[编辑 | 编辑源代码]

两种方法：

// 方法1：循环pop
while (!s.empty()) s.pop();

// 方法2：与空栈交换
std::stack<int>().swap(s);

性能考虑[编辑 | 编辑源代码]

默认使用deque作为底层容器时，内存分配比vector更高效
对于极端性能场景，可测试不同底层容器的表现

模板:Tip