数据结构：栈和队列

栈和队列

栈和队列是软件设计中常用的两种数据结构，逻辑结构和线性表相同。

特点：

栈： "先进后出"
队列："先进先出"

1.栈的定义及基本运算

栈（Stack）是限制在一端进行插入和删除的线性表。允许插入和删除的一端成为栈顶（Top）,另一个固定端成为栈底。当表中没有元素时成为空栈。

栈常见的集中运算：
（1）初始化 Init_Stack(s)

初始条件 ：栈(s)不存在。
操作结果：创建一个空栈（s）

（2）判空 Empty_Stack(s)

初始条件：栈(s)已存在
操作结果：若栈(s)为空返回 1，否则返回 0

（3）入栈 Push_Stack(s , x)

初始条件：栈(s)已存在
操作结果：在栈(s)的顶部插入一个新的元素x , x 成为新的栈顶元素。栈发生变化

（4）出栈 Pop_Stack(s)

初始条件：栈(s)存在且非空
操作结果：栈(s)的栈顶元素从栈中移除，栈中减少一个元素，栈发生变化

（5）读取栈顶 Top_Stack(s)

初始条件：栈(s)存在且非空
操作结果：栈顶元素作为结果返回，栈不发生变化

存储结构和基本运算

由于栈是运算受限的线性表，因此线性表的存储结构对栈也是适用的，只是操作不同
（1）顺序栈
定义：利用顺序存储方式实现的栈称为 顺序栈
类似顺序表的定义，栈中的数据元素用一个预设的足够长的一维数组来实现：
datatype data[MAXSIZE],栈底位置可以设置在数组的任意一个端点，而栈顶是随着插入和删除而变化的。通常将 0 下标端设为栈底，这样空栈时栈顶指针top = -1 ; 入栈时，栈顶指针 +1 ， 出栈时栈顶指针 -1 。

两点说明：

1. 对于顺序栈 ， 入栈时，首先判断栈是否满了，栈满的条件为 s->top == MAXSIZE -1 , 栈满时，不能入栈，否则会出现控件溢出，引起错误，称为上溢。
2. 出栈和读取栈顶元素操作， 先判断栈是否为空，为空是不能操作，否则产生错误。通常栈空时常作为一种控制转移的条件。
   （2）链栈