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

【数据结构与算法 经典例题】使用栈实现队列(图文详解)

             💓 博客主页:倔强的石头的CSDN主页 

             📝Gitee主页:倔强的石头的gitee主页

   ⏩ 文章专栏:《数据结构与算法 经典例题》C语言

                                  期待您的关注

1b7335aca73b41609b7f05d1d366f476.gif

目录

​​一、问题描述 

二、前置知识

三、解题思路

原理:

 图解:

注:

四、C语言实现代码 

🍃栈实现代码:

🍃栈实现队列代码:

🍃测试文件及结果:


​​一、问题描述 

原题出自

232. 用栈实现队列 - 力扣(LeetCode)

二、前置知识

关于栈的详细讲解请阅读这篇文章

【数据结构与算法】使用数组实现栈:原理、步骤与应用-CSDN博客

 关于队列的详细讲解请阅读这篇文章

【数据结构与算法】使用单链表实现队列:原理、步骤与应用-CSDN博客

三、解题思路

使用两个栈(Stack)来实现队列(Queue)的功能是一个经典的算法问题。栈和队列在数据结构上是两种完全不同的类型(栈是后进先出,队列是先进先出),解决问题的关键就在于如何巧妙地利用两个栈的后进先出的特性来模拟队列先进先出的行为。

原理:

  1. 结构定义我们定义两个栈,stack1 和 stack2。其中一个栈(例如 stack1)用于入队操作,另一个栈(例如 stack2)用于出队操作。
  2. 入队操作所有元素都压入 stack1
  3. 出队操作
    • 如果 stack2 不为空,直接从 stack2 弹出栈顶元素,作为出队元素。
    • 如果 stack2 为空,则将 stack1 中的所有元素逐个弹出并压入 stack2(这个操作实际上是将 stack1 的元素反转后压入 stack2),然后再从 stack2 弹出栈顶元素,作为出队元素。
  4. 取队首元素类似出队操作,只是最后支取栈顶元素,不出栈

 图解:

(为方便理解对队列的结构进行了简化)

取队首元素类似于出队列,只是取出的元素不出栈

注:

另外还有一种可行的实现方式:

结构定义一个栈用来出队列和入队列,另一个栈保持为空,只用来移动数据

  1. 入队列都入到非空栈
  2. 出队列先将非空栈的所有元素(除了最后一个)移到空栈,最后的元素出栈并返回,并将移出的元素移动回来恢复顺序
  3. 取队首元素先将非空栈的所有元素(除了最后一个)移到空栈,最后的元素返回,再将移出的元素移动回来恢复顺序

这种方法在理论上是可行的,只不过每次出队列或取队首元素都需要将栈的元素移动两遍,效率比较低,因此这里就不给出实现代码了,建议使用第一种方式

四、C语言实现代码 

🍃栈实现代码:

// 支持动态增长的栈
typedef int STDataType;//对数据类型重命名,方便后期修改类型
typedef struct Stack
{STDataType* a;int top;		// 栈顶int capacity;  // 容量 
}Stack;//定义结构同时重命名
// 初始化栈 
void StackInit(Stack* ps)
{assert(ps);ps->a = NULL;ps->top = ps->capacity = 0;
}// 入栈 
void StackPush(Stack* ps, STDataType data)
{assert(ps);//判断是否需要扩容if (ps->top == ps->capacity){int newcapa = ps->capacity == 0 ? 4 : 2 * (ps->capacity);STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapa);if (tmp == NULL){perror("realloc\n");exit(1);}ps->a = tmp;ps->capacity = newcapa;}//确定空间足够之后再插入数据ps->a[ps->top] = data;ps->top++;
}// 出栈 
void StackPop(Stack* ps)
{assert(ps);assert(ps->top);ps->top--;
}// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{assert(ps);assert(ps->top);return ps->a[ps->top-1];
}// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
int StackEmpty(Stack* ps)
{assert(ps);return ps->top == 0;
}// 销毁栈 
void StackDestroy(Stack* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}

🍃栈实现队列代码:

typedef struct {Stack pushst;//入数据的栈Stack popst;//出数据的栈
} MyQueue;MyQueue* myQueueCreate() //初始化
{MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));StackInit(&(obj->pushst));StackInit(&(obj->popst));return obj;
}void myQueuePush(MyQueue* obj, int x) //模拟入队列
{assert(obj);StackPush(&(obj->pushst), x);//入队列直接插入到pushst栈
}int myQueuePop(MyQueue* obj) //模拟出队列
{assert(obj);assert(!StackEmpty(&(obj->popst)) || !StackEmpty(&(obj->pushst)));//首先两个栈不能都为空if (StackEmpty(&(obj->popst)))//如果popst栈为空,把数据倒过去{while (obj->pushst.top){StackPush(&(obj->popst), StackTop(&(obj->pushst)));StackPop (&(obj->pushst));}}int top = StackTop(&(obj->popst));StackPop(&(obj->popst));//再从popst栈出数据return top;
}int myQueuePeek(MyQueue* obj) //模拟取队列首元素
{assert(obj);assert(!StackEmpty(&(obj->popst)) || !StackEmpty(&(obj->pushst)));if (StackEmpty(&(obj->popst)))//如果popst栈为空,把数据倒过去{while (obj->pushst.top){StackPush(&(obj->popst), StackTop(&(obj->pushst)));StackPop(&(obj->pushst));}}return StackTop(&(obj->popst));
}bool myQueueEmpty(MyQueue* obj) //模拟队列判空
{return StackEmpty(&(obj->pushst)) && StackEmpty(&(obj->popst));
}void myQueueFree(MyQueue* obj) //销毁
{StackDestroy(&(obj->pushst));StackDestroy(&(obj->popst));free(obj);obj = NULL;
}

🍃测试文件及结果:

void test2()
{MyQueue* Queue = myQueueCreate();if (myQueueEmpty(Queue))printf("队列空\n");elseprintf("队列非空\n");myQueuePush(Queue, 1);myQueuePush(Queue, 2);myQueuePush(Queue, 3);myQueuePush(Queue, 4);printf("队首元素 %d\n", myQueuePeek(Queue));if (myQueueEmpty(Queue))printf("队列空\n");elseprintf("队列非空\n");while (!myQueueEmpty(Queue)){printf("%d ", myQueuePop(Queue));}printf("\n");if (myQueueEmpty(Queue))printf("队列空\n");elseprintf("队列非空\n");myQueueFree(Queue);
}

相关文章:

【数据结构与算法 经典例题】使用栈实现队列(图文详解)

💓 博客主页:倔强的石头的CSDN主页 📝Gitee主页:倔强的石头的gitee主页 ⏩ 文章专栏:《数据结构与算法 经典例题》C语言 期待您的关注 目录 ​​一、问题描述 二、前置知识 三、解题思路 原理: 图解&…...

不知大家信不信,竟有这么巧的事,我领导的老婆,竟然是我老婆的下属,我在想要不要利用下这层关系,改善下领导对我的态度,领导怕老婆

职场如战场,每个人都身不由己。每天上班,除了要面对堆积如山的工作,还要小心应对来自领导的“狂风暴雨”。最近,我无意间发现领导一个秘密,这个秘密让我对职场关系和人性都产生了新的思考。 故事要从那天晚上说起。我…...

使用pkg -r 命令选项向jail虚拟子系统里安装软件@FreeBSD

刷FreeBSD 论坛的时候,看到这样一招:使用pkg -r选项,往jail等虚拟机子系统里安装软件。jails - How to install a pkg offline into a jail? | The FreeBSD Forums rootfbhost:~ # pkg pkg: not enough arguments Usage: pkg [-v] [-d] [-l…...

Go语言开发框架GoFly已集成数据可视化大屏开发功能,让开发者只专注业务开发,本文指导大家如何使用

前言 框架提供数据大屏开发基础,是考虑当前市场软件应用有一大部分是需要把业务数据做出大屏,很多政府项目对大屏需求特别高,还有生产企业项目也对大屏有需求,没有提供基础规范的后台框架,在开发大屏需要很多时间去基…...

PR模板 | RGB特效视频标题模板Titles | MOGRT

RGB特效视频标题模板mogrt免费下载 4K分辨率(38402160) 支持任何语言 友好的界面 输入和输出动画 快速渲染 视频教程 免费下载:https://prmuban.com/39055.html 更多pr模板视频素材下载地址:https://prmuban.com...

python替换文件内容

# 打开文件with open(name, r) as file:content file.read()# 替换内容old_string binarynew_string cc_library_sharedcontent content.replace(old_string, new_string)# 写回文件with open(name, w) as file:file.write(content)...

SD-WAN是什么?它有哪些应用领域?

随着企业业务的不断扩展和数字化转型的加速,传统网络架构已无法满足企业对高效、灵活和安全网络连接的需求。在此背景下,SD-WAN(软件定义广域网)应运而生,为企业带来了全新的网络连接体验。本文将详细介绍SD-WAN网络及…...

PHP-CGI的漏洞(CVE-2024-4577)

通过前两篇文章的铺垫,现在我们可以了解 CVE-2024-4577这个漏洞的原理 漏洞原理 CVE-2024-4577是CVE-2012-1823这个老漏洞的绕过,php cgi的老漏洞至今已经12年,具体可以参考我的另一个文档 简单来说,就是使用cgi模式运行的PHP&…...

人工智能前沿讲座——AIGC

目录 前情提要 一、什么是AIGC AIGC与传统的AI有何区别? 二、发展历程 GAN 生成对抗网络 大模型与Transformer Transformer\BERT\GPT 扩散模型和稳定扩散模型 三、AIGC的发展应用 新质生产力 前情提要 小学期某一门课的笔记,老师名字隐去&…...

CCF 第33次CCF计算机软件能力认证第二题

相似度计算 刷新 时间限制: 1.0 秒 空间限制: 512 MiB 下载题目目录(样例文件) 题目背景 两个集合的 Jaccard 相似度定义为:𝑆𝑖𝑚(𝐴,𝐵)∣&#x1d…...

python 学习积累

持续更新中 感受python的强大之case列举: 1. 生成的map list要经过json格式化写入文件,请用python实现这一需求 import json map{"name": "张三", "age": 18, "address": "北京"} list[] for i in …...

ARM day1总结

思维导图...

套路化编程:C# ListView 保存、恢复列宽度

初级代码游戏的专栏介绍与文章目录-CSDN博客 我的github:codetoys,所有代码都将会位于ctfc库中。已经放入库中我会指出在库中的位置。 这些代码大部分以Linux为目标但部分代码是纯C的,可以在任何平台上使用。 目录 技术基础 保存列头 删…...

python单元测试

文章目录 单元测试定义断言函数Test FixturesMockpatch装饰器模拟(首选)上下文管理器模拟手动模拟 测试实例 测试覆盖率pytest框架起步安装使用常用参数跳过测试pytest.fixtureconftest.py参数化测试 数据库查询的mock覆盖率 单元测试 定义 单元测试是…...

华为---静态路由-浮动静态路由及负载均衡(二)

7.2 浮动静态路由及负载均衡 7.2.1 原理概述 浮动静态路由(Floating Static Route)是一种特殊的静态路由,通过配置去往相同的目的网段,但优先级不同的静态路由,以保证在网络中优先级较高的路由,即主路由失效的情况下&#xff0c…...

Maven deploy上传远程私服失败

Failed to execute goal org.apache.maven.plugins:maven-deploy-plugin:2.8.2:deploy (default-deploy) on project 你的项目: Cannot deploy artifacts when Maven is in offline mode 解决方案&#xff1a; 1.IDEA把这个钩子去掉 2. settings.xml里把 <offline>标…...

通天星CMSV6车载定位监控平台 point_manage/merge SQL注入致RCE漏洞复现

0x01 产品简介 通天星CMSV6车载定位监控平台拥有以位置服务、无线3G/4G视频传输、云存储服务为核心的研发团队,专注于为定位、无线视频终端产品提供平台服务,通天星CMSV6产品覆盖车载录像机、单兵录像机、网络监控摄像机、行驶记录仪等产品的视频综合平台。 0x02 漏洞概述 …...

图像识别技术在人脸识别领域的新突破

图像识别技术在人脸识别领域的新突破主要体现在多个方面&#xff0c;这些突破不仅提高了人脸识别的准确性和效率&#xff0c;还拓展了其应用领域。以下是对这些新突破的详细归纳&#xff1a; 深度学习技术的应用&#xff1a; 深度学习技术&#xff0c;特别是卷积神经网络&…...

iview 组件里面的(任何一个月)整月日期全部选中_iview时间轴选中有历史记录日期

iview 组件里面的整月日期全部选中&#xff1a; ①&#xff1a;第一种是当前月的日期全部选中&#xff1a; 先上效果图&#xff1a;当前月分 获取到的值&#xff1a; 当前月的方法&#xff1a; // getDateStr() {// var curDate new Date();// var curMonth curDate.ge…...

Charles配置与API数据抓取

2024软件测试面试刷题&#xff0c;这个小程序&#xff08;永久刷题&#xff09;&#xff0c;靠它快速找到工作了&#xff01;&#xff08;刷题APP的天花板&#xff09;-CSDN博客跳槽涨薪的朋友们有福了&#xff0c;今天给大家推荐一个软件测试面试的刷题小程序。https://blog.c…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

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

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

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...