当前位置: 首页 > news >正文

数据结构第2章 栈和队列

名人说:莫听穿林打叶声,何妨吟啸且徐行。—— 苏轼《定风波·莫听穿林打叶声》
本篇笔记整理:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊)

目录

    • 0、思维导图
    • 栈和队列
    • 1、栈
      • 1)特点
      • 2)分类
      • 3)应用
    • 2、队列
      • 1)特点
      • 2)分类
      • 3)应用

0、思维导图

在这里插入图片描述

栈和队列

1、栈

栈是一种遵循后进先出(LIFO,Last In First Out)原则的数据结构。可以想象成一摞盘子,最后放上去的盘子会最先拿掉。
在这里插入图片描述

1)特点

“后进先出(LIFO)”
在这里插入图片描述

2)分类

①顺序栈
在这里插入图片描述

采用顺序存储的栈结构。

  • 1️⃣入栈和出栈
    在这里插入图片描述

  • 2️⃣判断栈满空

    说明:栈顶指针top表示当前栈顶元素的位置、MAXSIZE是数组容量大小。

    • a.满:top == MAXSIZE - 1

    • b.空:top == -1

②链栈

采用链式存储的栈结构
在这里插入图片描述

  • a.入栈和出栈

在这里插入图片描述

  • b.判断栈满空

    说明:top为栈顶指针

    • 栈满:一般不存在此类情况

    • 栈空:top == NULL

③共享栈
共享栈通常是指在程序设计中,多个线程共享同一个栈空间的概念,如下图,两个顺序栈共享内存空间。
在这里插入图片描述

判断栈空、栈满

  • 栈空:top0=-l 时0号栈为空,topl=MaxSize时1号栈空;
  • 栈满:两个栈顶指针相邻(topl-top0=l)。时

3)应用

①函数调用(一般递归较为常见)

②表达式求值
在这里插入图片描述

  • 前缀表达式

    • 运算符位于操作数之前
  • 中缀表达式

    • 运算符位于操作数之间
  • 后缀表达式

    • 运算符位于操作数之后
  • 前中后缀转换

    • 1️⃣中缀转前缀

      • 转换步骤

        • 1、加括号

        • 2、前移运算符

        • 3、去括号

      • 举例在这里插入图片描述

    • 2️⃣中缀转后缀

      • 转换步骤

        • 1、加括号

        • 2、后移运算符

        • 3、去括号

    • 举例在这里插入图片描述

③括号匹配

在这里插入图片描述

④深度优先搜索

2、队列

队列是一种遵循先进先出(FIFO,First In First Out)原则的数据结构。可以想象成排队买票,最先排队的人最先买到票。

在这里插入图片描述

1)特点

“ 先进先出(FIFO)”
在这里插入图片描述

2)分类

①顺序队列

使用顺序存储的队列结构

  • 入队和出队
    在这里插入图片描述

  • 判断满与空

    • 队头指针front和队尾指针rear分别指示当前队头元素和队尾元素的位置

    • 满:rear == MAXSIZE - 1

    • 空:front == rear

②循环队列

队列的头尾相接的顺序队列结构
在这里插入图片描述

  • 判断满与空

    • 队头指针front和队尾指针rear分别指示当前队头元素和队尾元素的位置。Maxsize指队列的数组大小。

    • 满:(rear + 1) % Maxsize == front,其中%表示取模运算。

    • 空:front == rear。

    • 元素个数:(rear - front + Maxsize) % Maxsize

③链式队列

使用链式存储的队列结构
在这里插入图片描述

  • 判断满与空

    说明:头指针front和尾指针rear分别指向当前队头元素和队尾元素。

    • 满:一般不存在此类情况
    • 空:front == NULL且rear == NULL。

④双端队列
两端都可以进行入队和出队操作的队列
在这里插入图片描述

  • 输出受限的双端队列

    • 一端可插入和删除,另一端只允许插入
      在这里插入图片描述
  • 输入受限的双端队列

    • 一端可进行插入和删除,另一端只允许删除
      在这里插入图片描述

3)应用

①层次遍历

②计算机系统

  • 资源管理

  • 消息缓冲

  • 页面替换算法

③广度优先搜索

上述内容笔记部分图片来源网络,侵删。
参考内容:
1.《王道数据结构》
2.【LeetCode】括号匹配问题
3.数据结构电子讲义
4.数据结构共享栈

Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder)
点赞加关注,收藏不迷路!本篇文章对你有帮助的话,还请多多点赞支持!

相关文章:

数据结构第2章 栈和队列

名人说:莫听穿林打叶声,何妨吟啸且徐行。—— 苏轼《定风波莫听穿林打叶声》 本篇笔记整理:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 目录 0、思维导图栈和队列1、栈1)特点2&#xff0…...

Axure鲜花商城网站原型图,网上花店订花O2O本地生活电商平台

作品概况 页面数量:共 30 页 兼容软件:仅支持Axure RP 9/10,非程序软件无源代码 应用领域:鲜花网、花店网站、本地生活电商 作品特色 本作品为「鲜花购物商城」网站模板,高保真高交互,属于O2O本地生活电…...

【docker】centos 使用 Nexus Repository 搭建私有仓库

Nexus Repository 是一种流行的软件仓库管理工具,它可以帮助您搭建私有仓库,以便在内部网络或私有云环境中存储、管理和分发各种软件包和组件。 它常被用于搭建Maven的镜像仓库。本文演示如何用Nexus Repository搭建docker 私有仓库。 使用Nexus Repos…...

RabbitMQ(八)消息的序列化

目录 一、为什么需要消息序列化?二、常用的消息序列化方式1)Java原生序列化(默认)2)JSON格式3)Protobuf 格式4)Avro 格式5)MessagePack 格式 三、总结 RabbitMQ 是一个强大的消息中间…...

23款奔驰GLC260L升级原厂540全景影像 安装效果分享

嗨 今天给大家介绍一台奔驰GLC260L升级原厂360全景影像 新款GLC升级原厂360全景影像 也只需要安装前面 左右三个摄像头 后面的那个还是正常用的,不过不一样的是 升级完成之后会有多了个功能 那就是新款透明底盘,星骏汇小许Xjh15863 左右两边只需要更换后…...

【CSS】文字描边的三种实现方式

目录 1. 可行的几种方式1.1. text-shadow 描边代码优缺点 1.2. text-stroke 描边实现优缺点 1.3. svg 描边实现优缺点 总结 1. 可行的几种方式 text-shadow–webkit-text-strokesvg 1.1. text-shadow 描边 MDN text-shadow 代码 <div class"text stroke">…...

【事务】事务传播级别

Spring事务定义了7种传播机制&#xff1a; PROPAGATION_REQUIRED&#xff1a;默认的Spring事物传播级别&#xff0c;若当前存在事务&#xff0c;则加入该事务&#xff0c;若不存在事务&#xff0c;则新建一个事务。 PAOPAGATION_REQUIRE_NEW&#xff1a;若当前没有事务&#x…...

Android WiFi 连接

Android WiFi 连接 1、设置中WiFi显示2、WiFi 连接流程2.1 获取PrimaryClientModeManager2.2 ClientModeImpl状态机ConnectableState2.3 ISupplicantStaNetworkCallback 回调监听 3、 简要时序图4、原生低层驱动5、关键日志 1、设置中WiFi显示 Android WiFi基础概览 packages/a…...

PLC与上位机PN通讯时,如何防止连接失败?

连接西门子PLC时失败&#xff0c;或者连接不上PLC&#xff0c;你可能需要做以下几点设置才可以。 一般来说每个PLC都有自己的IP地址&#xff0c;如果你的地址与PLC的地址冲突也就是地址重复是连接不上PLC的&#xff0c;如果地址没有冲突&#xff0c;但是不是在一个网段上也会导…...

LDD学习笔记 -- Linux错误码

LDD学习笔记 -- Linux错误码 EACCES(Permission Denied) 13EEXIST(File Exits) 17EINVAL(Invalid Argument) 22ENOENT(No Such File or Directory)ENOMEM(Out of Memory)EIO(Input/Output Error) 5ENOSPC(No space Left on Device)ENOTTY(Not a Typewrite)EPIPE(Broken Pipe)EI…...

华为交换机入门(六):VLAN的配置

VLAN&#xff08;Virtual Local Area Network&#xff09;即虚拟局域网&#xff0c;是将一个物理的LAN在逻辑上划分成多个广播域的通信技术。VLAN内的主机间可以直接通信&#xff0c;而VLAN间不能直接互通&#xff0c;从而将广播报文限制在一个VLAN内。 VLAN 主要用来解决如何…...

登录验证

目录 会话技术 Cookie Session JWT JWT生成 JWT校验 会话技术 会话 打开浏览器&#xff0c;访问web服务器的资源&#xff0c;会话建立&#xff0c;直到有一方断开连接&#xff0c;会话结束。在一次会话中可以包含多次请求与响应 会话跟踪 一种维护浏览器的方法 服务器需要…...

利用Podman构建基于Fission env/builder的镜像

镜像准备 构建Dockerfile fission的基础环境包括两种&#xff1a;env 以及 builder。如果仅基于code构建function&#xff08;i.e., 只创建deployachive&#xff09;&#xff0c;仅构建env即可&#xff1b;但如果需要构建sourcearchive&#xff0c;则需要同时创建env和builde…...

php加减乘除函数

目录 第一部分&#xff1a;简单示例 1、加法 2、减法 3、乘法 4、除法 第二部分&#xff1a;官方文档 1、加法 2、减法 3、乘法 4、除法 第一部分&#xff1a;简单示例 1、加法 $result bcadd(1.2, 1.4, 2); echo $result;//2.60 2、减法 $result bcsub(1.6, 1.…...

Go语言学习记录——用正则表达式(regexp包)来校验参数

前言 最近坐毕设ing&#xff0c;简单的一个管理系统。 其中对于用户注册、登录功能&#xff0c;需要进行一些参数校验。 因为之前使用过&#xff0c;因此这里计划使用正则表达式进行校验。但是之前的使用也仅限于使用&#xff0c;因此这次专门进行一次学习&#xff0c;并做此记…...

公司办公电脑文件防泄密系统

电脑文件防泄密系统是一种用于保护企业机密文件的软件系统&#xff0c;它采用一系列的安全技术手段&#xff0c;如数据加密、访问控制、审计跟踪等&#xff0c;来确保企业机密文件不被非法获取、窃取或泄漏。这种系统通常适用于企业、政府机构等需要对重要文件进行保密的机构。…...

手把手带你死磕ORBSLAM3源代码(三十四)Tracking.cc MonocularInitialization编辑

目录 一.前言 二.代码 2.1完整代码 2.2 单目视觉跟踪初始化 一.前言 这段代码是一个名为MonocularInitialization的函数,它属于Tracking类。从函数名称和代码内容来看,这个函数主要用于单目视觉跟踪的初始化过程。以下是代码的详细解读: 首先,函数检查一个名为m...

STL标准库与泛型编程(侯捷)笔记3

STL标准库与泛型编程&#xff08;侯捷&#xff09; 本文是学习笔记&#xff0c;仅供个人学习使用。如有侵权&#xff0c;请联系删除。 参考链接 Youbute: 侯捷-STL标准库与泛型编程 B站: 侯捷 - STL Github:STL源码剖析中源码 https://github.com/SilverMaple/STLSourceCo…...

Iceberg: 列式读取Parquet数据

通过Spark读取Parquet文件的基本流程 SQL > Spark解析SQL生成逻辑计划树 LogicalPlan > Spark创建扫描表/读取数据的逻辑计划结点 DataSourceV2ScanRelation > Spark优化逻辑计划树&#xff0c;生成物理计划树 SparkPlan > Spark根据不同的属性&#xff0c;将逻辑…...

Ansible、Saltstack、Puppet自动化运维工具介绍

本文主要是分享介绍三款主流批量操控工具Ansible、Saltstack、Puppet主要对比区别&#xff0c;以及Ansible和saltstack的基础安装和使用示例&#xff0c;如果觉得本文对你有帮助&#xff0c;欢迎点赞、收藏、评论&#xff01; There are many things that can not be broken&am…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...