04-数据结构/03-stack

栈是一种后进先出（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; }