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

数据结构-用栈实现队列

前言:

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(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自建网页浏览器如需安装运行环境或远程调试&#xff0c;见文章底部个人QQ名片&#xff0c;由专业技术人员远程协助&#xff01;前言这篇博客针对<<C Qt自建网页浏览器>>编写代码&#xff0c;代码整洁&#xff0c;规则&#xff0c;易读。 学习与应用推荐首选。文…...

Flink从入门到精通系列(四)

5、DataStream API&#xff08;基础篇&#xff09; Flink 有非常灵活的分层 API 设计&#xff0c;其中的核心层就是 DataStream/DataSet API。由于新版本已经实现了流批一体&#xff0c;DataSet API 将被弃用&#xff0c;官方推荐统一使用 DataStream API 处理流数据和批数据。…...

Nginx 配置实例-反向代理案例一

实现效果&#xff1a;使用nginx反向代理&#xff0c;访问 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…...

为什么北欧的顶级程序员数量远超中国?

说起北欧&#xff0c;很多人会想到寒冷的冬天&#xff0c;漫长的极夜&#xff0c;童话王国和圣诞老人&#xff0c;但是如果我罗列下诞生于北欧的计算机技术&#xff0c;恐怕你会惊掉下巴。Linux&#xff1a;世界上最流行的开源操作系统&#xff0c;最早的内核由Linus Torvalds开…...

vuex getters的作用和使用(求平均年龄),以及辅助函数mapGetters

getters作用&#xff1a;派生状态数据mapGetters作用&#xff1a;映射getters中的数据使用&#xff1a;方法名自定义&#xff0c;系统自动注入参数&#xff1a;state&#xff0c;每一个方法中必须有return&#xff0c;其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 第一次运行出现如下的警告&#xff1a; Fresh drivers from upstream, currently shipping Nvidia. ## Curren…...

2023腾讯面试真题:

​【腾讯】面试真题&#xff1a; 1、Kafka 是什么&#xff1f;主要应用场景有哪些&#xff1f; Kafka 是一个分布式流式处理平台。这到底是什么意思呢&#xff1f; 流平台具有三个关键功能&#xff1a; 消息队列&#xff1a;发布和订阅消息流&#xff0c;这个功能类似于消息…...

23种设计模式-建造者模式(Android应用场景介绍)

什么是建造者模式 建造者模式是一种创建型设计模式&#xff0c;它允许您使用相同的创建过程来生成不同类型和表示的对象。在本文中&#xff0c;我们将深入探讨建造者模式的Java实现&#xff0c;并通过一个例子来解释其工作原理。我们还将探讨如何在Android应用程序中使用建造者…...

English Learning - L2 语音作业打卡 双元音 [ʊə] [eə] Day17 2023.3.9 周四

English Learning - L2 语音作业打卡 双元音 [ʊə] [eə] Day17 2023.3.9 周四&#x1f48c;发音小贴士&#xff1a;&#x1f48c;当日目标音发音规则/技巧:&#x1f36d; Part 1【热身练习】&#x1f36d; Part2【练习内容】&#x1f36d;【练习感受】&#x1f353;元音 [ʊə…...

【动态规划】多重背包问题,分组背包问题

Halo&#xff0c;这里是Ppeua。平时主要更新C语言&#xff0c;C&#xff0c;数据结构算法......感兴趣就关注我吧&#xff01;你定不会失望。 &#x1f308;个人主页&#xff1a;主页链接 &#x1f308;算法专栏&#xff1a;专栏链接 我会一直往里填充内容哒&#xff01; &…...

JAVA面向对象特征之——封装

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

【数据结构】二叉树相关OJ题

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

Windows安装Hadoop

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

ICG-Hydrazide,吲哚菁绿-酰肼,ICG-HZ结构式,溶于二氯甲烷等部分有机溶剂,

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

【论文阅读】浏览器扩展危害-Helping or Hindering? How Browser Extensions Undermine Security

本文来源于ACM CCS 2022&#xff1b; https://dl.acm.org/doi/10.1145/3548606.3560685 摘要 “浏览器扩展”是轻量级的浏览器附加组件&#xff0c;使用各个浏览器特定的功能丰富的JavaScript api&#xff0c;为用户提供了额外的Web客户端功能&#xff0c;如改进网站外观和与…...

线性和非线性最小二乘问题的常见解法总结

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

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

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

文章目录 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…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...

面试高频问题

文章目录 &#x1f680; 消息队列核心技术揭秘&#xff1a;从入门到秒杀面试官1️⃣ Kafka为何能"吞云吐雾"&#xff1f;性能背后的秘密1.1 顺序写入与零拷贝&#xff1a;性能的双引擎1.2 分区并行&#xff1a;数据的"八车道高速公路"1.3 页缓存与批量处理…...

第八部分:阶段项目 6:构建 React 前端应用

现在&#xff0c;是时候将你学到的 React 基础知识付诸实践&#xff0c;构建一个简单的前端应用来模拟与后端 API 的交互了。在这个阶段&#xff0c;你可以先使用模拟数据&#xff0c;或者如果你的后端 API&#xff08;阶段项目 5&#xff09;已经搭建好&#xff0c;可以直接连…...

JS红宝书笔记 - 3.3 变量

要定义变量&#xff0c;可以使用var操作符&#xff0c;后跟变量名 ES实现变量初始化&#xff0c;因此可以同时定义变量并设置它的值 使用var操作符定义的变量会成为包含它的函数的局部变量。 在函数内定义变量时省略var操作符&#xff0c;可以创建一个全局变量 如果需要定义…...