栈的定义
在我们软件应用中，栈这种 后进先出 的数据结构应用非常广泛。比如最常见到的浏览器，在使用浏览器访问网页时我们会发现无论是什么浏览器都会有一个 后退 键，点击后退键可以按照访问顺序的逆序加载之前浏览过的网页。即使你从一个网页，连续点了十几个链接跳转，你点 后退 时，还是可以像历史倒退一样，回到之前浏览过的某一个页面，如下图所示：
很多类似的软件，都有撤销(undo)的操作，也是用栈这种方式来实现的，当然不同的软件具体实现代码会有很大的差异，不过原理其实都是一样的
栈(stack)是仅限定在表尾进行插入和删除操作的线性表
我们把允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)，不包含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表，简称 LIFO 结构
在理解栈的定义时有几点需要注意：
1.首先栈是一个线性表，也就是说栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说栈仅限定在表尾进行插入和删除操作，这里的表尾指的是栈顶(top)而不是栈尾(bottom)
2.栈的特殊之处在于它限定了插入和删除操作的位置，它始终只在栈顶进行。这也就使得栈底是固定的，最先进栈的只能在栈底
3.栈的插入操作，叫做进栈，也称压栈、入栈。类似子弹入弹夹
4.栈的删除操作，叫做出栈，也称弹栈。类似子弹出弹夹
进栈出栈变化形式
最先进栈的元素是不是只能最后出栈呢？
答案是不一定，这个要看是什么情况。
举例来说，如果我们现在有 3 个整型数字元素 1、2、3 依次进栈，会有哪些出栈次序呢?
- 第一种：1、2、3 依次进栈，再 3、2、1 出栈，这是最简单的最好理解的一种。出栈次序为 3、2、1
- 第二种：1 进 1 出，2、3 进，3、2 出。出栈次序为 1、3、2
- 第三种：1、2 进 2、1 出，3 进 3 出。出栈次序为 2、1、3
- 第四种：1 进，2 进 2 出，3 进 3 出，1 出。出栈次序为 2、3、1
- 第五种：1 进 1 出，2 进 2 出，3 进 3 出。进来一个出去一个。出栈次序为 1、2、3
那么有没有可能是 312 这种出栈次序呢?答案是不可能。因为 3 已经出栈，说明 3 进栈了，如果 3 进栈了那么1、2 也肯定是进栈了，2 一定是在 1 的上面，那么出栈次序只能是 3、2、1，不然不满足1、2、3 依次进栈的要求
从这个例子可以看出来，只有 3 个整型数字元素时，就有 5 种出栈次序，如果元素更多那么出栈的变化更多，所以一定要知道并不是最先进栈的元素就只能最后出栈
栈的顺序存储结构以及实现
栈的顺序存储结构
栈是线性表的特例，那么栈的顺序存储也是线性表顺序存储的简化，我们简称为 顺序栈。线性表的顺序存储是用数组实现的，那么对于栈这种只允许在栈顶插入删除操作的特殊线性表来说，用数组的哪一端来作为栈底和栈顶比较好?
使用下标为 0 的一端作为栈底比较好，因为首元素都在栈底，变化最小，所以让它做栈底
我们定义一个 top 变量来指示栈顶元素在数组中的位置，这个 top 变量有点类似中学物理学过的游标卡尺的游标，它可以来回移动，这就意味着栈顶的 top 可以变大变小，但无论如何不能超出尺的长度。同理，在这里如果栈的存储长度为 stackSize ，则栈顶位置必须小于 stackSize。当栈存在一个元素时，则 top 为 0，因此通常把空栈的判定条件定为等于 -1
来看下栈的结构定义
typedef int SElemType;// SElemType 表示栈中数据元素的数据类型，在这里假设为 int
typedef struc {
SElemType data[MAX];
int top;
}SqStack;
假设现在有一个栈，StackSize 是 5，则栈普通情况，空栈，栈满的情况如下示意图所示
进栈(PUSH)操作
若现在有一个长度为 5 的栈，此时栈中有两个元素 a1、a2，变量 top 为 1，我们把数据元素 e 插入该栈中，操作示意图如下所示
具体代码实现如下
// 入栈(push)操作具体代码实现
// 将数据元素 e 插入栈 S 中,此时栈中有两个元素 a1,a2,此时变量 top(栈顶指针) 为 1
// 定义栈结构
typedef int SELemType;
typedef struct
{
SELemType data[MAX];
int top;
};
Status push(SqStack *S,SELemType e) {
// 判断栈是否已满
if(S->top == MAX - 1) {
return ERROR;
}
S->top++;// 栈顶指针向上移动一位
S->data[S->top] = e;// 将新插入元素 e 赋值给栈顶空间
return OK;
}
注意：入栈操作时首先需要判断下栈中元素是否已满
出栈(POP)操作
出栈操作具体代码实现如下
// 出栈(pop)操作具体代码实现
// 将栈 S 的栈顶元素删除，返回 OK,并用 e 返回其值
typedef int SELemType;
typedef struct
{
SELemType data[MAX];
int top;
};
Status pop(SqStack *S,SELemType *e) {
// 判断是否为空栈
if(S->top == -1) {
return ERROR;
}
*e = S->data[S->top];// 将栈顶元素赋值给 e
S->top--;// 将top指针向下移动一位
return OK;
}
注意：出栈操作首先需要判断是否为空栈
通过观察发现，入栈、出栈操作均没有涉及到循环，两者时间复杂度均为 O(1)
两栈共享空间
栈的顺序存储结构相比较于数组还是好用的，由于栈仅限在栈顶进行数据元素的插入删除，所以不牵涉到移动数据元素的问题。不过栈和数组一样有一个很大的缺陷，需要提前分配好存储空间的大小，如果存储空间不够了，需要扩容，扩容操作会占用多余资源，对性能有一定的影响，比较麻烦。所以，对于一个栈的情况我们只能尽可能的根据实际需求设计出合适大小的存储空间来处理。
如果我们有两个相同类型的栈，我们分别为它们分配了存储空间，现在其中一个栈已经满了，另一个栈还有很多存储空间没有利用，这就造成了资源的浪费，我们可以使用一个数组来存储两个栈，具体操作过程看下面
数组有两个端点，首端和末端，现在让其中一个栈的栈底作为数组的首端，即下标为 0 处，另一个栈的栈底作为数组的末端，即下标为数组长度 n - 1 处。当两个栈新增元素即两个栈的栈顶指针向中间移动
从上图可以分析出来，栈 1 为空时，此时 top1 为 -1；而当栈 2 为空时，此时 top2 为 n。那么什么时候栈满呢?
我们先来考虑一下极端情况：
- 栈 1 为空，即 top1 == -1，如果这个时候要想满栈那么 top2 需要为 0
- 栈 2 为空，即 top2 == n，如果这个时候要满栈那么 top1 需要为 n - 1
那么非极端情况下，也就是两个栈都有数据元素，此时要想存储这两个栈的数组满的话，那就需要两个栈的栈顶元素见面，此时两个栈的栈顶指针相差 1 ，即 top1 + 1 == top2
两栈共享存储空间的结构定义如下：
typedef struct
{
SElemType data[MAX];
int top1;//栈1 栈顶指针
int top2;//栈2 栈顶指针
}
对于两栈共享空间时，入栈(pop)操作需要判断元素是插入栈1还是栈2，即需要判断栈号 stackNumber，具体实现代码如下：
// 两栈共享空间,入栈操作(POP)
// 定义两栈共享空间时结构
typedef int SELemType;
typedef struct
{
SELemType data[MAX];
int top1;// 栈1 栈顶指针
int top2;// 栈2 栈顶指针
}SqDoubleStack;
Status Push(SqDoubleStack *S,SELemType *e,int stackNumber) {
// 判断是否栈满
if(S->top1 + 1 == S->top2) {
return ERROR;
}
if(stackNumber == 1) {
S->top1++;
S->data[top1] = e;
}elseif(stackNumber == 2) {
S->top2--;
S->data[top2] == e;
}
return OK;
}
两栈共享空间的出栈(pop)操作，具体代码实现如下：
// 两栈共享空间的出栈操作(pop)
// 定义两栈共享空间的结构
typedef int SELemType;
typedef struct
{
SELemType data[MAX];
int top1;// 栈1 栈顶指针
int top2;// 栈2 栈顶指针
}SqDoubleStack;
Status Pop(SqDoubleStack *S,SELemType *e,int stackNumber) {
// 判断出栈操作的是哪个栈
if(stackNumber == 1) {
// 判断栈是否为空
if(S->top1 == -1) {
return ERROR;
}
*e = S->data[S->top1]
}elseif(stackNumber == 2) {
// 判断栈是否为空
if(S->top1 == MAX) {
return ERROR;
}
*e = S->data[S->top2]
}
return OK;
}
使用两栈共享空间数据结构，通常是当两个栈的空间需求有相反关系时，也就是一个栈增长时另一个栈在缩短的情况。这样使用两栈共享空间存储才有比较大的意义。否则两个栈都在不停地增长，那很快就会因栈满而溢出
注意：使用两栈共享空间数据结构时保证两个栈存储的数据类型一致
