第三章：栈和队列
1. 栈的基本概念
栈(Stack) 是一种特殊的线性表，其只允许在一端（称为栈顶）进行插入或删除操作。
在栈中，最先进入的元素将最后出栈，即遵循先进后出（LIFO）的原则。
2. 栈的基本操作及其详解
InitStack(&s) 初始化一个空栈，使其具备栈的基本属性。
StackEmpty(S) 判断一个栈是否为空，若栈内无元素则返回真。
Push(&S，x) 进栈操作，将元素x加入栈中，并使其成为新的栈顶。
Pop(&S，&x) 出栈操作，若栈非空，则弹出栈顶元素并返回其值至x。
GetTop(S，&x) 读取栈顶元素的操作，若栈非空，则将栈顶元素的值存入x。
ClearStack(&S) 销毁栈，释放S占用的内存空间。
值得注意的是，Pop和GetTop两个操作看似相似，但有本质区别。Pop会移除栈顶元素，而GetTop仅获取栈顶元素的值，并不会移除它。
3. 栈的顺序存储结构
顺序栈是采用顺序存储方式实现的栈。
3.1 判断栈的状态
当S.top为-1时，表示栈空；栈的长度为S.top+1；当S.top等于其最大容量MinSize-1时，表示栈满。
3.2 顺序栈的基本操作及其详解
包括初始化、判断栈空、进栈、出栈、获取栈顶元素等操作。
3.3 共享栈
共享栈是将两个栈底设置在共享空间的两端，使栈顶向空间中间延伸。这种结构能够有效地利用空间。
判空和判满的条件
- 0号栈 top值为-1时表示空；
- 1号栈 top值达到其最大容量时表示满；
- 两栈共享时需注意top值的计算以确定是否判满。
共享栈的优点在于其存取时间复杂度仍为O(1)，且空间利用更加高效。
4. 链式存储结构的栈
链栈 是采用链式存储方式实现的栈。
链栈不需要头节点，首个结点即为栈顶结点，所有操作均在表头进行。
4.1 链栈的基本操作及其特点