当前位置：网站首页>栈、队列和数组

栈、队列和数组

2022-08-02 18:48:00 【没有人会真的躺平】

3.1-1栈的基本概念

栈的定义

在这里插入图片描述

栈顶、栈底

在这里插入图片描述

栈的基本操作

在这里插入图片描述

栈的常考题型

在这里插入图片描述

3.1-2栈的顺序存储实现

第一种栈的实现方式

顺序栈的定义

在这里插入图片描述

顺序栈的初始化操作

在这里插入图片描述

顺序栈的进栈操作

在这里插入图片描述

顺序栈的出栈操作

顺序栈读栈顶元素操作

在这里插入图片描述

第二种栈的实现方式

在这里插入图片描述

第一种方法判栈满是 top==MaxSize-1;

共享栈

在这里插入图片描述

总结

在这里插入图片描述

3.1-3栈的链式存储实现

链栈本质上是只允许一端增加、删除元素的单链表

进栈

在这里插入图片描述

出栈

在这里插入图片描述

链栈的定义

在这里插入图片描述

3.2-1队列的基本概念

队列的定义

在这里插入图片描述

队列的基本操作

在这里插入图片描述

3.2-2 队列的顺序实现

队列顺序实现（通过数组）

在这里插入图片描述

初始化操作

在这里插入图片描述

入队操作

在这里插入图片描述

逻辑上相当于循环队列

如果不空着一个，那么rear=front就不知道是空还是满了
在这里插入图片描述

判定队列已满或者已空

空一个存储空间

在这里插入图片描述

设置队列长度变量size

在这里插入图片描述

设置tag，两个条件

在这里插入图片描述

有些区别的实现队列的方法，rear指向队尾元素，之前是rear指向队尾元素的后一个位置

在这里插入图片描述
指向队尾元素，由于刚开始没有队尾元素，所以可以指向n-1即 9 这个位置.

无论rear是指向队尾元素还是指向队尾元素的下一个位置，都必须采取方案才能避免判空判满的条件相同。

3.2-3 队列的链式实现

队列的链式实现

在这里插入图片描述

初始化（带头节点）

在这里插入图片描述

初始化（不带头节点）

在这里插入图片描述

入队（带头结点）

在这里插入图片描述

入队（不带头结点）

在这里插入图片描述

出队（带头结点）

在这里插入图片描述

出队（不带头结点）

在这里插入图片描述

队列满的条件

在这里插入图片描述

3.2-4 双端队列

栈、队列、双端队列都是插入和删除受限制的线性表

在这里插入图片描述

双端队列如果只从某一段进行输入输出，那他就退化成了一个栈，所以只要栈里面出现的合法的输出序列，在双端队列里面肯定也可以出现。

栈

在这里插入图片描述

输入受限的双端队列（入）

栈中合法的序列，双端队列中一定也合法，所以继续依次判断栈中不合法的就行了
在这里插入图片描述

输出受限的双端队列（出）

在这里插入图片描述

3.3-1栈在括号匹配中的应用

三种不匹配的情况演示

在这里插入图片描述

判定流程

在这里插入图片描述

算法实现

在这里插入图片描述

3.3-2栈在表达式求值中的应用（上）

中缀、后缀、前缀表达式

在这里插入图片描述

中缀转后缀（手算）举例

例1

在这里插入图片描述

例2(引出左优先原则)

左优先原则可保证最后生成的后缀表达式唯一，且从左到右的运算符恰好与运算的先后顺序相对应。
在这里插入图片描述

后缀表达式的计算（手算）引出使用栈进行机算

在这里插入图片描述

后缀表达式的计算（机算）（使用栈模拟运算过程）

在这里插入图片描述

中缀转前缀（手算）引出右优先原则

在这里插入图片描述

前缀表达式计算（从右往左）

在这里插入图片描述

总结

在这里插入图片描述

3.3-3栈在表达式求值中的应用（下）

中缀转后缀（手算）

在这里插入图片描述

中缀转后缀（机算）例1不带括号

在这里插入图片描述

A是操作数，直接输出

+是运算符且栈是空的状态，把 + 压入栈

B直接输出

减号- 和栈中 + 优先级相同，把减号-弹出来，把+压入栈

c是操作数直接输出

乘号比减号优先级高，第三条不符合，所以直接压入栈。D是操作数，直接输出。
在这里插入图片描述
除号 / 和栈中乘号 *优先级相同，乘号出栈，除号入栈。 E直接输出

加号 +优先级小于栈中除号/ , 等于栈中减号-的优先级。栈中运算符可依次输出。在把加法+ 运算符压入栈中，把F直接初始，栈中加号+出栈，完成后缀表达式的转变。
在这里插入图片描述

中缀转后缀（机算）例2带括号

栈用来保存暂时还不能确定运算顺序的运算符。
在这里插入图片描述
弹出减号，在去掉左括号

减号优先级比乘号*低，和加号+一样，依次弹出乘号，加号，再把减号压入栈里。

除号压入栈里

全部弹出

中缀表达式的求值（用栈实现）

中缀表达式的求值就是中缀转后缀+后缀表达式求值的结合。
一边把中缀表达式转后缀，一边计算已经转换完的后缀表达式的值（先弹出的是右操作数）

在这里插入图片描述

总结

在这里插入图片描述

3.3-4栈在递归中的应用

在这里插入图片描述

3.3-5队列的应用

1、树的层次遍历（树章节详解）
2、图的广度优先遍历（图章节详解）
3、在操作系统中的应用，多个进程争抢使用有限的系统资源时，可以用队列进行先来先服务的排序。

3.4 特殊矩阵的压缩存储

普通矩阵的存储

在这里插入图片描述

对称矩阵的压缩存储

在这里插入图片描述

三角矩阵的压缩存储

在这里插入图片描述

三对角矩阵的压缩存储（三斜行，除了第一行和最后一行两个元素，其余的行全是三个元素）

在这里插入图片描述

稀疏矩阵的压缩存储

三元组存储

在这里插入图片描述

十字链表法

在这里插入图片描述

版权声明
本文为[没有人会真的躺平]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_32480989/article/details/126005637

边栏推荐

猜你喜欢

随机推荐