LeetCode 225.用队列实现栈（详解） ૮꒰ ˶• ༝ •˶꒱ა

题目详情：

思路：1.定义两个队列用于存储栈的数据，其中一个为空。

          2.对我们定义的栈进行入数据，就相当于对不为空的队列进行入数据。

          3.对我们定义的栈进行删除，相当于取出不为空的队列中的数据放到为空的队列中，直到此时只剩下一个数据；对剩下的数据进行取出后删除。也就相当于对当前的栈进行删除。（对于栈的顶删相当于对队列的尾删）

        3.返回栈的顶部元素

        4.销毁栈

 注意：用c语言实现队列，没法直接引用，这里需要自己创建一个队列，再完成上述操作。如果还不会队列的小伙伴可以看看我的这篇博客数据结构--队列【详解】~(˶‾᷄ꈊ‾᷅˵)~-CSDN博客

 

 队列的实现：

typedef int QDataType;
typedef struct QueueNode
{//队列的定义与声明
	struct QueueNode* next;
	QDataType data;
}QNode;
//创建一个结构体用于存储队列头尾指针
typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;
//初始化队列
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}
//摧毁队列
void QueueDestory(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{//存储下一个节点的指针，防止找不到和野指针的出现
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

// 队尾入
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);//为队列开辟一个新节点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
//若第一个节点为空，则head和tail指向第一个节点
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}//如果不是空，就让尾指针指向新节点，并移动尾指针方便下一次插入
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

// 队头出
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	// 1、一个，直接释放第一个节点的内存
	// 2、多个，要记得保存第一个节点的下一个节点的位置，防止找不到
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

//返回队头节点的数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->head->data;
}
//返回队尾节点的数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->tail->data;
}
//返回队列的大小
int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;//这里用cur记录节点的个数
	QNode* cur = pq->head;
	while (cur)
	{
		++size;
		cur = cur->next;
	}
	return size;
}
//判断节点是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

 

 用队列实现栈的函数实现：

//定义一个结构体用于存放两个队列
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;
//用队列创造栈
MyStack* myStackCreate() {//用ps开辟空间，作为栈存储数据
    MyStack* ps=(MyStack*)malloc(sizeof(MyStack));
    if(ps==NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    QueueInit(&ps->q1);
    QueueInit(&ps->q2);
    return ps;
}
//用队列入栈
void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))//选择不为空的那个队列入
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}
//用队列进行出栈操作
int myStackPop(MyStack* obj) {
    Queue* emptyQ=&obj->q1;//将不为空的队列的数据转移到为空的队列，直到只剩一个
    Queue* nonemptyQ=&obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        emptyQ=&obj->q2;
        nonemptyQ=&obj->q1;
    }
    while(QueueSize(nonemptyQ)>1)
    {
        QueuePush(emptyQ,QueueFront(nonemptyQ));
        QueuePop(nonemptyQ);
    }
    int top=QueueFront(nonemptyQ);
    QueuePop(nonemptyQ);
    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) {
    QueueDestory(&obj->q1);
    QueueDestory(&obj->q2);
    free(obj);
}

 注意：摧毁栈时要先摧毁obj下所对应的队列，再进行free(obj)。如果先free(obj),就无法找到对应的队列了

完整代码： 

typedef int QDataType;
typedef struct QueueNode
{//队列的定义与声明
	struct QueueNode* next;
	QDataType data;
}QNode;
//创建一个结构体用于存储队列头尾指针
typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;
//初始化队列
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}
//摧毁队列
void QueueDestory(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{//存储下一个节点的指针，防止找不到和野指针的出现
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

// 队尾入
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);//为队列开辟一个新节点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
//若第一个节点为空，则head和tail指向第一个节点
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}//如果不是空，就让尾指针指向新节点，并移动尾指针方便下一次插入
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

// 队头出
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	// 1、一个，直接释放第一个节点的内存
	// 2、多个，要记得保存第一个节点的下一个节点的位置，防止找不到
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

//返回队头节点的数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->head->data;
}
//返回队尾节点的数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->tail->data;
}
//返回队列的大小
int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;//这里用cur记录节点的个数
	QNode* cur = pq->head;
	while (cur)
	{
		++size;
		cur = cur->next;
	}
	return size;
}
//判断节点是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}
//定义一个结构体用于存放两个队列
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;
//用队列创造栈
MyStack* myStackCreate() {//用ps开辟空间，作为栈存储数据
    MyStack* ps=(MyStack*)malloc(sizeof(MyStack));
    if(ps==NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    QueueInit(&ps->q1);
    QueueInit(&ps->q2);
    return ps;
}
//用队列入栈
void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))//选择不为空的那个队列入
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}
//用队列进行出栈操作
int myStackPop(MyStack* obj) {
    Queue* emptyQ=&obj->q1;//将不为空的队列的数据转移到为空的队列，直到只剩一个
    Queue* nonemptyQ=&obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        emptyQ=&obj->q2;
        nonemptyQ=&obj->q1;
    }
    while(QueueSize(nonemptyQ)>1)
    {
        QueuePush(emptyQ,QueueFront(nonemptyQ));
        QueuePop(nonemptyQ);
    }
    int top=QueueFront(nonemptyQ);
    QueuePop(nonemptyQ);
    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) {
    QueueDestory(&obj->q1);
    QueueDestory(&obj->q2);
    free(obj);
}

博客到这里也是结束了，喜欢的小伙伴可以点赞加关注支持下博主，这对我真的很重要~~

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

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

相关文章

【低照度图像增强系列（3）】EnlightenGAN算法详解与代码实现

【低照度图像增强系列（3）】EnlightenGAN算法详解与代码实现

前言 ☀️ 在低照度场景下进行目标检测任务，常存在图像RGB特征信息少、提取特征困难、目标识别和定位精度低等问题，给检测带来一定的难度。 🌻使用图像增强模块对原始图像进行画质提升，恢复各类图像信息，再使用目标检…
阅读更多...
约数个数和约数之和算法总结

约数个数和约数之和算法总结

知识概览 约数个数 基于算数基本定理，假设N分解质因数的结果为 可得对于N的任何一个约数d，有 因为N的每一个约数和~的一种选法是一一对应的，根据乘法原理可得， 一个数的约数个数为 约数之和 一个数的约数之和公式为 多项式乘积的…
阅读更多...
汽车IVI中控开发入门及进阶（十二）：手机投屏

汽车IVI中控开发入门及进阶（十二）：手机投屏

前言： 汽车座舱有车载中控大屏、仪表/HUD多屏的显示能力，有麦克风/喇叭等车载环境更好的音频输入输出能力，有方控按键、旋钮等方便的反向控制输入能力，还有高精度的车辆数据等。但汽车座舱中控主机硬件计算能力升级迭代周期相对较长，汽车的应用和服务不够丰富。现在很多汽…
阅读更多...
持续集成Jmeter+Jenkins+Ant

持续集成Jmeter+Jenkins+Ant

在开始这篇文章之前，我要先为大家解答2个疑惑： 第一点，我们为什么要在项目中进行接口自动化测试？好处是什么？ 相对于UI层面，接口的测试的收益是巨大的，能在最短的时间发现重要的问题。接口在迭…
阅读更多...
【Vue】文件管理页面制作

【Vue】文件管理页面制作

<template><div><div style"margin: 10px 0"><el-input style"width: 200px" placeholder"请输入名称" suffix-icon"el-icon-search" v-model"name"></el-input><el-button class"ml…
阅读更多...
VBA_NZ系列工具NZ11:VBA光标跟随策略

VBA_NZ系列工具NZ11:VBA光标跟随策略

我的教程一共九套及VBA汉英手册一部&#xff0c;分为初级、中级、高级三大部分。是对VBA的系统讲解&#xff0c;从简单的入门&#xff0c;到数据库&#xff0c;到字典&#xff0c;到高级的网抓及类的应用。大家在学习的过程中可能会存在困惑&#xff0c;这么多知识点该如何组织…
阅读更多...
python_数据可视化_pandas_导入CSV数据

python_数据可视化_pandas_导入CSV数据

目录 1.导入库 2.导入CSV文件 3.指定分隔符 4.指定读取行数 4.指定读取列数 5.读取文件或文件的路径中有中文 1.导入库 import pandas as pd 2.导入CSV文件 导入时要指定编码格式 data pd.read_csv(D:/desktop/TestCSV.csv,encodinggbk)print(data) 3.指定分隔符 默认…
阅读更多...
Mybatis——多表查询

Mybatis——多表查询

目录 一、简介 二、业务环境的准备 2.1、准备工作&#xff1a; 2.2、SQL 三、一对一和一对多 Sql语句&#xff1a; POJO OrderMapper OrderMapper.xml Test测试类 运行结果 一、简介 MyBatis 是一个优秀的持久层框架&#xff0c;它提供了强大的支持来执行数据库操作&am…
阅读更多...
概述：利用大模型 (LLMs) 解决信息抽取任务

概述：利用大模型 (LLMs) 解决信息抽取任务

论文标题&#xff1a;Large Language Models for Generative Information Extraction: A Survey 论文链接&#xff1a;https://arxiv.org/pdf/2312.17617.pdf 论文主要探讨了大型语言模型&#xff08;LLMs&#xff09;在生成式信息抽取&#xff08;IE&#xff09;任务中的应用…
阅读更多...
Scala入门到放弃—04—集合

Scala入门到放弃—04—集合

文章目录 集合数组ListSetMapTuple其他 集合 数组 可变数组 package org.example object ArrayApp extends App{//继承App后直接直接调用函数&#xff0c;不需要main//println("hello")val a new Array[String](5)a(0)"hello"println(a(0))val b Array…
阅读更多...
Linux C/C++ 显示NIC流量统计信息

Linux C/C++ 显示NIC流量统计信息

NIC流量统计信息是由操作系统维护的。当数据包通过NIC传输时&#xff0c;操作系统会更新相关的计数器。这些计数器记录了数据包的发送和接收数量、字节数等。通过读取这些计数器&#xff0c;我们可以获得关于网络流量的信息。 为什么需要这些信息? 可以使用这些信息来监控网络…
阅读更多...
怎么投稿各大媒体网站？

怎么投稿各大媒体网站？

怎么投稿各大媒体网站&#xff1f;这是很多写作者及自媒体从业者经常面临的问题。在信息爆炸的时代&#xff0c;如何将自己的文章推送到广大读者面前&#xff0c;成为了一个不可避免的挑战。本文将为大家介绍一种简单有效的投稿方法——媒介库发稿平台发稿&#xff0c;帮助大家…
阅读更多...
不知道题目是啥

不知道题目是啥

本题是学校的集训里的题&#xff0c;所有不知道题目名字是啥&#xff0c;直接看题目就好 解题思路&#xff1a;因为字符串只含有小写字母&#xff0c;所以可以创建两个数组分别来存s和t的每个字母出现次数&#xff0c;然后遍历数组&#xff0c;如果s字符串中的某个字母比t的小&…
阅读更多...
Python GIL 一文全知道！

Python GIL 一文全知道！

GIL 作为 Python 开发者心中永远的痛&#xff0c;在最近即将到来的更新中&#xff0c;终于要彻底解决了&#xff0c;整个 Python 社群都沸腾了 什么是GIL&#xff1f; GIL是英文学名global interpreter lock的缩写&#xff0c;中文翻译成全局解释器锁。GIL需要解决的是线程竞…
阅读更多...
云卷云舒：kubernetes简介

云卷云舒：kubernetes简介

Kubernetes是由google公司在2014年发布的一款开源的容器编排引擎&#xff0c;用于容器化应用程序的自动化部署、扩展与管理。它能够编排多种容器任务&#xff0c;涵盖虚拟机集群管理、负载均衡以及网络流量分配等等。2017年&#xff0c;aws、微软云、阿里云等等著名的云计算公司…
阅读更多...
文献阅读1

文献阅读1

A Hierarchical Representation Network for Accurate and Detailed Face Reconstruction from In-The-Wild Images 会议/期刊&#xff1a;CVPR 2023&#xff1b;阿里达摩院&#xff1b;Biwen Lei 概述&#xff1a;这是一篇单张图片三维人脸重建的论文&#xff0c;这篇论文的…
阅读更多...
26、web攻防——通用漏洞SQL注入SqlmapOracleMongodbDB2

26、web攻防——通用漏洞SQL注入SqlmapOracleMongodbDB2

文章目录 OracleMongoDBsqlmap SQL注入课程体系&#xff1b; 数据库注入&#xff1a;access、mysql、mssql、oracle、mongodb、postgresql等数据类型注入&#xff1a;数字型、字符型、搜索型、加密型&#xff08;base63 json&#xff09;等提交方式注入&#xff1a;get、post、…
阅读更多...
ChatGPT提示词大赏：GPT Prompts Hub 2024年最新ChatGPT提示词项目

ChatGPT提示词大赏：GPT Prompts Hub 2024年最新ChatGPT提示词项目

&#x1f31f; GPT Prompts Hub &#x1f31f; English | 简体中文 Security Prompts | GPTS Prompts 欢迎来到 “GPT Prompts Hub” 存储库&#xff01;&#x1f31f; 探索并分享高质量的 ChatGPT 提示词。培养创新性内容&#xff0c;提升对话体验&#xff0c;激发创造力。…
阅读更多...
创建型模式 | 建造者模式

创建型模式 | 建造者模式

一、建造者模式 1、原理 建造者模式又叫生成器模式&#xff0c;是一种对象的构建模式。它可以将复杂对象的建造过程抽象出来&#xff0c;使这个抽象过程的不同实现方法可以构造出不同表现&#xff08;属性&#xff09;的对象。创建者模式是一步一步创建一个复杂的对象&#xf…
阅读更多...
在App Store Connect上编辑多个用户的访问权限

在App Store Connect上编辑多个用户的访问权限

作为一名编程新手&#xff0c;在App Store Connect中管理用户权限可能初听起来有些复杂&#xff0c;但实际上它是一个相对直接的过程。这里是一个步骤清晰的指南来帮助您在App Store Connect上编辑多个用户的访问权限。 App Store Connect 简介 在开始之前&#xff0c;让我们先…
阅读更多...
最新文章

Copyright @ 2022~2023