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

数据结构与算法:栈与队列的高级应用

目录

3.1 栈的高级用法

3.2 队列的深度应用

3.3 栈与队列的综合应用

总结


数据结构与算法:栈与队列的高级应用

栈和队列是两种重要的线性数据结构,它们在计算机科学和工程的许多领域都有广泛的应用。从函数调用到表达式求值,再到任务调度系统,栈和队列无处不在。通过深入理解栈和队列的操作、内存管理及其高级应用,我们可以更好地使用这些基础结构来解决复杂的问题。本章将深入探讨栈与队列的高级应用。

3.1 栈的高级用法

栈是一种“后进先出”(LIFO,Last In First Out)的数据结构,具有非常明确的使用场景。栈在函数调用和递归处理、表达式求值、语法解析等方面有着广泛的应用。

栈帧在函数调用与递归中的应用:在程序执行过程中,每次函数调用都会创建一个栈帧,并将其压入调用栈中。栈帧中保存了函数的局部变量、返回地址等信息。递归调用通过重复利用栈来管理函数调用顺序和返回结果。

代码示例:递归函数的栈帧示意

#include <stdio.h>int factorial(int n) {if (n == 0) {return 1;} else {return n * factorial(n - 1);}
}int main() {int num = 5;printf("%d 的阶乘是 %d\n", num, factorial(num));return 0;
}

在这个代码示例中,每次调用 factorial() 时,都会在调用栈上创建一个新的栈帧,直到 n 减到 0 为止。在递归的返回阶段,栈帧按相反的顺序出栈,计算并返回结果。

栈在表达式求值与语法解析中的应用:栈被广泛用于表达式求值(例如中缀表达式转后缀表达式)以及编译器中的语法解析。通过将操作符压入栈,可以处理不同优先级的运算符,并确保表达式求值的正确性。

代码示例:中缀表达式转后缀表达式

#include <stdio.h>
#include <ctype.h>#define MAX 100
char stack[MAX];
int top = -1;void push(char c) {stack[++top] = c;
}char pop() {return stack[top--];
}int precedence(char op) {if (op == '+' || op == '-') {return 1;} else if (op == '*' || op == '/') {return 2;}return 0;
}void infixToPostfix(char* exp) {char* p = exp;while (*p != '\0') {if (isdigit(*p)) {printf("%c ", *p);} else if (*p == '(') {push(*p);} else if (*p == ')') {while (top != -1 && stack[top] != '(') {printf("%c ", pop());}pop();} else {while (top != -1 && precedence(stack[top]) >= precedence(*p)) {printf("%c ", pop());}push(*p);}p++;}while (top != -1) {printf("%c ", pop());}printf("\n");
}int main() {char expression[] = "3+(2*4)-5";printf("后缀表达式: ");infixToPostfix(expression);return 0;
}

在这个示例中,栈被用来存储操作符,确保运算符按正确的优先级顺序输出,从而完成中缀表达式到后缀表达式的转换。

双栈实现最小栈问题:最小栈是一种特殊的栈,它在常数时间内返回栈中最小的元素。可以通过两个栈来实现,一个用于存储数据,另一个用于存储当前最小值。

代码示例:最小栈的实现

#include <stdio.h>
#include <stdlib.h>#define MAX 100
int stack[MAX];
int minStack[MAX];
int top = -1;
int minTop = -1;void push(int value) {stack[++top] = value;if (minTop == -1 || value <= minStack[minTop]) {minStack[++minTop] = value;}
}void pop() {if (top == -1) {return;}if (stack[top] == minStack[minTop]) {minTop--;}top--;
}int getMin() {return minStack[minTop];
}int main() {push(10);push(20);push(5);push(15);printf("当前最小值: %d\n", getMin());pop();printf("当前最小值: %d\n", getMin());return 0;
}

通过维护一个辅助栈来存储最小值,可以在常数时间内获取栈的最小元素,从而实现高效的最小栈操作。

栈在图的遍历与路径记录中的应用:在图的深度优先遍历(DFS)中,栈被用来追踪访问过的节点,确保每个节点都被访问一次并记录路径。

3.2 队列的深度应用

队列是一种“先进先出”(FIFO,First In First Out)的数据结构,它在很多场景下都具有不可替代的作用。队列在任务调度、广度优先搜索等领域有着广泛的应用。

循环队列与环形缓冲区设计:循环队列是一种特殊的队列,它通过将队尾和队首连接形成一个环状,使得队列可以高效利用内存空间,特别适合于资源有限的系统,如嵌入式系统中的数据缓冲区管理。

代码示例:循环队列的实现

#include <stdio.h>
#define MAX 5int queue[MAX];
int front = -1;
int rear = -1;void enqueue(int value) {if ((rear + 1) % MAX == front) {printf("队列已满\n");} else {if (front == -1) front = 0;rear = (rear + 1) % MAX;queue[rear] = value;}
}void dequeue() {if (front == -1) {printf("队列为空\n");} else {printf("移除元素: %d\n", queue[front]);if (front == rear) {front = rear = -1;} else {front = (front + 1) % MAX;}}
}int main() {enqueue(10);enqueue(20);enqueue(30);enqueue(40);enqueue(50);dequeue();enqueue(60);dequeue();return 0;
}

在这个代码示例中,循环队列通过将数组的末端和开头相连,实现了空间的循环利用,使得队列可以在有限的内存中实现高效的插入和删除操作。

优先队列与双端队列(Deque)的实现:优先队列是一种特殊的队列,其中每个元素都有一个优先级,出队时优先级最高的元素优先被移除。优先队列在调度算法中具有重要作用,例如操作系统的任务调度。

队列在操作系统中的调度算法应用:队列广泛用于操作系统中的任务管理和调度。例如,打印队列、CPU任务调度队列等。通过合理使用优先队列,操作系统可以保证高优先级任务的及时响应,从而提高系统的效率和用户体验。

3.3 栈与队列的综合应用

应用实例分析:浏览器历史记录与任务调度系统:浏览器历史记录通常使用栈来存储访问的页面,用户点击“返回”按钮时会从栈中弹出上一个页面。同时,队列在任务调度系统中用于管理各个任务的执行顺序,保证先进先出的调度策略。

栈与队列在实际项目中的设计模式:栈和队列在实际项目中往往可以结合使用。例如,深度优先搜索使用栈来追踪节点,而广度优先搜索则使用队列。理解如何在复杂系统中结合使用这些数据结构,有助于构建更高效的算法。

总结

本章介绍了栈和队列的高级应用,包括它们在递归、表达式求值、任务调度、图遍历等方面的重要作用。栈的LIFO特性使得它在函数调用管理、表达式求值等场景中不可替代,而队列的FIFO特性则使其在任务调度和广度优先搜索中占据核心地位。理解栈与队列的高级用法,能够帮助我们设计出更高效、灵活的数据处理系统。

在下一章中,我们将讨论递归、分治与回溯等算法范式,它们与栈有着密不可分的关系,并且在解决复杂问题时表现出了卓越的能力。

相关文章:

数据结构与算法:栈与队列的高级应用

目录 3.1 栈的高级用法 3.2 队列的深度应用 3.3 栈与队列的综合应用 总结 数据结构与算法&#xff1a;栈与队列的高级应用 栈和队列是两种重要的线性数据结构&#xff0c;它们在计算机科学和工程的许多领域都有广泛的应用。从函数调用到表达式求值&#xff0c;再到任务调度…...

macos php开发环境之macport安装的php扩展安装,php常用扩展安装,port中可用的所有php扩展列表

macos中&#xff0c;我们使用了port 安装了php后&#xff0c;默认只带有php基本的核心扩展的&#xff0c; 如果需要使用其他的扩展&#xff0c;如 redis, https&#xff0c; xdebug等扩展就需要我们手动来安装对应的扩展。 macos php开发环境 macport安装的php的方法见macos 中…...

使用Pytorch+Numpy+Matplotlib实现手写字体分类和图像显示

文章目录 1.引用2.内置图片数据集加载3.处理为batch类型4.设置运行设备5.查看数据6.绘图查看数据图片(1)不显示图片标签(2)打印图片标签(3)图片显示标签 7.定义卷积函数8.卷积实例化、损失函数、优化器9.训练和测试损失、正确率(1)训练(2)测试(3)循环(4)损失和正确率曲线(5)输出…...

kimi帮我解决ubuntu下软链接文件夹权限不够的问题

我的操作如下 ubuntuubuntu-QiTianM420-N000:~$ ln -s /media/ubuntu/4701aea3-f883-40a9-b12f-61e832117414 code ubuntuubuntu-QiTianM420-N000:~$ ls -l 总用量 636 drwxrwxr-x 2 ubuntu ubuntu 4096 5月 7 17:16 bin drwxrwxrwx 2 ubuntu ubuntu 4096 5月 8 13…...

如何去除背景音乐保留人声?保留人声,消除杂音

在日常生活和工作中&#xff0c;我们经常遇到需要处理音频的情况&#xff0c;尤其是当我们想要去除背景音乐&#xff0c;仅保留人声时。这种需求在处理电影片段、制作音乐MV、或者提取演讲内容等场景中尤为常见。本文将为您详细介绍如何去除背景音乐并保留人声&#xff0c;帮助…...

2.4.ReactOS系统提升IRQL级别KfRaiseIrql 函数

2.4.ReactOS系统提升IRQL级别KfRaiseIrql 函数 2.4.ReactOS系统提升IRQL级别KfRaiseIrql 函数 文章目录 2.4.ReactOS系统提升IRQL级别KfRaiseIrql 函数KfRaiseIrql 函数 KfRaiseIrql 函数 /*********************************************************************** NAME …...

【新书】使用 OpenAI API 构建 AI 应用:利用 ChatGPT等构建 10 个 AI 项目(第二版),404页pdf

通过构建 ChatGPT 克隆、代码错误修复器、测验生成器、翻译应用、自动回复邮件生成器、PowerPoint 生成器等项目&#xff0c;提升您的应用开发技能。 关键特性 通过掌握 ChatGPT 概念&#xff08;包括微调和集成&#xff09;&#xff0c;转变为 AI 开发专家 通过涵盖广泛 AI …...

修改PostgreSQL表中的字段排列顺序

二、通过修改系统表(pg_attribute)达到字段重新排序的目的有关系统表的概述及用途可以查看官网&#xff1a;http://www.pgsqldb.org/pgsqldoc-cvs/catalogs.html 表名字表用途pg_class表&#xff0c;索引&#xff0c;序列&#xff0c;视图&#xff08;”关系”&#xff09;pg_…...

canvas实现手写功能

1.从接口获取手写内容&#xff0c;处理成由单个字组成的数组&#xff08;包括符号&#xff09; 2.合成所有图的时候&#xff0c;会闪现outputCanvas合成的图&#xff0c;注意隐藏 3.可以进行多个手写内容切换 4.基于uniapp的 <template><view class"content&quo…...

Python知识点:基于Python技术,如何使用TensorFlow进行目标检测

开篇&#xff0c;先说一个好消息&#xff0c;截止到2025年1月1日前&#xff0c;翻到文末找到我&#xff0c;赠送定制版的开题报告和任务书&#xff0c;先到先得&#xff01;过期不候&#xff01; 使用TensorFlow进行目标检测的完整指南 目标检测是计算机视觉领域中的一项重要任…...

初始爬虫13(js逆向)

为了解决网页端的动态加载&#xff0c;加密设置等&#xff0c;所以需要js逆向操作。 JavaScript逆向可以分为三大部分&#xff1a;寻找入口&#xff0c;调试分析和模拟执行。 1.chrome在爬虫中的作用 1.1preserve log的使用 默认情况下&#xff0c;页面发生跳转之后&#xf…...

前端发送了请求头的参数,经debug发现后端请求对象请求头中没有该参数

debug测试&#xff0c;发现前端发来请求头中确实没有找到添加的请求头参数&#xff0c;但是 Network 中却显示请求头中有该参数信息。 原因是RequestHeaders中设置的请求参数含有下划线&#xff0c;NGINX将静默地丢弃带有下划线的HTTP标头&#xff0c;这样做是为了防止在将头映…...

雷池社区版如何使用静态资源的方式建立站点

介绍&#xff1a; SafeLine&#xff0c;中文名 “雷池”&#xff0c;是一款简单好用, 效果突出的 Web 应用防火墙(WAF)&#xff0c;可以保护 Web 服务不受黑客攻击。 雷池通过过滤和监控 Web 应用与互联网之间的 HTTP 流量来保护 Web 服务。可以保护 Web 服务免受 SQL 注入、X…...

车载电源OBC+DC/DC

文章目录 1. 车载DC/DC应用场景2. PFC2.1 简介2.2 专业名词2.3 常见拓扑结构2.3.1 传统桥式PFC2.3.2 普通无桥型PFC2.3.3 双Boost无桥PFC2.3.4 图腾柱PFC2.3.5 参考资料 2.4 功率因数2.4.1 简介2.4.2 计算 3. DC/DC3.1 Boost升压电路3.1.1 简介3.1.2 电路框图3.1.3 工作原理3.1…...

【朝花夕拾】免费个人网页搭建:免费托管、CDN加速、个人域名、现代化网页模板一网打尽

现代化网页设计的免费宝藏&#xff1a;GitHub PagesCodePenCloudflareUS.KG 前言 在当今数字化时代&#xff0c;个人和企业越来越重视在线形象的建立。GitHub Pages 提供了一个免费且便捷的平台&#xff0c;允许用户托管静态网站。然而&#xff0c;GitHub Pages 默认的域名可…...

Spring Boot知识管理系统:用户体验设计

6系统测试 6.1概念和意义 测试的定义&#xff1a;程序测试是为了发现错误而执行程序的过程。测试(Testing)的任务与目的可以描述为&#xff1a; 目的&#xff1a;发现程序的错误&#xff1b; 任务&#xff1a;通过在计算机上执行程序&#xff0c;暴露程序中潜在的错误。 另一个…...

《数字信号处理》学习08-围线积分法(留数法)计算z 逆变换

目录 一&#xff0c;z逆变换相关概念 二&#xff0c;留数定理相关概念 三&#xff0c;习题 一&#xff0c;z逆变换相关概念 接下来开始学习z变换的反变换-z逆变换&#xff08;z反变化&#xff09;。 由象函数 求它的原序列 的过程就称为 逆变换。即 。 求z逆变换…...

vue3中的computed属性

模板界面&#xff1a; <template><div class"person"><h2>姓&#xff1a; <input type"text" v-model"person.firstName" /></h2><h2>名&#xff1a; <input type"text" v-model"person…...

C++学习笔记之vector容器

天上月&#xff0c;人间月&#xff0c;负笈求学肩上月&#xff0c;登高凭栏眼中月&#xff0c;竹篮打水碎又圆。 山间风&#xff0c;水边风&#xff0c;御剑远游脚下风&#xff0c;圣贤书斋翻书风&#xff0c;风吹浮萍又相逢。 STL(Standard Template Library,标准模板库 ) 从…...

LeNet-5(论文复现)

LeNet-5&#xff08;论文复现&#xff09; 本文所涉及所有资源均在传知代码平台可获取 文章目录 LeNet-5&#xff08;论文复现&#xff09;概述LeNet-5网络架构介绍训练过程测试过程使用方式说明 概述 LeNet是最早的卷积神经网络之一。1998年&#xff0c;Yann LeCun第一次将LeN…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...

ubuntu22.04有线网络无法连接,图标也没了

今天突然无法有线网络无法连接任何设备&#xff0c;并且图标都没了 错误案例 往上一顿搜索&#xff0c;试了很多博客都不行&#xff0c;比如 Ubuntu22.04右上角网络图标消失 最后解决的办法 下载网卡驱动&#xff0c;重新安装 操作步骤 查看自己网卡的型号 lspci | gre…...

在 Visual Studio Code 中使用驭码 CodeRider 提升开发效率:以冒泡排序为例

目录 前言1 插件安装与配置1.1 安装驭码 CodeRider1.2 初始配置建议 2 示例代码&#xff1a;冒泡排序3 驭码 CodeRider 功能详解3.1 功能概览3.2 代码解释功能3.3 自动注释生成3.4 逻辑修改功能3.5 单元测试自动生成3.6 代码优化建议 4 驭码的实际应用建议5 常见问题与解决建议…...

aardio 自动识别验证码输入

技术尝试 上周在发学习日志时有网友提议“在网页上识别验证码”&#xff0c;于是尝试整合图像识别与网页自动化技术&#xff0c;完成了这套模拟登录流程。核心思路是&#xff1a;截图验证码→OCR识别→自动填充表单→提交并验证结果。 代码在这里 import soImage; import we…...

聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇

根据 QYResearch 发布的市场报告显示&#xff0c;全球市场规模预计在 2031 年达到 9848 万美元&#xff0c;2025 - 2031 年期间年复合增长率&#xff08;CAGR&#xff09;为 3.7%。在竞争格局上&#xff0c;市场集中度较高&#xff0c;2024 年全球前十强厂商占据约 74.0% 的市场…...