第三章__栈和队列
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、案例四:舞伴问题
假设在舞会上,男士和女士各自排成一队,舞会开始时,依次从男队和女队的队头个出一人配成舞伴。如果两队初始人数不同,则较长的那一队未配对者等待下一轮舞曲。
标签:顺序,线性表,队列,运算符,数据结构,严蔚敏版,表达式,运算 From: https://www.cnblogs.com/javaxiaohao/p/16788248.html