一、栈
- 后进先出
- 是一种限制访问端口的线性表
- 主要操作
- 进栈（push）
- 出栈（pop）
- 应用
- 表达式求值（中缀表达式、后缀表达式）
- 消除递归
- 深度优先搜索（树、图）
二、栈的抽象数据类型
template <class T>
class Stack {
public: // 栈的运算集
void clear(); // 变为空栈
bool push(const T item); // item入栈，成功返回真，否则假
bool pop(T& item); // 返回栈顶内容并弹出，成功返回真，否则假
bool top(T& item); // 返回栈顶但不弹出，成功返回真，否则假
bool isEmpty(); // 若栈已空返回真
bool isFull(); // 若栈已满返回真
};
三、思考题
-
若入栈顺序为
1,2,3,4的话，则出栈的顺序可以有哪些?- 1234
- 1243
- 1324
- 1342
- 1423 错误
- 1432
- 2134
- 2143
引理：设 k 是最后一个出栈的，那么 k 把序列一分为二；在 k 之前入栈的元素，一定比在 k 之后入栈的元素，要提前出栈 -
从初始输入序列 $1,2,…,n$，希望利用一个栈得到输出序列 $p_1,p_2,…,p_n$（它们是 $1,2,…,n$的一种排列）。若存在下标 $i,j,k$，满足 $i<j<k$ 同时 $p_j<p_i<p_k$，则输出序列是否合法？
-
给定一个入栈序列，和一个出栈序列，请你写出一个程序，判定出栈序列是否合法？
可以根据上面的引理写一个 减而治之 的算法
-
给定一个入栈序列，序列长度为 N，请计算有多少种出栈序列？
$$ \begin{aligned} f(n) &= \sum_{x=0}^{n-1} f(x) \times f(N-1-x)\newline &= \frac{1}{N+1} \times C_{2N}^{N} \end{aligned} $$
Catalan 数