栈

知识总结

栈的定义

栈（Stack）是一种后进先出（LIFO, Last In First Out）的线性数据结构。

只能在栈顶进行插入（push）和删除（pop）操作。

基本操作

C++ STL 栈

1#include <stack>
2stack<int> s;
3s.push(1);
4s.push(2);
5s.push(3);
6cout << s.top(); // 3
7s.pop();
8cout << s.top(); // 2

栈的应用

1. 括号匹配：遇到左括号入栈，遇到右括号与栈顶匹配
2. 表达式求值：中缀转后缀、后缀表达式求值
3. 函数调用栈：递归的实现原理
4. 进制转换：利用栈记录余数

出栈序列问题（初赛常考）

n个元素依次入栈，合法出栈序列的数目 = 卡特兰数 C(2n, n) / (n+1)

例如：3个元素入栈，合法出栈序列有 5 种。

判断出栈序列是否合法：模拟入栈出栈过程，如果能完成则合法。