第三章__栈和队列3.1、栈和队列的定义和特点3.1.1、栈的定义和特点定义：

栈是是一种特殊的线性表，是限定在表尾进行插入或删除操作的线性表。又称为后进先出的线性表，简称LIFO

相关概念：

  • 表尾（即an端）称为栈顶Top；表头（即a1端）称为栈底Base
  • 插入元素到栈顶（即表尾）称为入栈
  • 从栈顶（即表尾）删除最后一个元素的操作，称为出栈

入栈的操作示意图

出栈示意图

思考：a、b、c3个元素，入栈顺序是a、b、c，则他们的出栈顺序有几种可能：

栈的相关概念：

  1. 定义：限定只能在表的一端进行插入和删除运算的线性表（只能在栈顶操作）
  2. 逻辑结构： 与同线性表相同，仍为一对一关系
  3. 存储结构：用顺序栈或链栈存储均可，但以顺序栈更常见
  4. 运算规则：只能在栈顶运算，且访问结点时依照后进先出（LIFO）的原则
  5. 实现方式：关键是编写入栈和出栈函数，具体实现依顺序或链栈的不同而不同。

栈与一般线性表的不同：

栈与一般线性表的区别：仅在于运算规则不同

3.1.2、队列的定义和特点

  • 队列是一种先进先出（FIFO）的线性表。在表的一端插入（表尾），在另一端（表头）删除

队列相关概念：

  1. 定义：只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表
  2. 逻辑结构：与同线性表相同，仍为一对一关系
  3. 存储结构：顺序队或链队，以循环顺序队列更常见
  4. 运算规则：只能在队首和队尾运算，且访问结点时依照先进先出的原则。
  5. 实现方式：关键时掌握入队和出队操作，具体实现依顺序队或链队的不同而不同

3.2、案例引入3.2.1、案例一：进制转换

十进制整数N向其它进制数d（二、八、十六）的转换是计算机实现计算的基本问题

  • 转换法则：除以d倒取余
  • 原理为：n = (n div d) * d + n mod d ,其中div为整除运算，mod为求余运算

例：把十进制数1348= 转换成八进制数为2504。

NN div 8N mod 8
13481684
168210
2125
202

3.2.2、案例二：括号匹配的检验

  • 假设表达式中允许包含两种括号：圆括号和方括号
  • 其嵌套的顺序随意，即：
    • ([] ()) 或 [ ( [] [] ) ]为正确格式
    • [ ( ] ) 或 （ [ () ) 或 ( ( ) ])为错误格式

3.2.3、案例三：表达式求值

表达式求值是程序设计语言编译中的一个基本问题，在实现时也需要运用栈。

实现：我们会使用算法——算符优先算法（运算符优先级确定运算顺序的表达式求值算法）

  • 表达式组成
    • 操作数：常数、变量
    • 运算符：算术运算符、关系运算符和逻辑运算符
    • 界限符：左右括弧和表达式结束符
  • 任何一个算术表达式都是由操作数（常数、变量）、算术运算符（+、-、*、/）和界限符（括号、表达式结束符 ’#‘、虚设的表达式起始符’#’）组成。

3.2.4、案例四：舞伴问题

假设在舞会上，男士和女士各自排成一队，舞会开始时，依次从男队和女队的队头个出一人配成舞伴。如果两队初始人数不同，则较长的那一队未配对者等待下一轮舞曲。