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

leetcode:225. 用队列实现栈

一、题目

链接:225. 用队列实现栈 - 力扣(LeetCode)

函数原型:

typedef struct { 

} MyStack;

MyStack* myStackCreate() 

void myStackPush(MyStack* obj, int x) 

int myStackPop(MyStack* obj) 

int myStackTop(MyStack* obj) 

bool myStackEmpty(MyStack* obj) 

void myStackFree(MyStack* obj) 

二、思路

利用队列实现栈:

1.我的栈的结构

“我的栈”是一个结构体,存放两个队列即可

2.我的栈创建及其初始化

函数返回值是“我的栈”结构体指针,动态申请一个“我的栈”大小内存空间,然后初始化“我的栈”结构体中中的两个队列,最后返回“我的栈”的结构体指针

3.我的栈入栈

“我的栈”中有两个队列,选择一个空队列进行存储数据。由于栈的入栈和队列的入队都是从尾部进行存储数据的,所以直接对空队列进行入队操作即可。

如何找到空队列?

利用假设法,假设q1为空队列,q2为非空队列;判断q1是否为空,如果不为空,则将空队列设为q2,非空队列设为q1.

4.我的栈出栈

由于栈删除元素是从栈顶删除,而队列删除元素是从队头删除,所以需要先将非空队列中的前n-1个元素出队并入队到空队列中,第n个元素直接出队无需入队。即可完成“我的栈”的出栈。

5.我的栈取栈顶元素

取栈顶元素是在栈尾部进行的,所以可以对非空队列的取队尾元素。

6.我的栈判空

只要对两个队列判空即可,只有当两个队列都为空时,“我的栈”才判断为空。

7.我的栈销毁

首先对“我的栈”中两个队列进行队列销毁,然后再对动态申请的“我的栈”空间进行动态内存释放。

三、代码

typedef int QDataType;//队列的结构定义
typedef struct QueueNode{QDataType val;struct QueueNode *next;
}QNode;//用结构体管理队列
typedef struct Queue{QNode* phead;QNode* ptail;int size;
}Queue;//队列的初始化
void QueueInit(Queue* pq)
{pq->phead=NULL;pq->ptail=NULL;pq->size=0;
}//入队
void QueuePush(Queue *pq,QDataType x)
{assert(pq);QNode *newnode=(QNode*)malloc(sizeof(QNode));if(newnode==NULL){perror("malloc fail");exit(-1);}newnode->val=x;newnode->next=NULL;if(pq->phead==NULL)//队列为空pq->phead=pq->ptail=newnode;else{pq->ptail->next=newnode;pq->ptail=newnode;}pq->size++;
}//出队
void QueuePop(Queue* pq)
{assert(pq);assert(pq->phead);//空队列if(pq->phead==pq->ptail){pq->ptail=NULL;}QNode* tmp=pq->phead;pq->phead=tmp->next;free(tmp);tmp=NULL;pq->size--;
}//取队头元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}//取队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}//判空
bool QueueEmpty(Queue *pq)
{assert(pq);return pq->phead==NULL;
}//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode *cur=pq->phead;while(cur){QNode* tmp=cur;cur=cur->next;free(tmp);tmp=NULL;}pq->phead=pq->ptail=NULL;pq->size=0;
}typedef struct {Queue q1;Queue q2;
} MyStack;//我的栈创建及其初始化
MyStack* myStackCreate() {MyStack *ps=(MyStack*)malloc(sizeof(MyStack));QueueInit(&ps->q1);QueueInit(&ps->q2);return ps;
}void myStackPush(MyStack* obj, int x) {//利用假设法Queue *empty=&obj->q1;Queue *noneempty=&obj->q2;if(!QueueEmpty(&obj->q1)){empty=&obj->q2;noneempty=&obj->q1;}QueuePush(noneempty,x);//QueuePush(&obj->q1,x);
}//我的栈-出栈
int myStackPop(MyStack* obj) {// while(obj->q1.size>1)// {//     QueuePush(&obj->q2,QueueFront(&obj->q1));//     QueuePop(&obj->q1);//     //QueuePush(&obj->q2,QueuePop(&obj->q1));// }// int stackpop=QueueFront(&obj->q1);// QueuePop(&obj->q1);// while(obj->q2.size)// {//     QueuePush(&obj->q1,QueueFront(&obj->q2));//     QueuePop(&obj->q2);//     //QueuePush(&obj->q1,QueuePop(&obj->q2));// }// return stackpop;//利用假设法Queue *empty=&obj->q1;Queue *noneempty=&obj->q2;if(!QueueEmpty(&obj->q1)){empty=&obj->q2;noneempty=&obj->q1;}while(noneempty->size>1){QueuePush(empty,QueueFront(noneempty));QueuePop(noneempty);}int stackpop=QueueFront(noneempty);QueuePop(noneempty);return stackpop;
}//我的栈-出栈
int myStackTop(MyStack* obj) {Queue* empty=&obj->q1;Queue* noneempty=&obj->q2;if(!QueueEmpty(&obj->q1)){empty=&obj->q2;noneempty=&obj->q1;}return QueueBack(noneempty);
}//我的栈-判空
bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}//我的栈-销毁
void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}/*** Your MyStack struct will be instantiated and called as such:* MyStack* obj = myStackCreate();* myStackPush(obj, x);* int param_2 = myStackPop(obj);* int param_3 = myStackTop(obj);* bool param_4 = myStackEmpty(obj);* myStackFree(obj);
*/

相关文章:

leetcode:225. 用队列实现栈

一、题目 链接:225. 用队列实现栈 - 力扣(LeetCode) 函数原型: typedef struct { } MyStack; MyStack* myStackCreate() void myStackPush(MyStack* obj, int x) int myStackPop(MyStack* obj) int myStackTop(MyStack* obj) …...

Centos7安装GItLab(在线版)

基础环境准备 1.配置清华大学镜像仓库 新建仓库配置文件使用 vim /etc/yum.repos.d/gitlab-ce.repo 命令,输入以下内容,保存 [gitlab-ce] nameGitlab CE Repository baseurlhttps://mirrors.tuna.tsinghua.edu.cn/gitlab-ce/yum/el$releasever/ gpgcheck0 enabl…...

Linux入门笔记

1 Linux概述 Linux 是一套免费使用和自由传播的类 Unix 操作系统,是一个基于 POSIX 和 UNIX 的多用户、多任务、支持多线程和多 CPU 的操作系统。Linux 能运行主要的 UNIX 工具软件、应用程序和网络协议。它支持 32 位和 64 位硬件。Linux 继承了 Unix 以网络为核心…...

nvm for windows使用与node/npm/yarn的配置

1 下载 nvm for windows download – github 下拉到Assets, 下载.exe文件 2 安装 安装到如下文件夹中 目录可以自己选, 可以换别的名字, 自己记住即可 新手建议全部看完再进行个人配置, 或者使用与博主一致的路径 D:\DevelopEnvironment\nvm3 配置nvm使用的镜像 node_mir…...

打工人副业变现秘籍,某多/某手变现底层引擎-StableDiffusionWebUI界面基本布局和操作

一、界面设置 文生图:根据文本提示生成图像 图生图:图像生成图像;功能很强大,自己在后续使用中探索。 后期处理:图片处理;功能很强大,自己在后续使用中探索。 PNG信息:这是一个快速获取图片生成参数的便捷功能。如果图像是在SD里生成的,您可以使用“发送到”按钮将…...

01、pytest:帮助你编写更好的程序

简介 ​pytest框架可以很容易地编写小型、可读的测试,并且可以扩展以支持应用程序和库的复杂功能测试。使用pytest至少需要安装Python3.7或PyPy3。PyPI包名称为pytest 一个快速的例子 # content of test_sample.py def inc(x):return x1def test_ansewer():asser…...

C语言--每日选择题--Day37

第一题 1. 有以下说明语句:则下面引用形式错误的是() struct Student {int num;double score; };struct Student stu[3] {{1001,80}, {1002,75}, {1003,91}} struct Student *p stu; A:p->num B:(p).num C&#…...

Android 12 及以上授权精确位置和模糊位置

请求位置信息权限 为了保护用户隐私,使用位置信息服务的应用必须请求位置权限。 请求位置权限时,请遵循与请求任何其他运行时权限相同的最佳做法。请求位置权限时的一个重要区别在于,系统中包含与位置相关的多项权限。具体请求哪项权限以及…...

scp 指令详细介绍

目录 1. 基本语法 2. 例子 从本地到远程 从远程到本地 从远程到远程 使用端口和指定私钥 递归复制目录 3. 注意事项 如何拷贝文件的软链接 SCP(Secure Copy Protocol)是一种用于在计算机之间安全地传输文件的协议。它通过加密的方式在网络上安全…...

构建第一个事件驱动型 Serverless 应用

我相信,我们从不缺精彩的应用创意,我们缺少的把这些想法变成现实的时间和付出。 我认为,无服务器技术真的有助于最大限度节省应用开发和部署的时间,并且无服务器技术用可控的成本,实现了我的那些有趣的想法。 在我 2…...

特征与特征图的区别

1.特征图是什么? 特征图是指在卷积神经网络中,通过卷积操作从输入图像中提取出来的图像特征。在卷积神经网络中,每一层的输出都是一个三维张量,其中第三维表示特征图的数量。每个特征图都是由若干个卷积核对上一层的特征图进行卷…...

Linux学习笔记之七(shell脚本的基本语法)

Shell 1、Shell脚本2、常用运算符2、特殊语法4、关于变量的一些命令4.1、echo4.2、export4.3、read4.4、declare/typeset4.5、local4.6、unset 5、基本逻辑语法5.1、if判断5.2、for循环5.3、while循环5.4、case语句 6、函数定义7、多脚本链接 1、Shell脚本 学习shell脚本开发之…...

PySpark开发环境搭建常见问题及解决

PySpark环境搭建常见问题及解决 1、winutils.exe问题2、SparkURL问题3、set_ugi()问题 本文主要收录PySpark开发环境搭建时常见的一些问题及解决方案,并收集一些相关资源 1、winutils.exe问题 报错摘要: WARN Shell: Did not find winutils.exe: {} ja…...

supervisor管理启动重启,Java,Go程序Demo

简介 Supervisor 是一款 Python 开发的进程管理系统,允许用户监视和控制 Linux 上的进程,能将一个普通命令行进程变为后台守护进程,异常退出时能自动重启 1、安装 yum -y install supervisor2、配置默认配置文件 echo_supervisord_conf &g…...

HarmonyOs 4 (三) ArkTS语言

目录 一 认识ArkTs语言1.1 ArkTs1.2 基本结构 二 基本语法2.1 声明式UI2.1.1 创建组件2.1.1.1 无参数2.1.1.2 有参数2.1.1.3 组件样式2.1.1.4 组件方法2.1.1.5 组件嵌套 2.1.2 自定义组件2.1.2.1 基本结构2.1.2.2 成员函数/变量2.1.2.3 自定义组件的参数规定2.1.2.4 Build函数2…...

PostGIS学习教程九:空间连接

PostGIS学习教程九:空间连接 空间连接(spatial joins)是空间数据库的主要组成部分,它们允许你使用空间关系作为连接键(join key)来连接来自不同数据表的信息。我们认为“标准GIS分析”的大部分内容可以表示…...

C++ day56 两个字符串的删除操作 编辑距离

题目1:583 两个字符串的删除操作 题目链接:两个字符串的删除操作 对题目的理解 返回使两个单词word1和word2相同的最少删除多少个元素,两个单词至少包含一个字母,且仅包含小写字母 思路1:这道题与昨天的不同子序列…...

Android studio中如何生成jar包?

文章目录 需求背景目录结构gradle结构makeJar的语法解析 执行makeJar 任务拿到jar包 需求背景 别部门做C语言开发的同学开发了一个库,需要给我们Android端去调用。 我们拿到源码,首先需要做的是通过CMake去把C源码编译链接成动态库。 当然静态库也行&am…...

【2】基于多设计模式下的同步异步日志系统-设计模式

6. 相关技术知识补充 6.1 不定参函数 在初学C语⾔的时候,我们都⽤过printf函数进⾏打印。其中printf函数就是⼀个不定参函数,在函数内部可以根据格式化字符串中格式化字符分别获取不同的参数进⾏数据的格式化。 ⽽这种不定参函数在实际的使⽤中也⾮常…...

第十五届蓝桥杯模拟赛B组(第二期)C++

前言: 第一次做蓝桥模拟赛的博客记录,可能有很多不足的地方,现在将第十五届蓝桥杯模拟赛B组(第二期)的题目与代码与大家进行分享,我是用C做的,有好几道算法题当时自己做的也是一脸懵&#xff0c…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?

在工业自动化持续演进的今天&#xff0c;通信网络的角色正变得愈发关键。 2025年6月6日&#xff0c;为期三天的华南国际工业博览会在深圳国际会展中心&#xff08;宝安&#xff09;圆满落幕。作为国内工业通信领域的技术型企业&#xff0c;光路科技&#xff08;Fiberroad&…...

离线语音识别方案分析

随着人工智能技术的不断发展&#xff0c;语音识别技术也得到了广泛的应用&#xff0c;从智能家居到车载系统&#xff0c;语音识别正在改变我们与设备的交互方式。尤其是离线语音识别&#xff0c;由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力&#xff0c;广…...

【UE5 C++】通过文件对话框获取选择文件的路径

目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 &#xff0c;这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器&#xff0c;右键点击 .uproject 文件&#xff0c;选择 "Generate Visual Studio project files"&#xff0c;重…...