栈的基本概念

栈的定义

栈（Stack）是只允许在一端进行插入或删除操作的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。

HTML 初体验

栈顶（Top）：线性表允许进行插入和删除操作的那一端。
栈底（Bottom）：固定的，不允许进行插入和删除操作的另一端。
空栈：不含任何元素的空表。

假设某个栈 $S = (a_{1}, a_{2}, a_{3}, a_{4}, a_{5})$ ，如图所示。则 $a_{1}$ 为栈底元素， $a_{5}$ 为栈顶元素。

入栈次序： $a_{1}$ -> $a_{2}$ -> $a_{3}$ -> $a_{4}$ -> $a_{5}$
出栈次序： $a_{5}$ -> $a_{4}$ -> $a_{3}$ -> $a_{2}$ -> $a_{1}$

由此可见，栈的操作特性可以明显地概括为后进先出（Last In First Out，LIFO）。

栈的基本操作

InitStack(&S)：初始化一个空栈 S ，分配内存空间。
DestroyStack(&S)：销毁栈 S ，销毁并释放栈 S 占用的内存空间。
Push(&S, x)：入栈，若栈 S 未满，则将 x 加入使之成为新栈顶。
Pop(&S, &x)：出栈，若栈 S 非空，则弹出栈顶元素，并用 x 返回。
GetTop(S, &x)：读栈顶元素，但不出栈，若栈 S 非空，则用 x 返回栈顶元素。
StackEmpty(S)：判断一个栈是否为空，若栈 S 为空则返回 true ，否则返回 false 。

在解答算法题时，若题干未做出限制，则也可直接使用这些基本的操作函数。

栈的数学性质：当 $n$ 个不同元素入栈时，出栈元素不同排列的个数为 $\begin{array}{r} \frac{C_{2 n}^{n}}{n + 1} \end{array}$ 。这个公式称为卡特兰数（Catalan）公式，可采用数学归纳法证明。

假设 $n = 5$ ，则出栈元素不同排列的个数为 $\begin{array}{r} \frac{1}{5 + 1} C_{10}^{5} = \frac{10 \times 9 \times 8 \times 7 \times 6}{6 \times 5 \times 4 \times 3 \times 2 \times 1} = 42 \end{array}$

HTML 初体验