数据结构 3-0 栈与队列总结_林北不要忍了的博客-程序员秘密

技术标签: 数据结构  笔记总结  

总结

栈和队列都可以看作对输入输出做限制的线性表。其中栈是限制了输入和输出只能在一端进行的线性表,可以将其看作向箱子里面摞书,想要取出最下面的书必须要先拿出上面的书,对应栈先进后出的特点。而队列正如其名,可以拿排队来理解,先来的在队伍前面,所以理所应当先出去,正好对应队列的先进先出的特点。书上侧重于链式结构的实现,这一点不难解释,顺序结构虽然对先学数组的我们很友好,但是在实际应用起来,光一个内存限制问题就够喝一壶了,所以链式结构的优点就凸显了出来,栈和队列都是在链表的两端做修改,所以并没有中间部位的修改,正好避开了链式结构遍历麻烦的缺点,用首尾指针来指向两端,链式结构完美契合了栈和队列的需求。实现上链式结构更好,但是顺序关系更考察对结构的理解,尤其是下标判断这类问题。
栈的实现:https://blog.csdn.net/weixin_43849505/article/details/106963008
共享栈实现:https://blog.csdn.net/weixin_43849505/article/details/106963443
队列链式实现:https://blog.csdn.net/weixin_43849505/article/details/107009683
队列顺序实现:https://blog.csdn.net/weixin_43849505/article/details/107014544

典型题

在这里插入图片描述
统考题出的确实有水平,题目很妙,乍一看看不通什么意思,一点一点理顺,目标是让火车顺序驶出,进入的火车是乱序的,我们要做的就是把火车顺序用数据结构来调整成可以顺序出去,中间的轨道条数有很多,每一条轨道都可以停很多量火车,所以只需要让小的停在前面,大的停在后面就可以了。顺序读入驶入顺序,如果下一个数比当前的数小就换一条轨道,按照这个方法,最后需要4条轨道,分别为:
①9 8
②6 7 5 4
③3 2
④1

在这里插入图片描述
这道题涉及到了中缀表达式转换为后缀表达式,转换的步骤为:初始化一个用于存放运算符的栈,栈底元素为优先级最低的元素,存储一个记录有优先级的表格,顺序扫描中缀表达式,遇见操作数则直接输出,遇见操作符则进行比较,如果扫描到的运算符优先级高于栈顶元素就直接入栈,如果当前扫描到的运算符的优先级比栈顶元素的优先级低,就输出栈顶运算符直到扫描到的运算符优先级高于栈顶元素。基于这个方法再来看这道题,一开始栈中只有起始符#,其优先级最低,运算符栈的变化情况为:

#+
#
#-
#-*
#-*(
#-*((
#-*((+
#-*((
#-*(
#-*(\
#-*(
#-*(-
#-*(
#-*
#-

#+

最多存放了6个元素,但只有五个运算符

在这里插入图片描述
与上面的题目一个考点,都是表达式之间的转换。
在这里插入图片描述
这里顺便补充一下中缀表达式前缀表达式之间的转换:初始化一个存放有优先级的表格和一个存放运算符的栈,栈底为优先级最低的运算符,从右向左扫描中缀表达式,遇见数就直接压入结果栈,遇见操作符则和当前的栈顶元素比较优先级,如果当前操作符优先级大于栈顶元素优先级就入栈,小于则输出栈顶元素到结果栈直到栈顶元素优先级小于当前操作符,最后输出结果栈即可。

★此外还有一类题目,叫做特殊矩阵压缩,即为了节省存储空间,将一些特殊的二维数组保存到一维数组中去,分为以下几种情况:
①对称矩阵
二维数组中的元素关于主对角线对称,如果用二维数组存储,里面一半的元素时重复的,所以将其转换为一维数组存放,不存放重复元素,转换前后的对应关系为:

在这里插入图片描述
在这里插入图片描述
②三角矩阵
即上面一半是同一元素或者下面一半全是同一元素,存储思路与对称矩阵相似,不同之处在于存储完变化的部分之后,再在一维数组最后补上相同元素,对应关系为:
在这里插入图片描述
在这里插入图片描述在这里插入图片描述在这里插入图片描述
在这里插入图片描述
③三对角矩阵
也称带状矩阵,根据“带”的宽度,就叫做几对角矩阵。三对角矩阵中,非零元素都集中在以主对角线为中心的三条的区域,其余元素都是零,对应关系为:k=2i+j-3
在这里插入图片描述在这里插入图片描述
④稀疏矩阵
当很大的矩阵里面只存了很少的元素时,存储整个矩阵很浪费空间,所以换用三元组(行位置、列位置、存储数据)或者十字链表法存储,但是这样处理后就失去了随机存取的特性。

最好的办法就是代数,拿几个特殊位置去带入选项验证,比如前三个元素、对角线上的元素、最后一个元素

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_43849505/article/details/107072493

智能推荐

Angular杂谈系列2-Angular2升级Angular4指南_airen7736的博客-程序员秘密

    什么什么?Angular4都发布了,之前不都才Angular2的么?又要推翻重来,啊?  那当然不是,Angualr4只是一个版本号而已,本质上还是Angular2;以后,谷歌把新版本的Angular称为Angular,而之前的1.x版本叫做AngularJs1.x。  Angular4的更新内容大致包括以下几个方面。  1.更小、更快   ...

从 0 学习 Python 0 - 100 大合集总结_微笑很纯洁的博客-程序员秘密

各位读者好,今天的文章是对 Python 阶段性学习的一个小结,同时附上相应目录,方便大家查阅。恭喜大家在 Python 100 天的学习计划中没有掉队,我们已经完成了一个小目标啦。在我...

《惢客创业日记》2019.11.11(周一) 一次纠结的人性体验(一)_敦厚的曹操的博客-程序员秘密

  今天是双十一,昨天晚上我和媳妇一直从晚上九点熬到了凌晨十二点半,我们俩就像是突击考试一样,一人捧着一个手机忙个不停。写到这里,您也应该知道是购物了,但与其说是购物,不如说是在算数学题。  记得去年双十一时,我还在日记中发了一痛感慨,而且还对惢客的315粉丝节做了一个全新的规划和畅想,而今年则有了很大的不同,因为,我接触了一些产品相关知识后,不再单纯的感慨,而是需要更好的体验和学习...

调试读卡器时的一些问题【1】_人生苦短,我学python,的博客-程序员秘密

项目场景:调试一款芯片作为读卡器使用将一款芯片的代码一直到另一款新芯片上,实现的功能是7816读卡器功能<技术小白,错误之处,烦请斧正>问题描述1、在初始化枚举时候对于主机下发的命令不能正确返回响应2、正确返回ATR后,主机不下发 61 指令,所以无法进行ETU自校验Bus Hound 6.01 capture on Windows Vista Service Pack 1 (x64). Complements of www.perisoft.net Device - Devi

[手把手系列之]Docker 部署 vue 项目_Web全栈开发的博客-程序员秘密

Docker 部署 vue 项目1.写在前面:Docker 作为轻量级虚拟化技术,拥有持续集成、版本控制、可移植性、隔离性和安全性等优势。本文使用Docker来部署一个vue的前端应用,并尽可能详尽的介绍了实现思路和具体步骤,以方便有类似需要的同学参考。Docker 是一个开源的应用容器引擎,让开发者可以打包他们的应用以及依赖包到一个可移植的容器中,该容器包含了应用程序的代码、运行环境、依赖...

Apache 与 Tomcat 整合_sun0322的博客-程序员秘密

使用 mod_jk当已经安装mod_jk,但是这次新添加的工程没有反应时(不加8080就不好用) 1修改 httpd.conf文件在里面添加你的工程jkMount    /Test     tom1jkMount    /Test/*   tom1 2重新启动apache   搜索apachectl所在目录执行命令apachectl restart

随便推点

2021最新出炉的,Java程序员极力推荐的springboot全家桶干货系列_Java世界上最好的语言的博客-程序员秘密

最近,在某平台收到读者反馈,希望能整理出一些有关spring的干货,主要是springboot有关的面试题和书籍,所以,应广大爱学习人士的需求,网罗了一些资料,并将这些资料分享给更多有需要的人。高频面试题:1、什么是 Spring Boot?2、Spring Boot 有哪些优点?3、什么是 JavaConfig?4、如何重新加载 Spring Boot 上的更改,而无需重新启动服务器?5、Spring Boot 中的监视器是什么?6、如何在 Spring Boot 中禁用 Actuator

Python实现九九乘法表_胖困困的博客-程序员秘密_python编程九九乘法表

九九乘法表有四种展现形式1.左下三角形:方法1:for循环实现for i in range(1, 10): for j in range(1, i + 1): print(f'{j}* {i}={i*j}' , end='\t') print()方法2:while循环实现i=1while i <10: j=1 while j<i+1: print(f'{j}* {i}={i * j}', end='\t'.

C# 学习笔记(一)_weixin_30568715的博客-程序员秘密

一直很好奇 C# 与 .Net 的关系,之前也没有接触过。因为项目需要,开始学习 .Net 框架。今天去书市借了一本 Deitel 的《Visual C#2012 大学教程(第五版)》,这里做一下学习笔记。一、 .NET、CLR、MSIL 之间的区别与联系.Net 是一个面向 Web 服务的开发平台,可以用来快速的搭建 C#、VC++、VB 等程序。CLR(公共语言运行时) 是执行 .Net ...

【Web3 系列开发教程——创建你的第一个 NFT(3)】开始创建 NFT_前端修罗场的博客-程序员秘密

本文将引导你使用以太坊和星际文件系统(IPFS)编写和部署不可替代()代币智能合约。星际文件系统IPFS是一个旨在。它是一种内容可寻址的对等超媒体分发协议。在IPFS网络中的节点构成一个分布式文件系统。它是一个开放源代码项目,自2014年开始由协议实验室在开源社区的帮助下发展。其最初由JuanBenet设计。ERC721是针对不可置换Token的智能合约标准接口,(non-fungiletokens)不可置换Token简称NFTs。在Goerli测试网络上创建和部署。...

HashMap源码阅读jdk1.7_leonliu06的博客-程序员秘密

HashMap源码(jdk1.7)阅读HashMap类主要由一个Entry数组Entry<K,V>[] table构成;1. put方法 public V put(K key, V value) { // 如果table为空,则初始化 if (table == EMPTY_TABLE) { inflateTable(threshold); } // 这里可以看出HashMap的key可以为空

数据导入如何不重复php,_php 如何在导入Excel数据时检查Mysql数据库内容是否存在,避免重复录入?..._李战阳的博客-程序员秘密

excel怎么让表格不出现重复数据库http://jingyan.baidu.com/article/37bce2be1abcd41002f3a2d6.htmlexcel如何删除单元格内重复的数据库代码来处理,公式不会如何判断导入数据库的Excel内容是否有重复记录条件格式,检查重复值如何判断导入数据库的excel表是否有重复记录选中单--单击[开始]--[条件格式]--[突出.....]--[重...

推荐文章

热门文章

相关标签