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

队列与堆栈:原理、区别、算法效率和应用场景的探究

队列与堆栈:原理、区别、算法效率和应用场景的探究

  • 前言
  • 原理与应用场景
    • 队列
      • 原理
      • 应用场景:
    • 堆栈
      • 原理
      • 应用场景
        • 递归原理和堆栈在其中的作用
          • 递归原理
          • 堆栈作用
  • 队列与堆栈区别
    • 队列
    • 堆栈
    • 算法效率

前言

本文主要讲解数据结构中队列和堆栈的原理、区别以及相关的应用方向。从图文和代码的角度进行解析。

原理与应用场景

队列

原理

先进先出的数据结构,元素从队尾入队,从队头出队。

应用场景:

任务调度:任务一般都是按序执行,基于先来先服务的概念,先放进去的任务先执行。如:操作系统进程调度、
排队系统:排队中,每个角色都是相同优先级情况下,比如说:餐厅点餐、银行办理业务、车票购买等系统,所有人都按先来先服务的概念执行。
消息传递:按照时间顺序进行消息的发送与接收,基于队列也就是先来先服务的概念。如:QQ、微信、QQ邮件。

堆栈

原理

后进先出的数据结构,元素从栈顶进入插入和删除操作。

应用场景

由于堆栈式后进先出,所以它能解决一种问题:也就是回退。如解决递归、回溯算法等。这里简单介绍其中递归算法与堆栈的关系。

递归原理和堆栈在其中的作用
递归原理

递归是一种通过在函数内部调用自身来解决问题的技术。把一个大问题拆解成有数个小问题,并逐一解决。通过不断调用自己(函数)把大问题拆解成小问题并把所有小问题的答案组合到一起最终解决大问题。

堆栈作用

递归每次调用自身时,都有一个新的地址用于存放它当前解决自身小问题的解,这个地址叫栈帧,栈帧用于存储函数的局部变量、参数、返回地址等信息。函数在不断调用自身时也就不断创造
新的栈帧,并将这些栈帧压入到堆栈中。满足条件后返回这些栈帧。

  • 存储函数调用的上下文信息,包括局部变量、参数和返回地址等。
  • 跟踪函数调用和返回的顺序,确保递归函数能够按照正确的顺序执行,并避免混乱或重复执行。
  • 限制递归的深度,防止无限递归导致程序崩溃或栈溢出。
  • 提供回退操作,使得递归函数可以从当前状态回到上一层状态,实现问题的逐步解决。

队列与堆栈区别

队列为先进先出,堆栈为先进后出。具体的我以代码和运行图形式讲解。

队列

<!DOCTYPE html>
<html><head><meta charset="utf-8"><title></title><style>#dataInput{width:100px;border:none;padding:5px 10px;border-bottom:1px solid lightgray;}#dataInput :active{border:none;}#dataInput :visited{border:none;}button{background-color: white;padding:5px 10px;border:1px solid lightgray;}.father {width: 100px;height: auto;margin: 0 auto 0 auto;}.son {width: 100px;height: 20px;border: 1px solid black;margin-right: 10px;margin: 0 auto 0 auto;text-align: center;justify-items: center;line-height: 20px;animation-duration: 3s;animation-name: slidein;}</style></head><body><div style="position: absolute;left:40%;"><input id="dataInput" type="number" aria-valuemax="10" placeholder="请输入数据" value=""><button onclick="pushs()">入队</button><button onclick="pops()">出队</button></div><div style="height:50px;"></div><div id="father" class="father"></div><script>function pushs() {let doc = document.getElementById('father')let data = document.getElementById('dataInput').valueif (data != '') {doc.insertAdjacentHTML('beforebegin', '<div id="son" class="son">' + data + '</div>')document.getElementById('dataInput').value = ''}}function pops() {document.getElementById('son').remove()}</script></body>
</html>

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
我们首先新增了一个5,这个5被压到最底下了,又点击出队,发现最开始新增的1出队了,这就叫先进先出。

堆栈

<!DOCTYPE html>
<html><head><meta charset="utf-8"><title></title><style>#dataInput{width:100px;border:none;padding:5px 10px;border-bottom:1px solid lightgray;}#dataInput :active{border:none;}#dataInput :visited{border:none;}button{background-color: white;padding:5px 10px;border:1px solid lightgray;}.father {width: 100px;height: auto;margin: 0 auto 0 auto;}.son {width: 100px;height: 20px;border: 1px solid black;border-top: none;margin-right: 10px;margin: 0 auto 0 auto;text-align: center;justify-items: center;line-height: 20px;animation-duration: 3s;animation-name: slidein;}</style></head><body><div style="position: absolute;left:40%;"><input id="dataInput" type="number" aria-valuemax="10" placeholder="请输入数据" value=""><button onclick="pushs()">push(入栈)</button><button onclick="pops()">pop(出栈)</button></div><div style="height:50px;"></div><div id="father" class="father"></div><script>function pushs() {let doc = document.getElementById('father')let data = document.getElementById('dataInput').valueif (data != '') {doc.insertAdjacentHTML('afterbegin', '<div id="son" class="son">' + data + '</div>')document.getElementById('dataInput').value = ''}}function pops() {document.getElementById('son').remove()}</script></body>
</html>

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
首先我们,新添加了一个5入栈,到栈顶,然后又点击出栈,会发现最后入栈的5,没有了。这就是先进后出算法。

算法效率

正常情况下都是常数时间复杂度也就是O(1),队列的查找操作的时间复杂度为O(n),而堆栈没有查找操作。

相关文章:

队列与堆栈:原理、区别、算法效率和应用场景的探究

队列与堆栈&#xff1a;原理、区别、算法效率和应用场景的探究 前言原理与应用场景队列原理应用场景&#xff1a; 堆栈原理应用场景递归原理和堆栈在其中的作用递归原理堆栈作用 队列与堆栈区别队列堆栈算法效率 前言 本文主要讲解数据结构中队列和堆栈的原理、区别以及相关的…...

数据结构与算法【链表:一】Java实现

目录 链表 单向链表 哨兵链表 双向链表 环形链表 链表 链表是数据元素的线性集合&#xff0c;其每个元素都指向下一个元素&#xff0c;元素存储上并不连续。 随机访问性能 根据 index 查找&#xff0c;时间复杂度 O(n) 插入或删除性能 起始位置&#xff1a;O(1)结束位…...

数据结构 | 队列的实现

数据结构 | 队列的实现 文章目录 数据结构 | 队列的实现队列的概念及结构队列的实现队列的实现头文件&#xff0c;需要实现的接口 Queue.h初始化队列队尾入队列【重点】队头出队列【重点】获取队列头部元素获取队列队尾元素获取队列中有效元素个数检测队列是否为空销毁队列 Que…...

flutter 集成 高德地图,退出界面闪退

android:allowNativeHeapPointerTagging"false"应用尝试释放系统堆分配器未分配的指针。 应用中的某个部分修改了指针的顶部字节。不能修改指针的顶部字节&#xff0c;您需要更改代码来修复此问题。 指针的顶部字节被错误使用或修改的示例包括&#xff1a; 指向特定…...

数据结构----链式栈的操作

链式栈的定义其实和链表的定义是一样的&#xff0c;只不过在进行链式栈的操作时要遵循栈的规则----即“先进后出”。 1.链式栈的定义 typedef struct StackNode {SElemType data;struct StackNode *next; }StackNode,*LinkStack; 2.链式栈的初始化 Status InitStack(LinkSta…...

识别伪装IP的网络攻击方法

识别伪装IP的网络攻击可以通过以下几种方法&#xff1a; 观察IP地址的异常现象。攻击者在使用伪装IP地址进行攻击时&#xff0c;往往会存在一些异常现象&#xff0c;如突然出现的未知IP地址、异常的流量等。这些现象可能是攻击的痕迹&#xff0c;需要对此加以留意。 检查网络通…...

C 语言指针

C 语言指针 在本教程中&#xff0c;您将学习指针。什么是指针&#xff0c;如何使用它们以及在示例的帮助下使用它们时可能遇到的常见错误。 指针是 C和C 编程的强大功能。在学习指针之前&#xff0c;让我们学习一下C语言编程中的地址。 C 语言地址 如果程序中有变量var&am…...

学【Java多态】-- 写高质量代码

多态的实现条件 在java中要实现&#xff0c;必须要满足如下几个条件&#xff0c;缺一不可。 1.必须在继承体系下2.子类必须要对父类中的方法进行重写3.通过父类的引用调用冲写的方法。 想要真正的学好多态需要去学习一些前置知识&#xff0c;那我们直接开始吧&#xff01; …...

【汇编】内存的读写与地址空间、寄存器及数据存储

文章目录 前言一、CPU对存储器的读写1.1 cpu对存储器的读写如何进行&#xff1f;1.2 演示 二、内存地址空间三、将各类存储器看作一个逻辑存储器——统一编址内存地址空间的分配方案 三、CPU的组成寄存器是CPU内部的信息存储单元通用寄存器--AX为例“横看成岭侧成峰“ 四、“字…...

DSP生成hex方法

以下使用两种方法生成的HEX文件&#xff0c;亲测可用 &#xff08;1&#xff09;万能法 不管.out文件是哪个版本CCS编译器生成的&#xff0c;只要用HEX2000.exe软件&#xff0c;翻译都可以使用。方法&#xff1a; hex2000 -romwidth 16 -memwidth 16 -i -o 20170817chuankou…...

GZ038 物联网应用开发赛题第7套

2023年全国职业院校技能大赛 高职组 物联网应用开发 任 务 书 &#xff08;第7套卷&#xff09; 工位号&#xff1a;______________ 第一部分 竞赛须知 一、竞赛要求 1、正确使用工具&#xff0c;操作安全规范&#xff1b; 2、竞赛过程中如有异议&#xff0c;可向现场考评…...

ELK之Logstash解析时间相差8h的问题

一、问题描述 服务器当前时间为&#xff1a;2022年 06月 28日 星期二 11:24:22 CST 而logstash解析的时间为2022-06-28T03:15:25.545Z与实际时间相差8h 一、解决办法&#xff1a; 需改logstash的配置文件&#xff1a; 原理就是&#xff1a;定义一个中间变量timestamp&…...

uniapp+vite+vue3开发跨平台app,运行到安卓模拟器调试方法

因为没有使用hbuilder开发uniapp&#xff0c;而是使用了vscode和vite来开发的&#xff0c;所以怎么将这个程序运行到安卓模拟器调试开发呢&#xff1f;其实方法很简单&#xff0c;使用android studio创建一个模拟器或者其他mumu模拟器&#xff0c;然后将项目使用hbuilder打开&a…...

Ubuntu诞生已经19年了

导读2004 年 10 月 20 日&#xff0c;Ubuntu 4.10 正式发布&#xff0c;代号‘Warty Warthog’。 2004 年 10 月 20 日&#xff0c;Ubuntu 4.10 正式发布&#xff0c;代号‘Warty Warthog’。 ▲ Ubuntu 4.10 与最新版 Ubuntu 23.10 的对比 作为 Ubuntu 第一个版本&#xff0…...

跟着基金买,别墅靠大海?买基金重仓股票,会破产吗?| 附最新选股结果

2020年A股经历了一波结构性牛市。 抱团核心资产的公募基金历史性大赚2万亿&#xff0c;一跃成为全市场顶流。不仅常年霸榜热搜&#xff0c;甚至连游戏直播的弹幕都在讨论基金。 很多年轻人也纷纷跑步入场&#xff0c;毕竟支付宝买基金贼方便。 可惜好景不长&#xff0c;大盘急…...

【教3妹学编辑-mysql】mybatis查询条件遇到的坑及解决方案

2哥 :3妹&#xff0c;今天怎么下班这么晚啊。 3妹&#xff1a;嗨&#xff0c;别提了&#xff0c;今天线上出bug了&#xff0c; 排查了好久。 2哥&#xff1a;啊&#xff0c;什么问题呀&#xff1f; 3妹&#xff1a;我们内部的一个管理系统报错了&#xff0c; 最近排查下来是myb…...

032-从零搭建微服务-定时服务(一)

写在最前 如果这个项目让你有所收获&#xff0c;记得 Star 关注哦&#xff0c;这对我是非常不错的鼓励与支持。 源码地址&#xff08;后端&#xff09;&#xff1a;mingyue: &#x1f389; 基于 Spring Boot、Spring Cloud & Alibaba 的分布式微服务架构基础服务中心 源…...

精通Nginx(11)-缓存

缓存能够存储请求的响应结果,以供未来再次使用,进而加速内容的提供。内容缓存可以缓存完整的响应,减少上游服务器的负载,避免了每次都为相同的请求重新运行计算和查询的麻烦。缓存可以提高性能并减少负载,这意味着可以用更少的资源更快地提供服务。NGINX 允许在NGINX 服务…...

用excel计算矩阵的乘积

例如&#xff0c;我们要计算两个矩阵的乘积&#xff0c; 第一个矩阵是2*2的&#xff1a; 1234 第2个矩阵是2*3的&#xff1a; 5697810 在excel中鼠标点到其它空白的地方&#xff0c;用来存放矩阵相乘的结果&#xff1a; 选择插入-》函数&#xff1a; 选中MMULT&#xff0c;…...

【微软技术栈】C#.NET 中使用依赖注入

本文内容 先决条件创建新的控制台应用程序添加接口添加默认实现添加需要 DI 的服务为 DI 注册服务结束语 本文介绍如何在 .NET 中使用依赖注入 (DI)。 借助 Microsoft 扩展&#xff0c;可通过添加服务并在 IServiceCollection 中配置这些服务来管理 DI。 IHost 接口会公开 IS…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...

go 里面的指针

指针 在 Go 中&#xff0c;指针&#xff08;pointer&#xff09;是一个变量的内存地址&#xff0c;就像 C 语言那样&#xff1a; a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10&#xff0c;通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...