第三章__栈和队列
3.1、栈和队列的定义和特点
3.1.1、栈的定义和特点
定义：
栈是是一种特殊的线性表，是限定在表尾进行插入或删除操作的线性表。又称为后进先出的线性表，简称LIFO
相关概念：
- 表尾（即an端）称为栈顶Top；表头（即a1端）称为栈底Base
- 插入元素到栈顶（即表尾）称为入栈
- 从栈顶（即表尾）删除最后一个元素的操作，称为出栈
入栈的操作示意图
出栈示意图
思考：a、b、c3个元素，入栈顺序是a、b、c，则他们的出栈顺序有几种可能：
栈的相关概念：
- 定义：限定只能在表的一端进行插入和删除运算的线性表（只能在栈顶操作）
- 逻辑结构： 与同线性表相同，仍为一对一关系
- 存储结构：用顺序栈或链栈存储均可，但以顺序栈更常见
- 运算规则：只能在栈顶运算，且访问结点时依照后进先出（LIFO）的原则
- 实现方式：关键是编写入栈和出栈函数，具体实现依顺序或链栈的不同而不同。
栈与一般线性表的不同：
栈与一般线性表的区别：仅在于运算规则不同
3.1.2、队列的定义和特点
- 队列是一种先进先出（FIFO）的线性表。在表的一端插入（表尾），在另一端（表头）删除
队列相关概念：
- 定义：只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表
- 逻辑结构：与同线性表相同，仍为一对一关系
- 存储结构：顺序队或链队，以循环顺序队列更常见
- 运算规则：只能在队首和队尾运算，且访问结点时依照先进先出的原则。
- 实现方式：关键时掌握入队和出队操作，具体实现依顺序队或链队的不同而不同
3.2、案例引入
3.2.1、案例一：进制转换
十进制整数N向其它进制数d（二、八、十六）的转换是计算机实现计算的基本问题
- 转换法则：除以d倒取余
- 原理为：n = (n div d) * d + n mod d ,其中div为整除运算，mod为求余运算
例：把十进制数1348= 转换成八进制数为2504。
| N | N div 8 | N mod 8 |
| 1348 | 168 | 4 |
| 168 | 21 | 0 |
| 21 | 2 | 5 |
| 2 | 0 | 2 |
3.2.2、案例二：括号匹配的检验
- 假设表达式中允许包含两种括号：圆括号和方括号
- 其嵌套的顺序随意，即：
- ([] ()) 或 [ ( [] [] ) ]为正确格式
- [ ( ] ) 或 （ [ () ) 或 ( ( ) ])为错误格式
3.2.3、案例三：表达式求值
表达式求值是程序设计语言编译中的一个基本问题，在实现时也需要运用栈。
实现：我们会使用算法——算符优先算法（运算符优先级确定运算顺序的表达式求值算法）
- 表达式组成
- 操作数：常数、变量
- 运算符：算术运算符、关系运算符和逻辑运算符
- 界限符：左右括弧和表达式结束符
- 任何一个算术表达式都是由操作数（常数、变量）、算术运算符（+、-、*、/）和界限符（括号、表达式结束符 ’#‘、虚设的表达式起始符'#'）组成。
3.2.4、案例四：舞伴问题
假设在舞会上，男士和女士各自排成一队，舞会开始时，依次从男队和女队的队头个出一人配成舞伴。如果两队初始人数不同，则较长的那一队未配对者等待下一轮舞曲。
