ch4 栈与队列¶

1. 栈¶

栈是受限的序列，只能在栈顶插入和删除，栈底为盲端，是一种后进先出（\(\tt LIFO\)）或先进后出（\(\tt FILO\)）的数据结构。

递归算法所需的空间，主要取决于最大递归深度，而非递归实例总数。为隐式地维护调用栈，需花费额外的时间、空间；为节省空间，可显式地维护调用栈，将递归算法改写为迭代版本。

尾递归是最简单的递归模式，一旦抵达递归基，便会引发一连串的 return 且返回地址相同，调用栈相应地连续 pop，因此不难改写为迭代形式。许多编译器可以自动识别并代为改写，比如 \(\tt g\)++ 中的 -O2 优化选项。时间复杂度有常系数改进，空间复杂度或有渐进改进。

【栈混洗】

混洗总数 \(SP(n) = \sum_{k=1}^n SP(k-1)\cdot SP(n-k)=catalan(n)=\frac{(2n)!}{(n+1)!\cdot n!}\)
禁形：对任何 \(1\le i<j<k\le n\)，\([..,k,..,i,..,j,..]\) 必非栈混洗。直接模拟可以得到一个 \(\cal O(n)\) 的检测禁形的算法。
\(n\) 个元素的栈混洗，等价于 \(n\) 对括号的匹配，二者的组合数也相等。

队列也是受限的序列，只能在队尾插入 / 查询，只能在队首删除 / 查询，是一种先进先出（\(\tt FIFO\)）或后进后出（\(\tt LILO\)）的数据结构。

可以用两个栈（对底栈）模拟实现队列。