定义
只能在表的一端(栈顶)进行插入和删除运算的线性表
逻辑结构
一对一关系
存储结构
用顺序栈或链栈存储均可，但以顺序栈更常见
运算规则
只能从栈顶运算，且访问结点时依照后进先出(LIFO)或后进后出(FILO)的原则
实现方法
关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同
基本操作
- 入栈
- 出栈
- 读栈顶元素值
- 建栈
- 判断栈满
- 栈空
栈与一般线性表的区别
栈是一种特殊的线性表，它只能在表的一端(栈顶)进行插入或删除运算
| ** | 一般线性 表 | 栈 |
|---|---|---|
| 逻辑结构 | 一对一 | 一对一 |
| 存储结构 | 顺序表、链表 | 顺序栈、链栈 |
| 运算规则 | 随机、顺序存储 | 后进先出 |
它们之间在于运算规则不同
我们在平常的程序设计中，如果需要按照保存数据时相反的顺序来使用数据，可以利用栈来实现。
顺序栈的表示
#define MAXSIZE 100
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
stacksize 指示栈的最大容量；base为栈底指针，它始终指向栈底位置，若base的值为NULL，则表明栈结构不存在；top为栈顶指针，其初值指向栈底，即top=base可作为栈空的标记。每当插入新的栈顶元素时，指针top增加1；删除栈顶元素时，指针top减1.因此，非空栈中的栈顶指针始终在栈顶元素的下一个位置上。
base == top 是栈空的重要标志
栈满时的处理方法
报错，返回操作系统。
分更大的空间，作为栈的存储空间，将原栈的内容移入新栈。
初始化
（1）分配空间并检查空间是否分配失败，若失败则返回错误
（2）设置栈底和栈顶指针
S.top = S.base;
（3）设置栈大小
【算法描述】
Status InitStack(SqStack &S)
{
S.base=new SElemType[MAXSIZE];
if(!S.base) return OVERFLOW;
S.top=S.base;
S.stackSize=MAXSIZE;
return OK;
}
判断顺序栈是否为空
bool StackEmpty(SqStack S)
{
if(S.top == S.base) return true;
else
return false;
}
求顺序栈的长度
int StackLength(SqStack 