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

【leetcode】225.用队列实现栈

分析:

队列遵循先入先出的原则,栈遵循后入先出的原则

也就是说,使用队列实现栈时,入队操作正常,但是出队要模拟出栈的操作,我们需要访问的是队尾的元素;题目允许使用两个队列,我们可以先将存有数据的队列中除队尾元素外的所有元素依次出队,存入空队列中,再访问原队列中的队头元素即可

1.使用两个队列构造栈:

C语言中没有定义队列的结构,我们需要自定义队列及其相关操作

如下:结构MyStack由两个队列结构q1和q2构成

为我们创建的栈结构进行动态内存申请并进行初始化

//由两个队列构成栈结构
typedef struct {Queue q1;Queue q2;} MyStack;
//创建栈
MyStack* myStackCreate() {//myStack未具有两个队列的栈结构类型MyStack* obj = (MyStack*)malloc(sizeof(MyStack));//内存开辟失败if(obj == NULL){perror("malloc fail");exit(-1);}//开辟成功,初始化else{QueueInit(&obj->q1);QueueInit(&obj->q2);}return obj;
}
2.压栈操作

模拟栈的压栈操作,数据正常入队即可

📖Note:

我们要将数据插入非空的队列,保证每次都存在一个空队列可以进行数据的存储

void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}}
3.移除并返回栈顶元素

模拟栈的出栈操作:访问并移除的是非空队列的队尾元素

步骤:将存有数据的队列中除队尾元素外的所有元素依次出队,存入空队列中,再访问并移除原队列中的队头元素即可,如下图:

上述操作后,q1和q2的结构如下:

此时,将队列q1中的元素(相当于后入的栈顶元素)先存储,再出队列q1(即清空队列q1,供下次压栈操作使用),返回存储的值即可

int myStackPop(MyStack* obj) {Queue* empty = &obj->q1;Queue* nonempty = &obj->q2;if(!QueueEmpty(&obj->q1)){nonempty = &obj->q1;	empty = &obj->q2;	}//非空队列前n-1个入空队列并出队,剩下最后一个即为栈顶元素while(QueueSize(nonempty) > 1){QueuePush(empty,QueueFront(nonempty));QueuePop(nonempty);}int top = QueueFront(nonempty);QueuePop(nonempty);//清空队列return top;
}
4.返回栈顶元素

栈顶元素即非空队列的队尾数据

int myStackTop(MyStack* obj) { if(!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}
5.判断是否为空栈 

myStack是由两个队列构成的栈结构,当两个队列都为空时栈即为空

bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
6.空间释放

创建栈时为其动态申请了空间,操作结束需要进行空间释放,否则会造成内存泄漏

void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);
}

 完整参考代码如下:

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;
}Queue;#define bool int
#define true 1
#define false 0//队列初始化
void QueueInit(Queue* pq);
//队列销毁
void QueueDestroy(Queue* pq);
//数据入队
void QueuePush(Queue* pq, QDataType x);
//数据出队
void QueuePop(Queue* pq);
//访问队头数据
QDataType QueueFront(Queue* pq);
//访问队尾数据
QDataType QueueBack(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);
//求队列的大小
int QueueSize(Queue* pq);//队列初始化
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;
}
//队列销毁
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* del = cur;cur = cur->next;free(del);}pq->head = pq->tail = NULL;
}
//数据入队
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}else{newnode->data = x;newnode->next = NULL;}//空队列时插入if (pq->tail == NULL){pq->head = pq->tail = newnode;}//非空队列时插入else{pq->tail->next = newnode;//链接新元素pq->tail = newnode;//更新队尾}
}
//数据出队
void QueuePop(Queue* pq)
{assert(pq);//空队列不能进行出队操作assert(!QueueEmpty(pq));//队列中只有一个元素if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* del = pq->head;pq->head = pq->head->next;free(del);del = NULL;}
}
//访问队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;}
//访问队尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);/*if (pq->tail == pq->head == NULL){return true;}else{return false;}*/return pq->head == NULL && pq->tail == NULL;
}
//求队列的大小
int QueueSize(Queue* pq)
{assert(pq);int size = 0;QNode* cur = pq->head;while (cur){size++;cur = cur->next;}return size;
}//由两个队列构成栈结构
typedef struct {Queue q1;Queue q2;} MyStack;
//创建栈
MyStack* myStackCreate() {//myStack未具有两个队列的栈结构类型MyStack* obj = (MyStack*)malloc(sizeof(MyStack));//内存开辟失败if(obj == NULL){perror("malloc fail");exit(-1);}//开辟成功,初始化else{QueueInit(&obj->q1);QueueInit(&obj->q2);}return obj;
}
void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}}int myStackPop(MyStack* obj) {Queue* empty = &obj->q1;Queue* nonempty = &obj->q2;if(!QueueEmpty(&obj->q1)){nonempty = &obj->q1;	empty = &obj->q2;	}//非空队列前n-1个入空队列并出队,剩下最后一个即为栈顶元素while(QueueSize(nonempty) > 1){QueuePush(empty,QueueFront(nonempty));QueuePop(nonempty);}int top = QueueFront(nonempty);QueuePop(nonempty);//清空队列return top;
}
//栈顶元素即非空队列的队尾数据
int myStackTop(MyStack* obj) { if(!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);
}

相关文章:

【leetcode】225.用队列实现栈

分析&#xff1a; 队列遵循先入先出的原则&#xff0c;栈遵循后入先出的原则 也就是说&#xff0c;使用队列实现栈时&#xff0c;入队操作正常&#xff0c;但是出队要模拟出栈的操作&#xff0c;我们需要访问的是队尾的元素&#xff1b;题目允许使用两个队列&#xff0c;我们可…...

机器学习中XGBoost算法调参技巧

本文将详细解释XGBoost中十个最常用超参数的介绍&#xff0c;功能和值范围&#xff0c;及如何使用Optuna进行超参数调优。 对于XGBoost来说&#xff0c;默认的超参数是可以正常运行的&#xff0c;但是如果你想获得最佳的效果&#xff0c;那么就需要自行调整一些超参数来匹配你…...

第1章:计算机网络体系结构

文章目录 1.1 计算机网络 概述1.概念2.组成3.功能4.分类5.性能指标1.2 计算机网络 体系结构&参考模型1.分层结构2.协议、接口、服务3.ISO/OSI模型4.TCP/IP模型1.1 计算机网络 概述 1.概念 2.组成 1.组成部分&...

【Java 动态数据统计图】动态数据统计思路Demo(动态,排序,containsKey)三(115)

上代码&#xff1a; import java.util.ArrayList; import java.util.HashMap; import java.util.Iterator; import java.util.LinkedList; import java.util.List; import java.util.Map;public class day10 {public static void main(String[] args) {List<Map<String,O…...

【游戏评测】河洛群侠传一周目玩后感

总游戏时长接近100小时&#xff0c;刚好一个月。 这两天费了点劲做了些成就&#xff0c;刷了等级&#xff0c;把最终决战做了。 总体感觉还是不错的。游戏是开放世界3D游戏&#xff0c;Unity引擎&#xff0c;瑕疵很多&#xff0c;但胜在剧情扎实&#xff0c;天赋系统、秘籍功法…...

java新特性之Lambda表达式

函数式编程 关注做什么&#xff0c;不关心是怎么实现的。为了实现该思想&#xff0c;java有了一种新的语法格式&#xff0c;Lambda表达式。Lambda本质是匿名内部类对象&#xff0c;是一个函数式接口。函数式接口表示接口内部只有一个抽象方法。使用该语法可以大大简化代码。 …...

【考研数学】线形代数第三章——向量 | 2)向量组相关性与线性表示的性质,向量组的等价、极大线性无关组与秩

文章目录 引言二、向量组的相关性与线性表示2.3 向量组相关性与线性表示的性质 三、向量组等价、向量组的极大线性无关组与秩3.1 基本概念 写在最后 引言 承接前文&#xff0c;我们来学习学习向量组相关性与线性表示的相关性质 二、向量组的相关性与线性表示 2.3 向量组相关性…...

Java中调用Linux脚本

在Java中&#xff0c;可以使用ProcessBuilder类来调用Linux脚本。以下是一个简单的示例&#xff0c;展示了如何在Java中调用Linux脚本&#xff1a; 创建一个Linux脚本文件&#xff08;例如&#xff1a;myscript.sh&#xff09;&#xff0c;并在其中编写需要执行的命令。确保脚…...

Nexus 如何配置 Python 的私有仓库

Nexus 可作为一个代理来使用。 针对一些网络环境不好的公司&#xff0c;可以通过配置 Nexus 来作为远程的代理。 Group 概念 Nexus 有一个 Group 的概念&#xff0c;我们可以认为一个 Nexus 仓库的 Group 就是很多不同的仓库的集合。 从下面的配置中我们可以看到&#xff0…...

Maven 配置文件修改及导入第三方jar包

设置java和maven的环境变量 修改maven配置文件 &#xff08;D:\app\apache-maven-3.5.0\conf\settings.xml&#xff0c;1中环境变量对应的maven包下的conf&#xff09; 修改131行左右的mirror&#xff0c;设置阿里云的仓库地址 <mirror> <id>alimaven</id&g…...

jmeter CSV 数据文件设置

创建一个CSV数据文件&#xff1a;使用任何文本编辑器创建一个CSV文件&#xff0c;将测试数据按照逗号分隔的格式写入文件中。例如&#xff1a; room_id,arrival_date,depature_date,bussiness_date,order_status,order_child_room_id,guest_name,room_price 20032,2023-8-9 14:…...

【SA8295P 源码分析】20 - GVM Android Kernel NFS Support 配置

【SA8295P 源码分析】20 - GVM Android Kernel NFS Support 配置 系列文章汇总见:《【SA8295P 源码分析】00 - 系列文章链接汇总》 本文链接:《【SA8295P 源码分析】20 - GVM Android Kernel NFS Support 配置》 # make menuconfigFile systems ---> [*] Network File Sy…...

c++都补了c语言哪些坑?

目录 1.命名空间 1.1 定义 1.2 使用 2.缺省参数 2.1 概念 2.2 分类 3.函数重载 4.引用 4.1 概念 4.2 特性 4.3 常引用 4.4 引用和指针的区别 5.内联函数 1.命名空间 在 C/C 中&#xff0c;变量、函数和后面要学到的类都是大量存在的&#xff0c;这些变量、函数和类的名称将…...

【C语言】C语言用数组算平均数,并输出大于平均数的数

题目 让用户输入一系列的正整数&#xff0c;最后输入“-1”表示输入结束&#xff0c;然后程序计算出这些数的平均数&#xff0c;最后输出输入数字的个数和平均数以及大于平均数的数 代码 #include<stdio.h> int main() {int x;double sum 0;int cnt 0;int number[100…...

「UG/NX」Block UI 体收集器BodyCollector

✨博客主页何曾参静谧的博客📌文章专栏「UG/NX」BlockUI集合📚全部专栏「UG/NX」NX二次开发「UG/NX」BlockUI集合「VS」Visual Studio「QT」QT5程序设计「C/C+&#...

金九银十面试题之《JVM》

&#x1f42e;&#x1f42e;&#x1f42e; 辛苦牛&#xff0c;掌握主流技术栈&#xff0c;包括前端后端&#xff0c;已经7年时间&#xff0c;曾在税务机关从事开发工作&#xff0c;目前在国企任职。希望通过自己的不断分享&#xff0c;可以帮助各位想或者已经走在这条路上的朋友…...

wireshark | 过滤筛选总结

wireshark 是一款开源抓包工具。比如与服务器的请求响应、tcp三次握手/四次挥手 场景&#xff1a;在linux环境下使用tcpdump -w 然后把爬的数据写入指定的XXX.pcap 然后在wireshark中导入该文件XXX.pcap 使用下面的过滤方式进行过滤 分析数据就可以了 #直接看 不需要硬背 和s…...

list使用

list的使用于string的使用都类似&#xff0c;首先通过查阅来看list有哪些函数&#xff1a; 可以看到函数还是蛮多的&#xff0c;我们值重点一些常用的和常见的&#xff1a; 1.关于push_back,push_front,和对应迭代器的使用 //关于push_back和push_front void test_list1() {l…...

【图解】多层感知器(MLP)

图片是一个多层感知器&#xff08;MLP&#xff09;的示意图&#xff0c;它是一种常见的神经网络模型&#xff0c;用于从输入到输出进行非线性映射。图片中的网络结构如下&#xff1a;...

React(8)

千锋学习视频https://www.bilibili.com/video/BV1dP4y1c7qd?p72&spm_id_frompageDriver&vd_sourcef07a5c4baae42e64ab4bebdd9f3cd1b3 1.React 路由 1.1 什么是路由&#xff1f; 路由是根据不同的 url 地址展示不同的内容或页面。 一个针对React而设计的路由解决方案…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...