一 目录
目录
二 栈的概念
1.定义
栈是一种只允许在一端进行插入和删除的线性表，是一种操作受限的线性表。
我们把允许插入删除的一端称为栈顶（top)，另一端称为栈底，不含任何数据元素的栈称为空栈。
栈又称为后进先出(Last In First Out)的线性表，简称LIFO结构。
2.操作
- 栈顶：允许进行删除和插入的一端称为栈顶
- 栈底：不允许进行删除和插入的一端称为栈底
- 出栈：在栈顶进行删除操作
- 入栈：在栈顶进行插入操作
- 空栈：栈内没有元素
二 进栈出栈变化形式
最先进栈的元素，不一定只能最后出栈。
栈对线性表的插入和删除的位置进行限制，并没有对元素进出的时间进行限制，也就是说，在不是所有元素都进栈的情况下，事先进去的元素也可以出栈，只要保证栈顶元素出栈即可。
举例， 3个整型数字元素进栈 1，2，3依次进栈会有以下几种出栈次序。
第一种：1，2，3 进，3 ，2， 1出。出栈次序为 123.
第二种：1 进，1 出，2 进，2 出，3 进， 3 出。 也就是一个进一个出， 出栈次序为123.
第三种：1 进， 2进， 2 出，1 出，3 进， 3 出。出栈次序213.
第四种：1 进，1 出，2 进， 3 进， 3 出， 2 出。 出栈次序132.
第五种：1 进，2 进， 2 出，3 进，3 出， 1 出。出栈次序231.
三 栈的抽象数据类型
四 栈的顺序存储结构极其实现
1 预说明
1：在栈中我们我们把空栈的top值设为 -1
2：把满栈的top值设为 maxsize - 1
3：把下标为0的一端作为栈底
2 栈的顺序存储结构——栈的定义
3:栈的顺序存储结构——进栈操作
4: 栈的顺序存储结构——出栈操作
5: 栈的顺序存储结构——两栈共享空间
在这儿我门先讨论一个解决栈上溢的解决方法
方法一：将栈的容量加到足够大，但这种方法由于事先难以估计容量，可能存在浪费空间的可能性
方法二：使用两个（或者多个）栈共享存储空间办法.两栈的栈底分别设在给定存储空间的两端，然后各自向中间伸延，当两栈的栈顶相遇时栈满。
.两栈共享技术： 双端栈
利用“栈底位置不变，栈顶位置动态变化”特征
1首先为两个栈申请一个共享的一维数组空间S[M]；
2将两个栈底分别放在一维数组的两端，分别为0，M-1。
思路关键：它们是数组的两端，向中间靠拢。top1 和 top2 是栈1 和栈2的栈顶指针，可以想象，只要他们两不见面，两个栈可以一直使用。
栈1为空的时候，就是 top1等于-1时；而当偷拍等于n时，栈2时空栈。
极端情况，栈2空栈，栈1 top1等于 n - 1栈1满，栈1为空栈，top2 等于 0栈2满。
大多情况，两个栈见面时，即两个指针之间相差1时，即top1 + 1 == top2 为满栈
