数据结构(严蔚敏版)第三章——栈和队列(一)【栈和队列的定义和特点】

简介: 3.1、栈和队列的定义和特点3.1.1、栈的定义和特点3.1.2、队列的定义和特点3.2、案例引入3.2.1、案例一:进制转换3.2.2、案例二:括号匹配的检验3.2.3、案例三:表达式求值3.2.4、案例四:舞伴问题

第三章__栈和队列

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。

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、案例四:舞伴问题

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

目录
相关文章
|
4天前
栈的几个经典应用,真的绝了
文章总结了栈的几个经典应用场景,包括使用两个栈来实现队列的功能以及利用栈进行对称匹配,并通过LeetCode上的题目示例展示了栈在实际问题中的应用。
栈的几个经典应用,真的绝了
|
1天前
|
负载均衡 网络协议 安全
DKDP用户态协议栈-kni
DKDP用户态协议栈-kni
|
1天前
|
负载均衡 网络协议 安全
DPDK用户态协议栈-KNI
DPDK用户态协议栈-KNI
|
1天前
|
测试技术
【初阶数据结构篇】栈的实现(附源码)
在每一个方法的第一排都使用assert宏来判断ps是否为空(避免使用时传入空指针,后续解引用都会报错)。
|
4天前
|
存储 网络协议 Linux
用户态协议栈06-TCP三次握手
用户态协议栈06-TCP三次握手
|
1天前
|
测试技术
【初阶数据结构篇】队列的实现(赋源码)
首先队列和栈一样,不能进行遍历和随机访问,必须将队头出数据才能访问下一个,这样遍历求个数是不规范的。
|
4天前
|
算法
【数据结构与算法】优先级队列
【数据结构与算法】优先级队列
6 0
|
4天前
|
存储 算法
【数据结构与算法】队列(顺序存储)
【数据结构与算法】队列(顺序存储)
5 0
【数据结构】栈和队列
【数据结构】栈和队列
|
6天前
|
算法 C语言 C++
【practise】栈的压入和弹出序列
【practise】栈的压入和弹出序列