栈的概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。
进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈。数据在栈顶进入。出栈：栈的删除操作叫做出栈。数据也在栈顶出去。
栈的结构
链式栈
如果以尾做栈顶，进行尾插尾删，效率较低（要进行遍历），除非设计成双向链表。
如果以头做栈顶，头插头删，效率则较高，可以设计成单链表。
数组栈
压栈出栈都比较方便，且CPU高速缓存命中率更高。
故而两种结构都可以使用，非要选一种的话，更建议使用数组栈，结构更好。
小习题
1.一个栈的初始状态为空。现有元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈。则元素出栈的顺序是（）。
A.12345ABCDE
B.EDCBA54321
C.ABCDE12345
D.54321EDCBA
2.若进栈序列为1、2、3、4。进栈过程中可以出栈，则下列不可能的一个出栈序列是（）
A.1、4、3、2
B.2、3、4、1
C.3、1、4、2
D.3、4、2、1
答案：1.B 2.C
第二题解析
在进栈的过程中可以随时出栈，所以出栈序列可以有多种可能性。用相同的思路判断即可得到答案C。
栈的结构体定义
#include <stdlib.h> #include <stdio.h> #include <assert.h> #include <stdbool.h> //栈的结构体定义 typedef int STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }ST;
基本接口函数
//基本接口函数 void StackInit(ST* ps); void StackDestroy(ST* ps); void StackPush(ST* ps, STDataType x); void StackPop(ST* ps); STDataType StackTop(ST* ps);//取出栈顶元素 int StackSize(ST* ps);//计算栈中有多少个元素 bool StackEmpty(ST* ps);//判断栈是否为空
栈的初始化函数
初始化函数时，栈顶top的初始化可以有两种方式。在数组栈中，top表示下标。
那么top在数组栈中初始化的两种方式分别是；top = -1；top = 0；
第一种的初始化意味着top指向的是栈顶数据；
第二种的初始化意味着top指向的是栈顶数据的下一位。
end
