上QQ阅读APP看书，第一时间看更新
3.2.3 栈的存储结构
采用顺序存储结构的栈称为顺序栈。顺序栈通常采用一组连续的存储单元存放栈中的元素，存放顺序依次从栈底到栈顶。
1．顺序栈的基本运算
顺序栈的存储空间通常有两种分配方式：静态分配和动态分配。其中，采用静态分配的顺序栈类型定义如下：
说 明
（1）初始时，栈为空，栈顶指针为0，即S.top=0。
（2）栈空条件为S.top==0，栈满条件为S.top==StackSize-1。
（3）入栈操作时，先将元素压入栈中，即S.stack［S.top］=e，然后使栈顶指针加1，即S.top++。出栈操作时，先使栈顶指针减1，即S.top--，然后元素出栈，即e=S.stack［S.top］。
（4）栈的长度即栈中元素的个数，即S.top。
采用动态分配的顺序栈类型定义如下：
说 明
（1）初始时，栈为空，栈顶指针为S.top=S.base。
（2）栈空条件为S.top==S.base，栈满条件为S.top-S.base==S.maxSize。
（3）入栈操作时，先将元素压入栈中，即*S.top=e，然后使栈顶指针加1，即S.top++。出栈操作时，先使栈顶指针减1，即S.top--，然后元素出栈，即e=*S.top。
（4）栈的长度为S.top-S.base。
两种顺序栈的实现方式如表3-1所示。
表3-1 两种顺序栈的实现方式比较
2．链栈的基本运算
（1）链栈的初始化。
（2）入栈操作。入栈操作就是要将新元素结点插入到链表的第一个结点之前，分为两个步骤：①p->next=top->next；②top->next=p。入栈操作如图3-2所示。
图3-2 入栈操作
（3）出栈操作。出栈操作就是将单链表中的第一个结点删除，并将结点的元素赋给e，最后释放结点空间。在元素出栈前，要判断栈是否为空。出栈操作如图3-3所示。
图3-3 出栈操作
