每日一题---OJ题: 用队列实现栈

片头

嗨! 小伙伴们,大家好! 今天我们一起来看看这道OJ题---用队列实现栈,话不多说,我们马上开始~

emmm,题目看似有点长,我们一起来分析分析!

我们都知道,栈的特点是后进先出(Last In First Out,简称 LIFO ),队列的特点是先进先出(First In First Out 简称 FIFO),明明两者的性质是相反的,怎么用队列实现栈呢?

屏幕前聪明的你应该已经知道了,哦! 一个队列肯定是实现不了的,那一个不行,两个队列总该可以吧!

嗯~聪明! 没错,的确是用两个队列实现,那么我们要怎样做呢?

思路一 :  ①保持一个队列存数据,一个队列为空 ②入数据,入到不为空的队列 ③出数据,借助空队列倒数据即可

首先,我们先定义队列的结构(这里我直接把代码拿出来)

队列的头文件 Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int ElemType;
typedef struct QueueNode {		//队列的每一个结点
	ElemType data;
	struct QueueNode* next;
}QNode;

typedef struct Queue {		   //队列
	QNode* front;			   //头结点
	QNode* rear;			   //尾结点
	int size;				   //队列的长度
}Queue;


//初始化队列
void QueueInit(Queue* q);
//队尾入队列
void QueuePush(Queue* q, ElemType x);
//队头出队列
void QueuePop(Queue* q);
//获取队列头部元素
ElemType QueueFront(Queue* q);
//获取队列队尾元素
ElemType QueueBack(Queue* q);
//获取队列中有效元素的个数
int QueueSize(Queue* q);
//检测队列是否为空
int QueueEmpty(Queue* q);
//销毁队列
void QueueDestroy(Queue* q);

定义队列的实现方法 Queue.c

#include"Queue.h"
//初始化队列
void QueueInit(Queue* q) {
	assert(q);
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
}
//队尾入队列
void QueuePush(Queue* q, ElemType x) {
	assert(q);
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	newNode->data = x;
	newNode->next = NULL;

	if (q->front == NULL) {
		q->front = q->rear = newNode;
	}
	else {
		q->rear->next = newNode;
		q->rear = newNode;
	}
	q->size++;
}
//队头出队列
void QueuePop(Queue* q) {
	assert(q);
	//0个结点
	assert(q->front != NULL);
	//1个结点
	//多个结点
	if (q->front->next == NULL) {
		free(q->front);
		q->front = q->rear = NULL;
	}else{
		QNode* del = q->front;
		q->front = q->front->next;
		free(del);
		del = NULL;
	}
	q->size--;

}
//获取队列头部元素
ElemType QueueFront(Queue* q) {
	assert(q);
	assert(q->front != NULL);

	return q->front->data;
}
//获取队列队尾元素
ElemType QueueBack(Queue* q) {
	assert(q);
	assert(q->rear != NULL);

	return q->rear->data;
}
//获取队列中有效元素的个数
int QueueSize(Queue* q) {
	assert(q);
	return q->size;
}
//检测队列是否为空
int QueueEmpty(Queue* q) {
	assert(q);
	return q->size == 0;
}
//销毁队列
void QueueDestroy(Queue* q) {
	assert(q);
	QNode* p = q->front;
	while (p != NULL) {
		QNode* Q = p->next;
		free(p);
		p = Q;
	}
	q->front = q->rear = NULL;
	q->size = 0;
}

OK,准备工作做好啦,接下来需要怎么做呢?

嗯,题目说,需要用两个队列实现栈,我们已经写出了队列的代码,接下来我们需要一一实现这些函数

别慌,咱们先来画个图哈~

①初始化2个队列(QueueInit)

假设这里有2个队列,分别为q1和q2,初始时均为空

②往其中一个空队列里插入元素(Push)

接着我们往其中一个队列(q1或者q2都可以)里面插入元素 1, 2, 3, 4

③删除元素（Pop）

然后我们想要删除最后一个元素,类似于栈里面的Pop,但是题目给的条件是队列,所以,如果我们用队列的方式Pop(删除)的话,只能删除队头的元素,也就是"1"

那怎么办呢? 很简单,不是有2个队列么,把非空队列的前 n-1 个元素放到另外一个队列(也就是空队列就好了呀)!

来看看例子:

第一次: 我们先获取q2里面的队头元素"1",把它拷贝放入q1中,再将这个值从q1中删除

第二次: 我们接着获取q2里面的队头元素"2",将它拷贝放入q1中, 再将这个值从q1中删除

第三次: 我们接着获取q2里面的队头元素"3",将它拷贝放入q1中, 再将这个值从q1删除

OK,现在q2队列里面只有"4",这一个元素了,相当于栈顶, 此时,我们只需要获取"4"这个元素,然后将它从q2队列里面删除就行了, 删除完"4"这个元素后,q2队列为空

④获取栈底元素(非空队列里面的最后一个元素)

诶,说到这里,如果我们想直接获取非空队列的最后一个元素(也就是栈顶元素),需不需要这么挪动元素呢?

答案是: 不需要啦! 还是上面这个例子,现在元素"4"已经被我们删除了,如果我们想从q1队列里面"1","2","3"元素中获取最后一个元素"3",相当于栈底元素,我们可以直接调用队列的QueueBack函数(获取队尾的元素),这样就不用挪动元素了。

⑤往非空队列里面继续插入新元素(Push)

那问题又来了, 如果我们此时想插入新元素"5",该怎么办呢?

哈哈哈,很简单,就直接把"5"插入到"3"的后面就可以了呀! 

道理我想都明白,那就是将新元素直接尾插到非空队列里面,方便下一次进行插入和删除。   

⑥判断栈(2个队列)是否为空

好啦,如何判断2个队列是否为空呢? 哈哈哈,so easy! 我们知道,当一个队列插入元素的时候,总有另外一个队列为空 ; 或者,当一个队列需要删除队尾元素的时候,总是需要将数据挪动到另外一个队列里面,然后获取这个队列的队尾元素,最后将这个元素删除,这个队列最后为空 。所以，不管怎么样，总有一个队列为空，所以，一个队列为空并不足以判断栈是否为空。只有当2个队列同时为空的时候，栈才为空。

⑦销毁栈

OK! 到这里,基本上关于栈的主要几个操作都实现了,接下来就是销毁操作咯! 毕竟,借了内存空间,就要归还嘛,免得内存泄漏,hhhhh~

怎么销毁由2个队列组成的栈呢? 很简单,就是将2个队列依次销毁,最后把我们在堆上malloc申请的MyStack结构体释放内存,归还给系统就可以啦!

欧克克~ 大功告成! 整道题的代码如下:

typedef int ElemType;
typedef struct QueueNode {		//队列的每一个结点
	ElemType data;
	struct QueueNode* next;
}QNode;

typedef struct Queue {		   //队列
	QNode* front;			   //头结点
	QNode* rear;			   //尾结点
	int size;				   //队列的长度
}Queue;


//初始化队列
void QueueInit(Queue* q);
//队尾入队列
void QueuePush(Queue* q, ElemType x);
//队头出队列
void QueuePop(Queue* q);
//获取队列头部元素
ElemType QueueFront(Queue* q);
//获取队列队尾元素
ElemType QueueBack(Queue* q);
//获取队列中有效元素的个数
int QueueSize(Queue* q);
//检测队列是否为空
int QueueEmpty(Queue* q);
//销毁队列
void QueueDestroy(Queue* q);

//初始化队列
void QueueInit(Queue* q) {
	assert(q);
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
}
//队尾入队列
void QueuePush(Queue* q, ElemType x) {
	assert(q);
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	newNode->data = x;
	newNode->next = NULL;

	if (q->front == NULL) {
		q->front = q->rear = newNode;
	}
	else {
		q->rear->next = newNode;
		q->rear = newNode;
	}
	q->size++;
}
//队头出队列
void QueuePop(Queue* q) {
	assert(q);
	//0个结点
	assert(q->front != NULL);
	//1个结点
	//多个结点
	if (q->front->next == NULL) {
		free(q->front);
		q->front = q->rear = NULL;
	}else{
		QNode* del = q->front;
		q->front = q->front->next;
		free(del);
		del = NULL;
	}
	q->size--;

}
//获取队列头部元素
ElemType QueueFront(Queue* q) {
	assert(q);
	assert(q->front != NULL);

	return q->front->data;
}
//获取队列队尾元素
ElemType QueueBack(Queue* q) {
	assert(q);
	assert(q->rear != NULL);

	return q->rear->data;
}
//获取队列中有效元素的个数
int QueueSize(Queue* q) {
	assert(q);
	return q->size;
}
//检测队列是否为空
int QueueEmpty(Queue* q) {
	assert(q);
	return q->size == 0;
}
//销毁队列
void QueueDestroy(Queue* q) {
	assert(q);
	QNode* p = q->front;
	while (p != NULL) {
		QNode* Q = p->next;
		free(p);
		p = Q;
	}
	q->front = q->rear = NULL;
	q->size = 0;
}


typedef struct {
    //在 MyStack 结构体里面分别定义两个队列
    Queue q1;           
    Queue q2;
} MyStack;


MyStack* myStackCreate() {
    //在堆里面用mallo申请空间给2个队列
    MyStack* Q =(MyStack*) malloc(sizeof(MyStack));

    //将2个队列初始化
    QueueInit(&Q->q1);
    QueueInit(&Q->q2);

    //将结构体指针Q返回
    return Q;

}

void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1)){      //若q1队列不为空,将新元素插入到q1
        QueuePush(&obj->q1,x);
    }else{                          //若q2不为空,将新元素插入到q2
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj) {
    Queue* pEmpy = &obj->q1;        //假设q1队列为空,q2队列不为空
    Queue* pNotEmpty = &obj->q2;    
    if(QueueEmpty(&obj->q2)){       //如果假设错误,那么q2队列为空,q1队列不为空
        pEmpy = &obj->q2;
        pNotEmpty = &obj->q1;
    }

    while(QueueSize(pNotEmpty) > 1){    //将非空队列的前n-1个元素倒入空队列
        int top = QueueFront(pNotEmpty);
        QueuePush(pEmpy,top);
        QueuePop(pNotEmpty);
    }
    int ret = QueueFront(pNotEmpty);
    QueuePop(pNotEmpty);
    return ret;                         //将非空队列里面的最后一个元素返回
}

int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1)){      //如果q1队列不为空,将q1队列的最后一个元素返回
        return QueueBack(&obj->q1);
    }else{
        return QueueBack(&obj->q2); //如果q2队列不为空,将q2队列的最后一个元素返回
    }
}

bool myStackEmpty(MyStack* obj) {
     //2个队列同时为空,才能算空
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);   
}

void myStackFree(MyStack* obj) {
    //将队列q1和队列q2都销毁
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    //将myStack销毁
    free(obj);
}

片尾

 今天我们学习了一道OJ题---用队列实现栈,里面包含了关于队列的基础知识和栈的基础知识,做完这道题能够帮助更好的理解栈和队列的性质,希望看完这篇文章能对友友们有所帮助 !   !   !

求点赞收藏加关注 !   !   !

谢谢大家 !   !   !

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/552937.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【记录】Python｜Selenium 下载 PDF 不预览不弹窗（2024年）

【记录】Python｜Selenium 下载 PDF 不预览不弹窗（2024年）

版本&#xff1a; Chrome 124Python 12Selenium 4.19.0 版本与我有差异不要紧&#xff0c;只要别差异太大比如 Chrome 用 57 之前的版本了&#xff0c;就可以看本文。 如果你从前完全没使用过、没安装过Selenium&#xff0c;可以参考这篇博客《【记录】Python3&#xff5c;Sele…
阅读更多...
求π的近似值（C语言）

求π的近似值（C语言）

一、N-S流程图&#xff1b; 二、运行结果&#xff1b; 三、源代码&#xff1b; # define _CRT_SECURE_NO_WARNINGS # include <stdio.h> # include <math.h>int main() {//初始化变量值&#xff1b;int symbol 1;double denominator 1.0, sum 0, term 1.0;//循…
阅读更多...
Excel文件解析(Java)

Excel文件解析(Java)

一、概述 在应用程序的开发过程中&#xff0c;经常需要使用 Excel文件来进行数据的导入或导出。所以&#xff0c;在通过Java语言实现此类需求的时候&#xff0c;往往会面临着Excel文件的解析(导入&#xff09;或生成&#xff08;导出)。 在Java技术生态圈中&#xff0c…
阅读更多...
JVM运行时内存溢出以及解决办法

JVM运行时内存溢出以及解决办法

JVM有哪些运行时数据区 JVM运行时数据区有程序计数器、本地方法栈虚拟机栈、堆、元数据区、直接内存。 其中只有程序计数器不是内存溢出&#xff0c;其他的都有可能会产生内存溢出。 栈内存溢出 当方法的调用深度过深&#xff0c;可能会导致栈内存溢出。 一般是发生在递归调…
阅读更多...
Elasticsearch：如何将 MongoDB 数据引入 Elastic Cloud

Elasticsearch：如何将 MongoDB 数据引入 Elastic Cloud

作者&#xff1a;Hemendra Singh Lodhi Elastic Cloud 是由 Elastic 提供的基于云的托管服务。Elastic Cloud 允许客户在亚马逊网络服务 (AWS)、谷歌云平台 (GCP) 和微软 Azure 上部署、管理和扩展他们的 Elasticsearch 集群。 MongoDB 是一种流行的 NoSQL 文档导向数据库&am…
阅读更多...
IDEA最好用插件推荐

IDEA最好用插件推荐

1 背景 俗话说&#xff1a;“工欲善其事必先利其器”&#xff0c;本问介绍几款强大实用的 IDEA 插件&#xff0c;助力大家开发。 希望大家做一个聪明又努力的人&#xff0c;而不只是一个努力的人。 以下插件大都可以通过 IDEA 自带的插件管理中心安装&#xff0c;如果搜不到可以…
阅读更多...
算法|最大堆、最小堆和堆排序的实现（JavaScript）

算法|最大堆、最小堆和堆排序的实现（JavaScript）

一些概念 堆&#xff1a;特殊的完全二叉树&#xff0c;具有特定性质的完全二叉树。大根堆&#xff1a;父节点 > 子节点小根堆&#xff1a;父节点 < 子节点 二叉堆也属于完全二叉树&#xff0c;所以可以用数组表示。 若下标从1开始&#xff0c;左节点为 2*i &#xff0…
阅读更多...
类和对象-封装-设计案例1-立方体类

类和对象-封装-设计案例1-立方体类

#include<bits/stdc.h> using namespace std; class Cube{public://设置长void setL(int l){m_Ll;} //获取长int getL(){return m_L;}//设置宽 void setW(int w){m_Ww;}//获取宽 int getW(){return m_W;}//设置高 void setH(int h){m_Hh;}//获取高int getH(){return m_H;…
阅读更多...
【机器学习300问】72、神经网络的隐藏层数量和各层神经元节点数如何影响模型的表现？

【机器学习300问】72、神经网络的隐藏层数量和各层神经元节点数如何影响模型的表现？

评估深度学习的模型的性能依旧可以用偏差和方差来衡量。它们反映了模型在预测过程中与理想情况的偏离程度&#xff0c;以及模型对数据扰动的敏感性。我们简单回顾一下什么是模型的偏差和方差&#xff1f; 一、深度学习模型的偏差和方差 偏差&#xff1a;衡量模型预测结果的期望…
阅读更多...
JAVAEE—UDP协议TCP协议/三次握手四次挥手

JAVAEE—UDP协议TCP协议/三次握手四次挥手

文章目录 UDP协议UDP协议的段格式UDP的传输过程校验和无连接 TCP协议TCP报文的格式段有连接可靠性确认应答超时重传如果ACK丢了呢&#xff1f; 序号和确认序号 连接的构建和断开连接的构建&#xff08;三次握手&#xff09;三次握手的作用为什么握手是三次&#xff0c;而不是四…
阅读更多...
微信小程序的常用API ①

微信小程序的常用API ①

前言&#xff1a;什么是微信小程序的API&#xff1f; &#xff08;1&#xff09;微信小程序的API是由宿主环境提供的。通俗来说API是一种接口函数&#xff0c;把函数封装起来给开发者使用&#xff0c;这样好多功能都无需开发者去实现&#xff0c;直接调用即可。 &#xff08;…
阅读更多...
工业电脑在ESOP工作站行业应用

工业电脑在ESOP工作站行业应用

ESOP工作站行业应用 项目背景 E-SOP是实现作业指导书电子化&#xff0c;并统一管理和集中控制的一套管理信息平台。信迈科技的ESOP终端是一款体积小巧功能齐全的高性价比工业电脑&#xff0c;上层通过网络与MES系统连接&#xff0c;下层连接显示器展示作业指导书。ESOP控制终…
阅读更多...
Covalent Network（CQT）宣布推出面向 Cronos 生态的捐赠计划与 API 积分，为 Web3 创新赋能

Covalent Network（CQT）宣布推出面向 Cronos 生态的捐赠计划与 API 积分，为 Web3 创新赋能

为了促进 Web3 领域的创新&#xff0c;Covalent Network&#xff08;CQT&#xff09;宣布将其捐赠计划向 Cronos 生态系统中的开发者拓展。这一战略性举措&#xff0c;旨在通过向 Cronos 网络中基于 Covalent Network&#xff08;CQT&#xff09;API 构建的项目提供支持和资源&…
阅读更多...
OpenHarmony实战开发-如何使用Navigation实现多设备适配。

OpenHarmony实战开发-如何使用Navigation实现多设备适配。

介绍 在应用开发时&#xff0c;一个应用需要适配多终端的设备&#xff0c;使用Navigation的mode属性来实现一套代码&#xff0c;多终端适配。 效果图预览 使用说明 将程序运行在折叠屏手机或者平板上观看适配效果。 实现思路 本例涉及的关键特性和实现方案如下&#xff1a…
阅读更多...
高版本Android studio 使用Markdown无法预览（已解决）

高版本Android studio 使用Markdown无法预览（已解决）

目录 概述 解决方法 概述 本人升级Android studio 当前版本为Android Studio Jellyfish | 2023.3.1 RC 2导致Markdown无法预览。 我尝试了很多网上的方法都无法Markdown解决预览问题&#xff0c;包括升级插件、安装各种和Markdown相关的插件及使用“Choose Boot Java Runtim…
阅读更多...
Linux 操作系统编译器、静态库、动态库

Linux 操作系统编译器、静态库、动态库

1、编辑器 1.1、vim的安装 指令&#xff1a;sudo apt-get install vim 1.2 vim的使用 格式&#xff1a;vim 文件名 如果文件存在&#xff0c;只打开&#xff0c;文件不存在&#xff0c;创建并打开 vim的4中模式&#xff1a; 命令模式&#xff0c;插入模式&#xff0c;地行模…
阅读更多...
springboot Logback 不同环境，配置不同的日志输出路径

springboot Logback 不同环境，配置不同的日志输出路径

1.背景&#xff1a; mac 笔记本开发&#xff0c;日志文件写到/data/logs/下&#xff0c;控制台报出&#xff1a;Failed to create parent directories for [/data/logs/........... 再去手动在命令窗口创建文件夹data&#xff0c;报Read-only file system 2.修改logback-spri…
阅读更多...
Hbase的shell命令（详细）

Hbase的shell命令（详细）

一、help 1.help 显示命名的分组情况 2.help 命令名称 查看命令的具体使用&#xff0c;包括命令的作用和用法。 举例&#xff1a;help list 二、general 组&#xff08;普通命令组&#xff09; 命令 描述 …
阅读更多...
Redux极客园项目初始化搭建

Redux极客园项目初始化搭建

基本结构搭建 实现步骤 在 Login/index.js 中创建登录页面基本结构在 Login 目录中创建 index.scss 文件&#xff0c;指定组件样式将 logo.png 和 login.png 拷贝到 assets 目录中 代码实现 pages/Login/index.js import ./index.scss import { Card, Form, Input, Button }…
阅读更多...
【第十二届“泰迪杯”数据挖掘挑战赛】【2024泰迪杯】B题基于多模态特征融合的图像文本检索—更新（正式比赛）

【第十二届“泰迪杯”数据挖掘挑战赛】【2024泰迪杯】B题基于多模态特征融合的图像文本检索—更新（正式比赛）

【第十二届“泰迪杯”数据挖掘挑战赛】【2024泰迪杯】B题基于多模态特征融合的图像文本检索—更新&#xff08;正式比赛&#xff09; 往期链接&#xff1a; 【第十二届“泰迪杯”数据挖掘挑战赛】【2024泰迪杯】B题基于多模态特征融合的图像文本检索—解题全流程&#xff08;…
阅读更多...
最新文章

Copyright @ 2022~2023