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

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 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

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 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录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)简介第一篇

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