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

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

逻辑回归暴力训练预测金融欺诈

简述 「使用逻辑回归暴力预测金融欺诈&#xff0c;并不断增加特征维度持续测试」的做法&#xff0c;体现了一种逐步建模与迭代验证的实验思路&#xff0c;在金融欺诈检测中非常有价值&#xff0c;本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...