7、数据结构——栈与队列——栈（一）
定义
线性表是具有相同数据类型的n(n ≥ 0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用命名线性表，则其一般表示为
$$
L=(a_1,a_2…,a_i~…,a_n)
$$
栈(Stack)是只允许在一端进行插入或删除操作的线性表
重要术语： 栈底、栈顶、空栈
特点： 后进现出，比如这个图的进栈顺序是
$$
a_1->a_2->a_3->a_4->a_5
$$
出栈顺序是
$$
a_5->a_4->a_3->a_2->a_1
$$
栈的基本操作
InitStack(& S)：初始化栈。构造一个空栈S，分配内存空间。
DestotyStack(& L)： 销毁栈。销毁并释放栈S所占的内存空间。
Push(&S,x)： 进栈。若S未满，将x插入成为新栈。
Pop(&S)： 出栈。若S非空，将栈顶x弹出成为新栈。
GetTop(&S)：读栈顶元素。若栈S非空，则用 x 返回栈顶元素。
StackEmpty(& S)： 判断一个栈 S 是否为空。若S为空，则返回true，反之返回false。
一个公式
n个不同元素进栈，出栈元素不同排列的个数为
上述公式称为卡特兰(Catalan)数，可采用数学归纳法证明（不要求掌握)。
