查看“︁04-数据结构/03-stack”︁的源代码


栈是一种'''后进先出（LIFO）'''的数据结构。

=== 定义 ===

<syntaxhighlight lang="cpp">
stack<int> sta;
</syntaxhighlight>

=== 常用操作 ===

{| class="wikitable"
! 操作 !! 说明
|-
| <code>sta.push(x)</code>
| 将 <code>x</code> 压入栈顶
|-
| <code>sta.pop()</code>
| 弹出栈顶元素
|-
| <code>sta.top()</code>
| 返回栈顶元素
|-
| <code>sta.size()</code>
| 返回元素数量
|-
| <code>sta.empty()</code>
| 判断是否为空
|}

=== 示例 ===

<syntaxhighlight lang="cpp">
stack<int> sta;
sta.push(1);
sta.push(2);
sta.push(3);

while (!sta.empty())
{
    cout << sta.top() << " "; // 输出 3 2 1
    sta.pop();
}
</syntaxhighlight>

=== 栈的典型应用 ===

- 括号匹配
- 表达式求值
- DFS（深度优先搜索）的非递归实现
- 单调栈

=== 手写栈 ===

可以用数组模拟栈：

<syntaxhighlight lang="cpp">
int stk[1005];
int top = 0; // 栈顶指针

void push(int x) { stk[++top] = x; }
void pop() { top--; }
int getTop() { return stk[top]; }
bool empty() { return top == 0; }
</syntaxhighlight>


[[Category:数据结构]]
[[Category:三三文档]]