栈（代码分解）

完整代码的链接：https://www.cnblogs.com/ouyang_wsgwz/p/7748058.html

栈和队列是两种中重要的线性结构。从数据结构的角度来看，栈和队列也是线性表，其特殊的在于栈和队列的基本操作是线性表操作的子集，它们是受限的线性表，因此，可称为限定性的数据结构。

栈

1.栈（stack）是限定仅在标为之间进行插入或者删除操作的线性表。

　　栈顶（Top）。线性表允许进行插入和删除的那一端。

　　栈底（Bottom）。固定的，不允许进行插入和删除的另一端。

　　空栈。不含任何元素的空表。

栈的抽象数据类型的类型：

ADT Stack {

　　数据对象：D = { a_i | a_i ∈ ElemSet, i = 1, 2, …, n, n≥0 }

　　数据关系：R1 = { < a_i-1, a_i > | a_i-1, a_i ∈ D, i = 1, 2, …, n }

　　　　　　　约定an端为栈顶，a1端为栈底。

　　基本操作：

　　　　InitStack( &S )

　　　　　　操作结果：构造一个空栈S。

　　　　DestroyStack ( &S )

　　　　　　初始条件：栈S已存在。

　　　　　　操作结果：销毁栈S。

　　　　ClearStack( &S )

　　　　　　初始条件：栈S已存在。

　　　　　　操作结果：将S清为空栈。

　　　　StackEmpty( S )

　　　　　　初始条件：栈S已存在。

　　　　　　操作结果：若S为空栈，则返回TRUE，否则返回FALSE。

　　　　StackLength( S )

　　　　　　初始条件：栈S已存在。

　　　　　　操作结果：返回S的数据元素个数，即栈的长度。

　　　　GetTop( S, &e )

　　　　　　初始条件：栈S已存在且非空。

　　　　　　操作结果：用e返回S的栈顶元素。

　　　　Push( &S, e )

　　　　　　初始条件：栈S已存在。

　　　　　　操作结果：插入元素e为新的栈顶元素。

　　　　Pop( &S, &e )

　　　　　　初始条件：栈S已存在且非空。

　　　　　　操作结果：删除S的栈顶元素，并用e返回其值。

　　　　StackTraverse( S, visit() )

　　　　　　初始条件：栈S已存在且非空。

　　　　　　操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。

}ADT Stack

1.顺序栈的实现

采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶的位置。

　　栈的顺序存储类型可描述为：

1 #define MaxSize 50                //定义栈中元素的最大个数
2 typedef struct{            
3     ElemType data[MaxSize];        //存放栈中元素
4     int top;                    //栈顶指针
5 } SqStack;

　　栈顶指针：S.top，初始时设置 S.top = -1；栈顶元素：S.data[S.top]。

　　进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素。

　　出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减1。

　　栈空条件：S.top == -1；栈满条件：S.top == MasSize - 1；栈长：S.top+1

　　由于顺序栈的入栈操作受数组上界的约束，当对栈的最大使用空间估计不足时，有可能发生上溢，此时应及时向用户报告信息，以便于及时处理。

　　栈和后面的队列的判空和判慢条件，会因为实际给的条件不同而变化，以上提到的方法以及给出的代码实现只是一些相应的方法，其他情况需要具体问题具体分析。

2.顺序栈的基本运算

（1）初始化

void InitStack(SqStack &S){ S.top = -1; }

（2）判栈空

1 bool StackEmpty(SqStack){
2     if (S.top == -1)
3         return true;    //栈空
4     else 
5         return false;    //不空
6 }

（3）进栈

1 bool Push(SqStack &S, ElemType x){
2     if (S.top == MaxSize - 1){        //栈满，报错
3         return false;        
4     }    
5     S.data[++S.top] = x;            //指针先加1，再入栈
6     return true;
7 }

（4）出栈

1 bool Pop(SqStack &S, ElemType &x){
2     if (S.top == -1){        //栈空，报错
3         return false;
4     }
5     x = S.data[S.top--];    //先出栈，指针再减1
6     return true;
7 }

（5）读栈顶元素

1 bool GetTop(SqStack S, ElemType &x) {
2     if (S.top == -1)     //栈空报错。
3         return false;
4     x = S.data[S.top];    //记录栈顶元素
5     return true;
6 }

注：这里栈顶元素指针指向的是栈顶元素，所以进栈时的操作是S.data[++S.top] = x，出栈的操作是 x = S.data[S.top--]。若栈顶指针初始化为 S.top = 0，即栈顶指针指向栈顶元素的下一个位置，则入栈操作变为 S.data[S.top++] = x；出栈操作会变为 x = S.data[--S.top]。相应的栈空、栈满条件也会改变，要灵活应变。

3.共享栈

　　利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数据空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。

　　两个栈的栈顶指针都指向栈顶元素，top0 = -1时0号栈为空，top1 = MaxSize 时1号栈为空；仅当两个栈顶指针相邻（top1-top0 = 1）时，判断为栈满。当0号栈进栈时 top0先加1再赋值，1号栈进栈时top1先减1再赋值；出栈时刚好相反。

优点：共享栈是为了更有效地利用存储空间，两个栈的空间互相调节，只有在整个存储空间被占满的时候才会发生上溢。其存取数据的时间复杂度均为O(1)，所以对存取效率没有什么影响。

栈的链式存储结构

　　采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头结点，Lhead指向栈顶元素。

　　栈的链式存储类型可描述为：

1 typedef struct Linknode{
2     ElemType data;            //数据域
3     struct Linknode *next;    //指针域
4 } *LiStack;                    //栈类型定义

　　采用链式存储，便于结点的插入与删除。链栈的操作与链表类似。