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做的,有好几道算法题当时自己做的也是一脸懵,…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...
C/C++ 中附加包含目录、附加库目录与附加依赖项详解
在 C/C 编程的编译和链接过程中,附加包含目录、附加库目录和附加依赖项是三个至关重要的设置,它们相互配合,确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中,这些概念容易让人混淆,但深入理解它们的作用和联…...
第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)
第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10pip3.10) 一:前言二:安装编译依赖二:安装Python3.10三:安装PIP3.10四:安装Paddlepaddle基础框架4.1…...
raid存储技术
1. 存储技术概念 数据存储架构是对数据存储方式、存储设备及相关组件的组织和规划,涵盖存储系统的布局、数据存储策略等,它明确数据如何存储、管理与访问,为数据的安全、高效使用提供支撑。 由计算机中一组存储设备、控制部件和管理信息调度的…...
计算机系统结构复习-名词解释2
1.定向:在某条指令产生计算结果之前,其他指令并不真正立即需要该计算结果,如果能够将该计算结果从其产生的地方直接送到其他指令中需要它的地方,那么就可以避免停顿。 2.多级存储层次:由若干个采用不同实现技术的存储…...
大模型真的像人一样“思考”和“理解”吗?
Yann LeCun 新研究的核心探讨:大语言模型(LLM)的“理解”和“思考”方式与人类认知的根本差异。 核心问题:大模型真的像人一样“思考”和“理解”吗? 人类的思考方式: 你的大脑是个超级整理师。面对海量信…...
