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

第三章__栈和队列

3.1、栈和队列的定义和特点

3.1.1、栈的定义和特点

定义:

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

相关概念:

  • 表尾(即an端)称为栈顶Top;表头(即a1端)称为栈底Base
  • 插入元素到栈顶(即表尾)称为入栈
  • 栈顶(即表尾)删除最后一个元素的操作,称为出栈

入栈的操作示意图

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

出栈示意图

数据结构(严蔚敏版)——栈和队列(一)【栈和队列的定义和特点】插图1

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

数据结构(严蔚敏版)——栈和队列(一)【栈和队列的定义和特点】插图2

栈的相关概念:

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

栈与一般线性表的不同:

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

数据结构(严蔚敏版)——栈和队列(一)【栈和队列的定义和特点】插图3

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、案例三:表达式求值

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

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

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

数据结构(严蔚敏版)——栈和队列(一)【栈和队列的定义和特点】插图4

3.2.4、案例四:舞伴问题

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

文章来源于互联网:数据结构(严蔚敏版)——栈和队列(一)【栈和队列的定义和特点】

THE END
分享
二维码