【栈和队列面试题】用栈实现队列(动图解析更清晰)

2023-09-21 13:16:30

leetcode 232.用栈实现队列

前言:用两个栈实现一个队列，模拟实现队列的功能。

💥🎈个人主页:​​​​​​Dream_Chaser～ 🎈💥

✨✨刷题专栏:http://t.csdn.cn/UlvTc

💨💨本篇内容:力扣上栈与队列面试题目

目录

leetcode 232.用栈实现队列

📌结构体类型的声明(MyQueue)

1️⃣队列的初始化(myQueueCreate)

2️⃣元素入队列(myQueuePush)

3️⃣获得队首元素(myQueuePeek)

4️⃣元素出队列(myQueuePop)

5️⃣判空(myQueueEmpty)

6️⃣销毁队列(myQueueFree)

总代码:

来源:232. 用栈实现队列 - 力扣（LeetCode）

📌结构体类型的声明(MyQueue)

        使用栈来模式队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈一个输入栈(pushst)，一个输出栈(popst)

typedef struct {
	 ST pushst;//输入栈
 	 ST popst;//输出栈
} MyQueue;//自定义队列结构体

1️⃣队列的初始化(myQueueCreate)

图解:

代码实现: 

MyQueue* myQueueCreate() {
    //使用malloc函数为MyQueue结构体分配内存空间,定义一个MyQueue*  的指针指向这块空间
        
		MyQueue* obj =(MyQueue*)malloc(sizeof(MyQueue));
		// 若分配失败
        if(obj == NULL)
		{//则打印错误信息
			perror("malloc fail");
			return NULL;//返回NULL
		}
		STInit(&obj->pushst);//初始化输入栈
		STInit(&obj->popst);//初始化输出栈
		return obj;//返回指向这个结构体的指针
}

2️⃣元素入队列(myQueuePush)

图解：在push数据的时候，只要数据放进输入栈就好

void myQueuePush(MyQueue* obj, int x) {
		STPush(&obj->pushst , x);//往队列导入元素 
}

3️⃣获得队首元素(myQueuePeek)

        假设我们需要在正常的队列中获取头部元素，那么应该怎么在这个自定义的队列中获得呢？

        那么就应该想清楚(Output stack)输出栈的出栈顺序，由下图可以看出，输入栈(Input stack)出栈顺序是:3 2 1,那么(Output stack)输出栈的入栈顺序是: 3 2 1,自然的，(Output stack)输出栈的出栈顺序就应该为1 2 3，那么(Output stack)输出栈的这个元素1就是队列的队首元素。

        这个函数的功能，先判断输出栈为空的前提下，循环条件是输入栈不为空,STPush()的功能就是把输入栈的元素，一个一个导入到输出栈，再一个一个把输入栈的元素弹出。直到输入栈为空栈时结束循环，返回此时的输出栈栈顶元素。

int myQueuePeek(MyQueue* obj) {
		if(STEmpty(&obj->popst))//若输出栈为空
		{	
            //结束条件是把输入栈元素全部挪动到输出栈为止
			while(!STEmpty(&obj->pushst))//输入栈不为空
			{   //获得输入栈头部元素,挪动到输出栈
				STPush(&obj->popst,STTop(&obj->pushst));
				STPop(&obj->pushst);//弹出输入栈元素
			}
		}
        //返回此时的输出栈栈顶元素
		return STTop(&obj->popst);
}

4️⃣元素出队列(myQueuePop)

 错误操作:假设输入栈数据没有全部导入到输出栈里，那么最终的出栈顺序会混乱的。

正确操作:        

        所以在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。

代码实现的部分需要注意的： 

        可以看出myQueuePop的实现，直接复用了myQueuePeek() ,要不然，对stEmpty判空的逻辑又要重写一遍。

代码实现: 

int myQueuePop(MyQueue* obj) {
		int front = myQueuePeek(obj);//代码复用,获得队列头部元素
		STPop(&obj->popst);//弹出元素
		return front;//获得队列的头部元素
}

5️⃣判空(myQueueEmpty)

如果进栈和出栈都为空的话，说明模拟的队列为空了。

bool myQueueEmpty(MyQueue* obj) {
		return STEmpty(&obj->pushst) 
		&&	STEmpty(&obj->popst);
}//判断队列是否为空，需要输入栈和输出栈两个同时为空，才会返回true

6️⃣销毁队列(myQueueFree)

和队列实现栈同样道理，需要先释放两个栈的空间，再释放结构体的空间，这样才确保不会内存泄露

//队列空间的释放
void myQueueFree(MyQueue* obj) {
		STDestroy(&obj->pushst);//释放输入栈
		STDestroy(&obj->popst);//释放输出栈
		free(obj);//释放自定义的队列
}

总代码:

#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<stdio.h>
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;//栈顶的位置
	int capacity;//栈的容量
}ST;
 
void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst,STDataType x);
void STPop(ST* pst);
STDataType STTop(ST* pst);
bool  STEmpty(ST* pst);
int STSize(ST*pst);


void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;//栈底
	
	//top不是下标
    //pst->top=-1;//指向栈顶元素
	pst->top = 0;//指向栈顶元素的下一个位置
	pst->capacity = 0;
}
 
void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
}
 
 
void STPush(ST* pst,STDataType x)
{
	if (pst->top == pst->capacity)
	{
		int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;//true,4.false,括2倍
 
		STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));//返回值地址相等就是原地扩容，不同就是异地扩
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;//返回的是realloc出来的内存块的地址
		pst->capacity = newCapacity;//把扩容后的空间大小赋值给栈容量
	}
	pst->a[pst->top] = x;//先放值
	pst->top++;//再++
}
 
 
void STPop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	pst->top--;
}
 
 
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
 
	return pst->a[pst->top - 1];
}
 
bool STEmpty(ST* pst)//栈为空返回true,不为空返回false
{
	//assert(pst);
	//if (pst->top == 0)
	//{
	//	return true;
	//}
	//else
	//{
	//	return false;
	//}
	return pst->top == 0;
}

int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}
 


typedef struct {
	 ST pushst;//输入栈
 	 ST popst;//输出栈
} MyQueue;//自定义队列

MyQueue* myQueueCreate() {
    //使用malloc函数为MyQueue结构体分配内存空间,定义一个MyQueue*  的指针指向这块空间
        
		MyQueue* obj =(MyQueue*)malloc(sizeof(MyQueue));
		// 若分配失败
        if(obj == NULL)
		{//则打印错误信息
			perror("malloc fail");
			return NULL;//返回NULL
		}
		STInit(&obj->pushst);//初始化输入栈
		STInit(&obj->popst);//初始化输出栈
		return obj;//返回指向这个结构体的指针
}

void myQueuePush(MyQueue* obj, int x) {
		STPush(&obj->pushst , x);//往队列导入元素 
}

int myQueuePop(MyQueue* obj) {
		int front = myQueuePeek(obj);//代码复用,获得队列头部元素
		STPop(&obj->popst);//弹出元素
		return front;//获得队列的头部元素
}


int myQueuePop(MyQueue* obj) {
	if(STEmpty(&obj->popst))//若输出栈为空
		{	
            //结束条件是把输入栈元素全部挪动到输出栈为止
			while(!STEmpty(&obj->pushst))//输入栈不为空
			{   //获得输入栈头部元素,挪动到输出栈
				STPush(&obj->popst,STTop(&obj->pushst));
				STPop(&obj->pushst);//弹出输入栈元素
			}
		}
        //返回此时的输出栈头部元素
		int front= STTop(&obj->popst);
		STPop(&obj->popst);//弹出元素
		return front;//获得队列的头部元素
}

int myQueuePeek(MyQueue* obj) {
		if(STEmpty(&obj->popst))//若输出栈为空
		{	
            //结束条件是把输入栈元素全部挪动到输出栈为止
			while(!STEmpty(&obj->pushst))//输入栈不为空
			{   //获得输入栈头部元素,挪动到输出栈
				STPush(&obj->popst,STTop(&obj->pushst));
				STPop(&obj->pushst);//弹出输入栈元素
			}
		}
        //返回此时的输出栈头部元素
		return STTop(&obj->popst);
}

bool myQueueEmpty(MyQueue* obj) {
		return STEmpty(&obj->pushst) 
		&&	STEmpty(&obj->popst);
}//判断队列是否为空，需要输入栈和输出栈两个同时为空，才会返回true

//队列空间的释放
void myQueueFree(MyQueue* obj) {
    //和队列实现栈同样道理，需要先释放两个栈的空间，再释放结构体的空间，这样才确保不会内存泄露
		STDestroy(&obj->pushst);//释放输入栈
		STDestroy(&obj->popst);//释放输出栈
		free(obj);//释放自定义的队列
}

代码执行: 

        本文结束，如有错误，欢迎指正，感谢你的来访！🚩

更多推荐

十二、LCD1602

十二、LCD1602介绍功能函数介绍引脚和应用电路时许结构功能函数#include<REGX52.H>//引脚定义sbitLCD_RS=P2^6;sbitLCD_RW=P2^5;sbitLCD_E=P2^7;#defineLCD_DataPortP0/***@briefLCD1602延时函数，12MHz调用可延时1ms

TCP/IP、DTN网络通信协议族

TCP/IP从19世纪60年代计算机网络发展开始，网络协议技术已经经历了半个多世纪的发展，地面互联网已经形成了以传输控制协议（TCP）/IP协议体系为主的网络架构。TCP/IP体系发源于计算机网络，是一种以主机为中心的网络协议体系，IP地址直接对应到主机，主机与主机之间的数据可靠传输采用“端到端原则”。随着移动通信技术

Kafka自带zookeeper---集群安装部署

kafka简介kafka官网：http://kafka.apache.org/kafka下载页面：http://kafka.apache.org/downloadskafka配置快速入门：http://kafka.apache.org/quickstart首先让我们看几个基本的消息系统术语：•Kafka将消息以topi

PCIE基础知识-3

PCIE三种传输方式：IO中断，DMA，peertopeer中断：PCI设备需要向内存（SDRAM）中写入一些数据，该PCI设备会向CPU请求一个中断，然后CPU首先先通过PCI总线把该PCI设备的数据读取到CPU内部的寄存器中，然后再把数据从内部寄存器写入到内存（SDRAM）中。DMA：直接内存访问（DMA，Dire

​CVPR 2023 | STAR Loss：减少人脸关键点标注歧义，实现人脸关键点SOTA精度

论文链接：https://arxiv.org/pdf/2306.02763.pdf代码链接：https://github.com/ZhenglinZhou/STAR要解决的问题：人脸关键点检测标注中存在语义歧义问题。语义歧义是指不同的标注者对同一个面部特征点的位置有不同的理解，导致标注结果不一致，影响模型的收敛和准确性

设计模式-代理模式

“阁下有什么问题可以和我的代理律师谈即可”，为什么会有律师这个职业呢？随着法律法规的逐步完善，日益复杂，导致大部分的普通民众掌握的法律知识明显不足，进而无法在合适的时间点进行维权、规避风险。可见，律师的作用就是利用自身的专业知识帮助案件当事人处理其无法处理的事情。不仅只有律师，生活中处处可见这种代理模式的存在，比如婚庆

麦肯锡：中国生成式AI市场现状和未来发展趋势

本文来自《麦肯锡中国金融业CEO季刊》，版权归麦肯锡所有。该季刊主要围绕生成式AI（以下简称“GenAI”）主题，通过4大章节共8篇文章，全面深入分析了GenAI对各主要行业的影响、价值链投资机会、中国GenAI市场现状和未来趋势以及企业如何布局GenAI，从而真正挖掘其价值。随着ChatGPT的火爆出圈，GenAI成

2023年8月京东空调行业品牌销售排行榜（京东数据报告）

鲸参谋监测的京东平台8月份空调市场销售数据已出炉！鲸参谋数据显示，今年8月份，京东平台上空调的销量将近146万，环比降低约44%，同比降低约37%；销售额为41亿+，环比下降约45%，同比下降约40%。可以看到，8月份空调市场整体下滑。*数据源于鲸参谋-行业趋势分析（来自公开渠道获取，数据仅供参考）空调市场中，格力品牌

Python编程指南：利用HTTP和HTTPS适配器实现智能路由

目录HTTP和HTTPS适配器什么是智能路由利用HTTP和HTTPS适配器实现智能路由总结在Python编程中，利用HTTP和HTTPS适配器实现智能路由是一项非常实用的技能。智能路由可以根据不同的条件选择不同的路由，从而提高网络性能和用户体验。在本文中，我们将介绍如何使用Python编程语言和HTTP/HTTPS适配

非对称加密、解密原理及openssl中的RSA示例代码

一、【原理简介】非对称加密非对称加密，也被称为公钥加密，其中使用一对相关的密钥：一个公钥和一个私钥。公钥用于加密数据，私钥用于解密数据。公钥可以公开分享，而私钥必须保密。密钥生成:当一个用户或设备希望使用非对称加密时，要生成一对密钥：一个公钥和一个私钥。这两个密钥是数学上相关的，但从公钥中计算出私钥在计算上是不可行的。

【操作系统笔记】内存寻址

物理寻址主存（内存）计算机主存也可以称为物理内存，内存可以看成由若干个连续字节大小的单元组成的数组每个字节都有一个唯一的物理地址（PhysicalAddress）CPU访问内存前，先拿到内存地址，然后，通过内存地址访问内存中数据指令总线的分工数据总线：负责传输实际数据的地址总线：负责传输数据地址的，用来确定到底把数据传

热文推荐
  1. 开发需知的文件加密与解密

    背景最近团队遇到一个小需求，存在两个系统A、B，系统A支持用户在线制作皮肤包，制作后的皮肤包用户可以下载后，导入到另外的系统B上。皮肤包本身的其实就是一个zip压缩包，系统B接收到压缩包后，解压并做一些常规的校验，比如版本、内容合法性校验等，整体功能也比较简单。但没想到啊，一帮测试人员对我们开发人员一顿输出，首先绕过系

  2. Spring Cloud Alibaba Nacos 2.2.3 (1) - 下载与数据库配置

    这里写自定义目录标题下载nacos修改配置文件application.properties执行数据库脚本下载nacosnacos在GitHub上有下载地址：https://github.com/alibaba/nacos/releases，可以选择任意版本下载。我下载的是2.2.3版本修改配置文件application

  3. LeetCode 面试题 04.08. 首个共同祖先

    文章目录一、题目二、C#题解一、题目设计并实现一个算法，找出二叉树中某两个节点的第一个共同祖先。不得将其他的节点存储在另外的数据结构中。注意：这不一定是二叉搜索树。例如，给定如下二叉树:root=[3,5,1,6,2,0,8,null,null,7,4]3/\51/\/\6208/\74点击此处跳转题目。示例1:输入:

  4. Kafka消费者组重平衡（二）

    文章目录概要重平衡通知机制消费组组状态消费端重平衡流程Broker端重平衡流程概要上一篇Kafka消费者组重平衡主要介绍了重平衡相关的概念，本篇主要梳理重平衡发生的流程。为了更好地观察，数据准备如下：kafka版本：kafka_2.13-3.2.1控制台创建topic(2个分区1个副本):bin/kafka-topic

  5. 详细指南：基于差分进化的马尔可夫链蒙特卡罗加速技术在MATLAB中的应用

    第一部分：概念简介与基础知识1.什么是马尔可夫链蒙特卡罗(MarkovChainMonteCarlo,MCMC)？马尔可夫链蒙特卡罗是一种通过马尔可夫链来估计复杂分布的统计方法。通过构建一个特定的马尔可夫链，使其平稳分布等于目标分布，我们可以从该马尔可夫链中抽取样本来估计目标分布的统计性质。2.差分进化(Differe

  6. 实战SRC漏洞挖掘全过程，流程详细【网络安全】

    前言记录一次完整的某SRC漏洞挖掘实战，为期一个多星期。文章有点长，请耐心看完，记录了完整的SRC漏洞挖掘实战渗透过程因为选择的幸运儿没有对测试范围进行规划，所以此次范围就是没有范围。先上主域名看一眼，看看能收集到什么有效信息：发现存在搜索框：测试点＋1对页面点点点没发现什么有用的页面。抓包看看，发现网站搭建了CDN，

  7. Elasticsearch：什么是向量和向量存储数据库，我们为什么关心？

    Elasticsearch从7.3版本开始支持向量搜索。从8.0开始支持带有HNSW的ANN向量搜索。目前Elasticsearch已经是全球下载量最多的向量数据库。它允许使用密集向量和向量比较来搜索文档。矢量搜索在人工智能和机器学习领域有许多重要的应用。有效存储和检索向量的数据库对于构建生产就绪的AI/ML服务至关重

  8. 您距离一个成熟安全的 DevOps 平台，只差一个迁移

    历经14年的发展后，DevOps已经不再是一个鲜为人知的术语，国内外众多企业在成熟方法论和复杂工具链的加持下，通过DevOps的落地实践实现了软件交付效率的提升。随着DevOps的深入发展，DevOps的市场规模也在进一步快速发展。根据ResearchandMarkets的调研数据，2020年全球DevOps市场规模大

  9. springboot和vue：阿里云云服务器ECS的购买与基础参数配置+XShell远程连接服务器

    云服务器ECS的特点弹性水平拓展的应用场景：譬如微博热搜爆了，则需要水平拓展。其他功能ECS一般提供自动宕机迁移、数据备份和回滚、系统性能报警等功能，稳定性更高阿里云服务器的购买（针对学生党学习自用）其他：推荐支付宝登录创建ECS登陆进去后可以从两个地方创建ECS。地方一：直接点击创建我的ECS（如果你没有买过的话）地