(15)王道数据结构-栈的基本概念

基本定义

栈是只允许在一端进行插入或删除操作的线性表

重要概念

栈顶：允许插入和删除的一端
栈底：不允许插入和删除的一端

基本结构

逻辑结构：与普通线性表相同
数据运算：插入、删除操作有区别

基本操作

InitStack(&S): 初始化栈。构造一个空栈S，分配内存空间****
DestoryStack(&S): 销毁栈。销毁并释放栈S所占用的内存空间
Push(&S, x): 进栈，若栈S未满，则将x加入使之成为新栈顶
Pop(&S, &x): 出栈，若栈S未空，则弹出栈顶元素，并用x返回
GetTop(S, &x): 读取栈顶元素。若栈S非空，则用x返回栈顶元素

其他操作：

StackEmpty(S): 判断一个栈是否为空。若S为空，则返回true，否则返回false

常考题型

进栈顺序：a->b->c->d->e，有哪些合法的出栈顺序

卡特兰数

n个不同元素出栈，出栈不同排列的个数为
$$
\frac{1}{n+1}·C_{2n}^{n}
$$