首页 > 其他分享 >数据结构(严蔚敏版)——栈和队列(一)【栈和队列的定义和特点】

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

时间:2022-10-13 15:22:54浏览次数:64  
标签:顺序 线性表 队列 运算符 数据结构 严蔚敏版 表达式 运算

第三章__栈和队列

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

3.1.1、栈的定义和特点

定义:

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

相关概念:

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

入栈的操作示意图

image-20221012215223918

出栈示意图

image-20221012215122869

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

image-20221012215655461

栈的相关概念:

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

栈与一般线性表的不同:

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

image-20221012220646138

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

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

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

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

image-20221012225013051

3.2.4、案例四:舞伴问题

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

标签:顺序,线性表,队列,运算符,数据结构,严蔚敏版,表达式,运算
From: https://www.cnblogs.com/javaxiaohao/p/16788248.html

相关文章

  • 【算法】214-每周一练 之 数据结构与算法(Queue)
    这是第二周的练习题,这里补充下咯,五一节马上就要到了,自己的计划先安排上了,开发一个有趣的玩意儿。下面是之前分享的链接:  ​​【算法】200-每周一练之数据结构与算法(Stac......
  • 【算法】213-每周一练 之 数据结构与算法(LinkedList)
    这是第三周的练习题,原本应该先发第二周的,因为周末的时候,我的母亲大人来看望她的宝贝儿子,哈哈,我得带她看看厦门这座美丽的城市呀。这两天我抓紧整理下第二周的题目和答案,下面......
  • R语言中数据结构知识补充以及常见错误习惯
    读书笔记:R语言中数据结构基础知识补充R语言中常见错误习惯大小写使用错误,函数名的大小写不同表示的功能也不同。引号使用错误,R包的名称前后需要引号包围,否则报错。......
  • 数据结构(二)线性表
    线性表基础线性表的基本操作初始化操作销毁操作引用(使用)型操作加工型操作线性表主要有两种,一种是顺序结构,也就是常说的数组,还有一直是链式结构,也就是链表这里,我们......
  • 通过消息队列MQ实现组件解耦
    ​当业务系统的规模扩大时,也会增加系统架构的复杂度,在架构设计时对系统进行分层与解耦能够避免多个组件之间的性能不足、负载高、任务处理堆栈长及组件故障等风险。    ......
  • JAVA并发之阻塞队列浅析
    JAVA并发之阻塞队列浅析背景因为在工作中经常会用到阻塞队列,有的时候还要根据业务场景获取重写阻塞队列中的方法,所以学习一下阻塞队列的实现原理还是很有必要的。(PS:不深......
  • ajax 请求队列解决方案并结合elementUi做全局加载状态
    全本下载地址ajax文件入口可发送blob文档流,form表单与通常json解决方案结合消息队列(messagelist)与elementUi(Loading)制作请求加载方案拥有post默认请求......
  • 队列实现回文
      #include<stdio.h>#include<queue>#include<cstring>#defineMAXSIZE100usingnamespacestd;intmain(){queue<char>q;chara[MAXSIZE];......
  • 数据结构第二次上机
    #include<stdio.h>#include<stdlib.h>typedefstructLinkNode{  intdata;  structLinkNode*next;}LinkNode,*LinkList;voidInitLinkList(LinkList&L)/......
  • C++ 循环队列(基于数组)
    Code: classCircularQueue{private://容量intC;//容器vector<int>els;//队头指针intfront;//队尾指针intrear;......