### 定义
只能在表的一端(栈顶)进行插入和删除运算的线性表
### 逻辑结构
一对一关系
### 存储结构
用顺序栈或链栈存储均可，但以顺序栈更常见
### 运算规则
只能从栈顶运算，且访问结点时依照后进先出(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.
报错，返回操作系统。
1.
分更大的空间，作为栈的存储空间，将原栈的内容移入新栈。
### 初始化
（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 S)
{
return S.top-S.base;
}
~~~
### 清空顺序栈
~~~
Status ClearStack(SqStack S)
{
if(S.base)S.top = S.base;
return OK;
}
~~~
### 销毁顺序栈
~~~
Status DestroyStack(SqStack &S)
{
if(S.base)
{
delete S.base;
S.stacksize = 0;
S.base = S.top =NULL;
}
return OK;
}
~~~
### 顺序栈进栈
（1）判断是否栈满，若满则出错
（2）元素e压入栈顶
（3）栈顶指针加1
~~~
Status Push(SqStack &S,SElemType e)
{
if(S.top - S.base == S.stacksize)//栈满
return ERROR;
*S.top=e;
S.top++;
return OK;
}
~~~
### 顺序栈出栈
(1)判断是否栈空。若空则出错
（2）获取栈顶元素e
（3）栈顶指针减1
Status Pop(SqStack &S,SElemType &e)
{
if(S.top == S.base)//栈空
return ERROR；
–S.top;
e= *S.top;
return OK;
}
### 取顺序栈栈顶元素
判断是否为空栈，若为空则返回错误
否则通过栈顶指针获取栈顶元素
~~~
Status GetTop(SqStack S,SElemType &e)
{
if(S.top == S.base)
return ERROR;//栈空
e = *(S.top-1);
return OK;
}
~~~
