• 栈、队列和数组

    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 特殊矩阵的压缩存储

    普通矩阵的存储

    在这里插入图片描述

    对称矩阵的压缩存储

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    三角矩阵的压缩存储

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

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

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    稀疏矩阵的压缩存储

    三元组存储

    在这里插入图片描述

    十字链表法

    在这里插入图片描述

  • 相关阅读:
    C#实现全盘扫描，找到符合要求的文件，并把路径写入到TXT中
    分饼干问题（DP）
    （十三）Java算法：基数排序（详细图解）
    C&C！无法检测的远程命令执行工具
    项目管理构建工具——Maven（基础篇）
    java线程局部变量ThreadLocal的作用和理解
    艾美捷高纯度 Cholesterol胆固醇相关介绍
    Python基础用法
    UWB定位模块
    SQL分页查询，SQL的LIMIT语句用法，SQL如何实现分页查询，SpringBoot实现分页查询。
  • 原文地址：https://blog.csdn.net/qq_32480989/article/details/126005637