编辑“︁C++stac”︁

{{Note|本文是C++STL容器系列的一部分，重点介绍'''stack（栈）'''容器适配器的特性和用法。适合初学者和需要巩固概念的开发者阅读。}}

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

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

== 成员函数 ==
{| class="wikitable"
! 函数 !! 描述
|-
| <code>push()</code> || 在栈顶插入元素
|-
| <code>pop()</code> || 移除栈顶元素（不返回）
|-
| <code>top()</code> || 返回栈顶元素引用
|-
| <code>empty()</code> || 检查栈是否为空
|-
| <code>size()</code> || 返回元素数量
|}

== 代码示例 ==
=== 基础用法 ===
<syntaxhighlight lang="cpp">
#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;
}
</syntaxhighlight>

'''输出结果：'''
<pre>
Top element: 30
After pop, top element: 20
Stack elements: 20 10
</pre>

=== 自定义底层容器 ===
<syntaxhighlight lang="cpp">
#include <stack>
#include <vector>

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

== 实际应用案例 ==
=== 括号匹配检查 ===
<syntaxhighlight lang="cpp">
#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();
}
</syntaxhighlight>

=== 浏览器历史记录 ===
<mermaid>
graph LR
    A[访问页面A] --> B[访问页面B]
    B --> C[访问页面C]
    C --> D[点击后退按钮]
    D --> E[显示页面B]
</mermaid>

== 数学表示 ==
栈操作可以形式化为：
* 初始化：<math>S = \empty</math>
* 压栈：<math>S' = S \cup \{x\}</math>
* 弹栈：<math>x = top(S), S' = S \setminus \{x\}</math>

== 常见问题 ==
=== 为什么stack没有迭代器？===
由于LIFO原则的限制，直接访问非栈顶元素会破坏栈的设计初衷。如需遍历，可临时复制到其他容器。

=== 如何清空stack？===
两种方法：
<syntaxhighlight lang="cpp">
// 方法1：循环pop
while (!s.empty()) s.pop();

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

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

{{Tip|stack常用于需要撤销操作的场景，如文本编辑器的撤销栈、函数调用栈等。}}

[[Category:编程语言]]
[[Category:C++]]
[[Category:C++stl 容器]]