数据结构-用栈实现队列
前言:
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):
实现 MyQueue 类:
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空,返回 true ;否则,返回 false
说明:
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
目录
1.栈得实现
1.1结构体定义
1.2初始化栈
1.3压栈函数
1.4出栈函数
1.5返回栈顶函数
1.6判空函数
1.7销毁函数
2.题目解析
3.软件程序
3.1结构体定义及初始化
3.2进队函数
3.3出队函数
3.3返回队头元素
3.4判空函数
3.5销毁函数
1.栈得实现
这个题我是使用C语言解法进行解题得,因为要使用栈实现队列,所以首先我们要有栈得源函数,我在这里就把之前写过得栈得源函数按功能分类拷贝下来:代码如下:
1.1结构体定义
typedef int STDataType;
typedef struct Stack
{STDataType* a;//数组栈 int top;//栈顶int capacity;//容量
}ST;
1.2初始化栈
void StackInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = 0; // ps->top = -1;ps->capacity = 0;
}
1.3压栈函数
void StackPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newCapacity);if (tmp == NULL){printf("realloc fail\n");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;
}
1.4出栈函数
void StackPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));ps->top--;
}
1.5返回栈顶函数
STDataType StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top - 1];
}
1.6判空函数
bool StackEmpty(ST* ps)
{assert(ps);/*if (ps->top == 0){return true;}else{return false;}*/return ps->top == 0;
}
1.7销毁函数
bool StackEmpty(ST* ps)
{assert(ps);/*if (ps->top == 0){return true;}else{return false;}*/return ps->top == 0;
}
2.题目解析
我们知道队列是先进先出得,数据得进出如下图所示:
而栈得数据是先进后出, 如果上面数据进入栈内,先出的肯定就是数据6,不符合队列要求的数字1先出,所以我们要使用两个栈,一个栈pushST用来将所有数据存储进去,另一个栈popST用来出数据,这样就会把栈底得数据,在出数据得得栈中第一个出去,就满足队列得先进先出得原则。图解图下:
我们如果这时候想入数据,应该往pushST这个栈里面入,出数据就看popST栈中有无数据,没有数据就往里添pushST中得数据,如果有直接出,如下图所示:
3.软件程序
3.1结构体定义及初始化
typedef struct {
ST pushST; //定义一个专门存数据得栈
ST popST;//定义一个专门出数据得栈} MyQueue;MyQueue* myQueueCreate() {MyQueue *q = (MyQueue*)malloc(sizeof(MyQueue)); //定义一个结构体指针变量 指向两个栈StackInit(&q->pushST);//初始化StackInit(&q->popST);return q;}
3.2进队函数
void myQueuePush(MyQueue* obj, int x) {StackPush(&obj->pushST,x); // 开始存数据}
3.3出队函数
要先判断栈里面是否为空,为空要先进数据。题目要求 要返回出队得元素,所以我们要定义个变量用来存储出队得数据,代码如下:
int myQueuePop(MyQueue* obj) {//如果出栈得数据为空得话,要将存数据得栈内数据放进出栈if(StackEmpty(&obj->popST)){while(!StackEmpty(&obj->pushST)){StackPush(&obj->popST,StackTop(&obj->pushST));StackPop(&obj->pushST);}}int front = StackTop(&obj->popST);StackPop(&obj->popST);return front;
}
3.3返回队头元素
返回的队头元素即为,出栈得栈定元素,代码如下:
int myQueuePeek(MyQueue* obj) {if(StackEmpty(&obj->popST)){while(!StackEmpty(&obj->pushST)){StackPush(&obj->popST,StackTop(&obj->pushST));StackPop(&obj->pushST);}}//返回栈定数据return StackTop(&obj->popST);
}
3.4判空函数
如果pushST栈 以及popST栈都为空得话 则队列为空,直接用表达式真假判断即可,代码如下:
bool myQueueEmpty(MyQueue* obj) {return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);}
3.5销毁函数
我们需要先销毁两个栈,再销毁 自定义结构体指针变量得指向,图解如下:
代码如下:
void myQueueFree(MyQueue* obj) {StackDestroy(&obj->pushST);StackDestroy(&obj->popST);free(obj);}
相关文章:

数据结构-用栈实现队列
前言: 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty): 实现 MyQueue 类: void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int…...
第十四章 从 Windows 客户端控制 IRIS
文章目录第十四章 从 Windows 客户端控制 IRISIRISctlGetDirsSyntaxReturn ValuesIRISctlConfigStatusSyntaxReturn ValuesIRISctlControlSyntaxReturn Values第十四章 从 Windows 客户端控制 IRIS IRIS 为 Windows 客户端程序提供了一种机制来控制 IRIS 配置并启动 IRIS 进程…...

数据结构---双链表
专栏:数据结构 个人主页:HaiFan. 专栏简介:从零开始,数据结构!! 双链表前言双链表各接口的实现为要插入的值开辟一块空间BuyLN初始化LNInit和销毁LNDestory打印链表中的值LNPrint尾插LNPushBack和尾删LNPop…...

Windows 环境安装Scala详情
为了进一步学习Spark,必须先学习Scala 编程语言。首先开始Scala 环境搭建。温馨提示:本文是基于Windows 11 安装Scala 2.13.1 版本第一步:确保本机已经正确安装JDK1.8 环境第二步:Scala 官网下载我们所属scala版本文件。Scala 官网…...

C++ Qt自建网页浏览器
C Qt自建网页浏览器如需安装运行环境或远程调试,见文章底部个人QQ名片,由专业技术人员远程协助!前言这篇博客针对<<C Qt自建网页浏览器>>编写代码,代码整洁,规则,易读。 学习与应用推荐首选。文…...

Flink从入门到精通系列(四)
5、DataStream API(基础篇) Flink 有非常灵活的分层 API 设计,其中的核心层就是 DataStream/DataSet API。由于新版本已经实现了流批一体,DataSet API 将被弃用,官方推荐统一使用 DataStream API 处理流数据和批数据。…...

Nginx 配置实例-反向代理案例一
实现效果:使用nginx反向代理,访问 www.suke.com 直接跳转到本机地址127.0.0.1:8080 一、准备工作 Centos7 安装 Nginxhttps://liush.blog.csdn.net/article/details/125027693 1. 启动一个 tomcat Centos7安装JDK1.8https://liush.blog.csdn.net/arti…...

为什么北欧的顶级程序员数量远超中国?
说起北欧,很多人会想到寒冷的冬天,漫长的极夜,童话王国和圣诞老人,但是如果我罗列下诞生于北欧的计算机技术,恐怕你会惊掉下巴。Linux:世界上最流行的开源操作系统,最早的内核由Linus Torvalds开…...

vuex getters的作用和使用(求平均年龄),以及辅助函数mapGetters
getters作用:派生状态数据mapGetters作用:映射getters中的数据使用:方法名自定义,系统自动注入参数:state,每一个方法中必须有return,其return的结果被该方法名所接收。在state中声明数据listst…...

20230311给Ubuntu18.04下的GTX1080M安装驱动
20230311给Ubuntu18.04下的GTX1080M安装驱动 2023/3/11 12:50 2. 安装GTX1080驱动 安装 Nvidia 驱动 367.27 sudo add-apt-repository ppa:graphics-drivers/ppa 第一次运行出现如下的警告: Fresh drivers from upstream, currently shipping Nvidia. ## Curren…...
2023腾讯面试真题:
【腾讯】面试真题: 1、Kafka 是什么?主要应用场景有哪些? Kafka 是一个分布式流式处理平台。这到底是什么意思呢? 流平台具有三个关键功能: 消息队列:发布和订阅消息流,这个功能类似于消息…...
23种设计模式-建造者模式(Android应用场景介绍)
什么是建造者模式 建造者模式是一种创建型设计模式,它允许您使用相同的创建过程来生成不同类型和表示的对象。在本文中,我们将深入探讨建造者模式的Java实现,并通过一个例子来解释其工作原理。我们还将探讨如何在Android应用程序中使用建造者…...
English Learning - L2 语音作业打卡 双元音 [ʊə] [eə] Day17 2023.3.9 周四
English Learning - L2 语音作业打卡 双元音 [ʊə] [eə] Day17 2023.3.9 周四💌发音小贴士:💌当日目标音发音规则/技巧:🍭 Part 1【热身练习】🍭 Part2【练习内容】🍭【练习感受】🍓元音 [ʊə…...

【动态规划】多重背包问题,分组背包问题
Halo,这里是Ppeua。平时主要更新C语言,C,数据结构算法......感兴趣就关注我吧!你定不会失望。 🌈个人主页:主页链接 🌈算法专栏:专栏链接 我会一直往里填充内容哒! &…...

JAVA面向对象特征之——封装
4.封装 private关键字 是一个权限修饰符 可以修饰成员(成员变量和成员方法) 作用是保护成员不被别的类使用,被private修饰的成员只在本类中才能访问 针对private修饰的成员变量,如果需要被其他类使用,提供相应的操作 提供 “get变量名()…...

【数据结构】二叉树相关OJ题
文章目录一、单值二叉树二、检查两颗树是否相同三、判断一棵树是否为另一颗树的子树四、对称二叉树五、二叉树的前序遍历六、二叉树中序遍历七、二叉树的后序遍历八、二叉树的构建及遍历一、单值二叉树 单值二叉树 题目描述 如果二叉树每个节点都具有相同的值,那…...

Windows安装Hadoop
当初搭建Hadoop、Hive、HBase、Flink等这些没有截图写文,今为分享特重装。下载Hadoop下载地址:https://mirrors.tuna.tsinghua.edu.cn/apache/hadoop/以管理员身份运行cmd切换到所在目录执行start winrar x -y hadoop-3.3.4.tar.gz,解压。配置…...

ICG-Hydrazide,吲哚菁绿-酰肼,ICG-HZ结构式,溶于二氯甲烷等部分有机溶剂,
ICG-Hydrazide,吲哚菁绿-酰肼 中文名称:吲哚菁绿-酰肼 英文名称:ICG-Hydrazide 英文别名:ICG-HZ 性状:粉末或固体 溶剂:溶于二氯甲烷等部分有机溶剂 稳定性:-20℃密封保存、置阴凉干燥处、防潮 分子…...

【论文阅读】浏览器扩展危害-Helping or Hindering? How Browser Extensions Undermine Security
本文来源于ACM CCS 2022; https://dl.acm.org/doi/10.1145/3548606.3560685 摘要 “浏览器扩展”是轻量级的浏览器附加组件,使用各个浏览器特定的功能丰富的JavaScript api,为用户提供了额外的Web客户端功能,如改进网站外观和与…...

线性和非线性最小二乘问题的常见解法总结
线性和非线性最小二乘问题的各种解法 先看这篇博客,非常好:线性和非线性最小二乘问题的各种解法 1. 线性最小二乘问题有最优解 但是面对大型稀疏矩阵的时候使用迭代法效率更好。 迭代法 有Jacobi迭代法、 Seidel迭代法及Sor法 【数值分析】Jacobi、Se…...

Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

CMake基础:构建流程详解
目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...

微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...

Golang——7、包与接口详解
包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...

车载诊断架构 --- ZEVonUDS(J1979-3)简介第一篇
我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 做到欲望极简,了解自己的真实欲望,不受外在潮流的影响,不盲从,不跟风。把自己的精力全部用在自己。一是去掉多余,凡事找规律,基础是诚信;二是…...