数据结构 | 栈
01 栈的定义
栈（Stack）是限定仅在表尾进行插入和删除操作的线性表。
我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。栈又称为后进先出（Last In First Out）的线性表，简称 LIFO 结构。
从上面这两段话，可以确定：首先栈是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系，只不过它是一种特殊的线性表。定义中说在线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底。
栈的插入操作，叫做进栈，也叫压栈、入栈。
栈的删除操作，叫做出栈。
02
进栈出栈变化多端
最先进栈的元素，不一定是最后出栈的。
栈对线性表的插入和删除的位置进行了限制，并没有对元素进出的时间进行限制。意思就是说，当并非所有的元素都进栈的情况下，先进去的元素也可以出栈，只要保证栈顶元素出栈就可以了。
比如，现在有 3 个元素 1、2、3，可能的出栈顺序有下面几种：
- 第一种：1、2、3 依次进栈，再 3、2、1依次出栈，显然出栈顺序为321。
- 第二种：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。
03
栈的抽象数据类型
我们知道，栈是一个特殊的线性表，由于它的特殊性，所以与线性表的操作会略有不同。特别是插入和删除操作，我们分别叫它 push 和 pop。
栈的抽象数据类型
ADT 栈（stack）
Data
同线性表，元素具有相同的类型，相邻元素具有前驱和后继关系。
Operation
initStack(*S)：初始化操作，建立一个空栈 S。
destroyStack(*S)：若栈存在，则销毁它。
clearStack(*S)：清空栈。
isEmpty(S)：若栈为空返回 true，否则返回 false。
getTop(S, *e)：若栈存在且非空，用 e 返回 S 的栈顶元素。
push(*S, e)：若栈 S 存在，插入新元素 e 到栈 S 中并成为栈顶元素。
pop(*S, *e)：删除栈顶元素，并且 e 返回其值。
length(S)：返回栈 S 的元素个数。
endADT
由于栈本身就是一个线性表，所以线性表的顺序存储和链式存储对于栈来说，同样适用。
04
栈的顺序存储结构及实现
因为栈是线性表的特例，栈的顺序存储其实是线性表顺序存储的简化，简称为顺序栈。
线性表是用数组实现的，对于栈这种只能一端插入删除的线性表来说，下标为 0 的一端作为栈底比较好，因为首元素都存在栈底，变化最小。
我们定义一个变量 top 来指示栈顶元素在数组中的位置，若栈的长度为 stackSize，则栈顶位置 top 必须小于 stackSize。当栈中存在一个元素时，top 等于 0，因此把空栈的判定条件定为 top = -1。
栈的结构定义
define MAXSIZE = 10
typedef struct {
int data[MAXSIZE];
int top;
} SqStack;
进栈操作
boolean push(SqStack *s, int e) {
if (s->top == MAXSIZE - 1） {
return false;
}
s->top++;
s->data[s->top] = e;
return true; }
出栈操作
若栈不为空，则删除栈顶元素，并把其值赋值给 e。
boolean pop(SqStac *s, int *e) {
if (s->top == -1)
return false;
*e = s->data[s->top];
s->top--;
return true; }
通过进栈和出栈操作的代码可以看出，时间复杂度都为 O(1)。
05
两栈共享空间
栈的顺序存储有一个很大的缺陷，必须先确定数组存储空间大小，而且万一不够用了，还要扩容。
对于一个栈，我们只能尽量考虑周全，设计出合适大小的数组来处理，但对于两个相同类型的栈，我们可以做到最大限度地利用事先开辟的存储空间来进行操作。
如果我们有两个相同类型的栈，我们为它们各自开辟了数组空间，有可能第一个栈已经满了，而另一个栈还有很多存储空间。我们完全可以用一个数组来存储两个栈。
我们知道，数组有两个端点，两个栈有两个栈底。可以让一个栈的栈底为数组的开始端，即下标为 0 处，另一个栈的栈底为数组的末端，即下标为数组长度 n - 1 处，这样两个栈如果增加元素，就是两端点向中间移动，如图所示。
两栈共享
top1 和 top2 是栈 1 和栈 2 的栈顶指针，只要二者的值不相等，两个栈就可以进行入栈操作。当 top1 等于 -1 时，栈 1 为空；当 top2等于 n 时，栈 2 为空。当 top2 - top1 = 1 时，栈就满了。
两栈共享空间的代码如下：
typedef struct {
int data[MAXSIZE];
int top1;
int top2; }
SqDoubleStack;
对于两栈共享空间的插入方法，除了要插入元素值参数外，还需要有一个判断是栈 1 还是栈 2 的栈号参数。代码如下：
boolean push(SqDoubleStack *s, int e, int stackNumber) {
if (s->top2 - s->top1 == 1) { /* 栈满 */
return false; }
if (stackNumber == 1) {
s->data[++s->top1] = e;
}
else if (stackNumber == 2) {
s->data[--s->top2] = e;
}
return true;
}
出栈方法的代码
boolean pop(SqDoubleStack *s, int *e, int stackNumber) {
if (stackNumber == 1) {
if (s->top1 == -1)
return false;
*e = s->data[s->top1--]; }
else if (stackNumber == 2) {
if (s->top2 == MAXSIZE)
return false;
*e = s->data[s->top2++];
}
return true;
}
两栈共享通常用于两个栈的空间需求具有相反关系时，也就是一个栈增长时另一个栈在缩短。就像买卖股票一样，一个人买入时，一定有另一个人在做卖出操作。这样使用两栈共享空间存储方法才有比较大的意义。
两栈共享只针对两个具有相同数据类型的栈。
06
栈的链式存储结构
栈的链式存储结构，简称为链栈。
由于单链表有头指针，而栈顶指针也是必须的，所以把栈顶放在链表的头部。另外，由于已经有了栈顶在头部，所以单链表中的头结点就不需要了。
对于链栈来说，基本不存在栈满的情况，因为只要内存有空间，链表就可以一直添加结点。
链栈的结构代码如下：
/**
* Node结点 */
typedef struct StackNode {
int data;
struct StackNode *next;
} StackNode, *pStackNode;
typedef struct LinkStack {
pStackNode top; /* 栈顶指针 */
int count;
} LinkStack;
07
栈的链式存储结构—进栈操作
假设新结点 s 的值为 e，top 为栈顶指针，将 s->next 指向当前栈顶结点，栈元素个数加 1。
boolean push(LinkStack *s, int e) {
pStackNode pNewNode = (pStackNode)malloc(sizeof(StackNode));
if (NULL == newNode)
return false;
pNewNode->data = e;
/* 把当前栈顶元素赋值给新结点的直接后继 */
pNewNode->next = s->top;
/* 新结点作为栈顶 */
s->top = pNewNode;
s->count ++;
return true;
}
08
栈的链式存储—出栈操作
出栈的操作步骤：先用一个变量 p 来存储要删除的栈顶结点，将栈顶指针 改为 p->next，释放 p。
boolean pop(LinkStack *s, int *e) { if (stackEmpty(*s)) { return false; } pStackNode pNode = s->top; *e = pNode->data; s->top = pNode->next; free(pNode);
s->count--; return true; }
上面出栈操作中，用到判断栈是否为空，那么链栈是怎样判断是否为空栈的呢？
boolean stackEmpty(LinkStack *s) {
if (s->top->next == NULL)
return true;
else
return false;
}
09
总结
从链栈的进栈和出栈操作，可以看出时间复杂度都为 O(1)。
对比顺序栈和链栈，它们的时间复杂度是一样的，对于空间性能，顺序栈需要先确定一个固定的长度，可能会造成空间浪费，但是它在存取时定位很方便，而链栈则要求每个元素都有指针域，无形中增加了内存开销，但是链栈对长度是没有限制的。
所以它们的区别和线性表的顺序存储以及链式存储的区别是一样的：如果栈中的元素个数变化较大，那么使用链栈再合适不过，反之，如果元素个数变化较小，使用顺序栈会更好一些。