stack
分类: 数据结构
· 更新时间 2026-5-27 21:41:24
栈是一种**后进先出（LIFO）**的数据结构。
定义
stack<int> sta;
常用操作
| 操作 | 说明 |
|---|---|
sta.push(x) |
将 x 压入栈顶 |
sta.pop() |
弹出栈顶元素 |
sta.top() |
返回栈顶元素 |
sta.size() |
返回元素数量 |
sta.empty() |
判断是否为空 |
示例
stack<int> sta;
sta.push(1);
sta.push(2);
sta.push(3);
while (!sta.empty())
{
cout << sta.top() << " "; // 输出 3 2 1
sta.pop();
}
栈的典型应用
- 括号匹配
- 表达式求值
- DFS（深度优先搜索）的非递归实现
- 单调栈
手写栈
可以用数组模拟栈：
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; }