当前位置: 首页 > 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…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

tauri项目,如何在rust端读取电脑环境变量

如果想在前端通过调用来获取环境变量的值&#xff0c;可以通过标准的依赖&#xff1a; std::env::var(name).ok() 想在前端通过调用来获取&#xff0c;可以写一个command函数&#xff1a; #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...