【数据结构】如何用栈实现队列？图文解析（LeetCode）

LeetCode链接：232. 用栈实现队列 - 力扣（LeetCode）

注：本文默认读者已掌握栈与队列的基本操作

可以看这篇文章熟悉知识点：【数据结构】栈与队列_字节连结的博客-CSDN博客

目录

做题思路

代码实现

1. MyQueue

2. myQueueCreate

3. myQueuePush

4. myQueuePeek

5. myQueuePop

6. myQueueEmpty

7. myQueueFree

全部代码

做题思路

简单来说，就是把一个栈（栈1）的数据捯入另一个栈（栈2），此时（栈2）出数据的顺序就和队列是一样的。

为了更方便理解，我会画图来演示一下具体思路。

我们需要两个栈来实现队列：

  • push栈：专门入数据的栈
  • pop栈：专门出数据的栈

如下图：

插入数据：直接在push栈内插入即可

push栈内插入数据：1、2、3、4、5

删除数据：需要把push栈内的数据捯入pop栈

  • 栈是后入先出的
  • 当push栈的数据捯入pop栈后，数据顺序会改变

如下图：

可以看到数据顺序逆转了

但是栈的这些操作跟队列有什么联系呢？

不妨来看看pop栈与队列的对比：

由此可见：pop栈出数据的顺序是和队列一样的

到这里思路已经很清晰了：我们需要两个栈，一个专门用来push，一个专门用来pop，捯数据后，pop栈出数据的顺序就跟队列是一样的。

那么如何用代码（C）来实现这个思路呢？

代码实现

由于我们使用的是C语言，不能直接使用栈的操作

所以先把之前模拟实现过的栈复制过来：

//C语言模拟实现栈

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

//初始化栈
void STInit(ST* ps);
//销毁栈
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool STEmpty(ST* ps);

void STInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void STPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

void STPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

STDataType STTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

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

bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

复制完成之后就是本题的重点内容了。

本题要求：

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

1. MyQueue

由于我们是用两个栈实现队列

所以这里需要定义两个栈

//两个栈模拟实现队列
typedef struct
{
    ST pushst;
    ST popst;
} MyQueue;

2. myQueueCreate

这个函数要求我们开辟空间，并初始化栈

//开辟空间并初始化
MyQueue* myQueueCreate()
{
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&obj->pushst);
    STInit(&obj->popst);
    return obj;
}

3. myQueuePush

直接把数据插入到push栈即可

//将元素X推到队列的末尾
void myQueuePush(MyQueue* obj, int x)
{
    STPush(&obj->pushst, x);
}

4. myQueuePeek

本函数要求返回队列开头的元素

  • 如果pop栈为空：要把push栈的数据捯入pop栈才能找到队列的首元素
  • 如果pop栈不为空：pop栈的栈顶元素就是队列的首元素

//返回队列开头的元素
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);
}

5. myQueuePop

  • 要求删除队头元素，也就是pop栈的栈顶元素，直接删除即可
  • 并且要返回队头元素的值，需要先定义一个临时变量来保存队头元素的值
  • 最后返回这个临时变量
//从队列的开头移除并返回元素
int myQueuePop(MyQueue* obj)
{
    int front = myQueuePeek(obj);
    STPop(&obj->popst);
    return front;
}

6. myQueueEmpty

判断队列是否为空，返回一个bool值（true/false）

如果push栈和pop栈都为空，则说明队列为空

//如果队列为空，返回true；否则，返回false
bool myQueueEmpty(MyQueue* obj)
{
    return STEmpty(&obj->popst) && STEmpty(&obj->pushst);
}

7. myQueueFree

销毁队列

  • 销毁push栈和pop栈
  • 释放动态开辟的空间
//销毁队列
void myQueueFree(MyQueue* obj)
{
    STDestroy(&obj->popst);
    STDestroy(&obj->pushst);
    free(obj);
}

到这里全部函数已经实现完毕，提交代码：

成功通过

下面我会把本题的全部代码整合在一起发出来

全部代码

//C语言模拟实现栈

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

//初始化栈
void STInit(ST* ps);
//销毁栈
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool STEmpty(ST* ps);

void STInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void STPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

void STPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

STDataType STTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

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

bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

//=======================================================================

//两个栈模拟实现队列
typedef struct
{
    ST pushst;
    ST popst;
} MyQueue;

//开辟空间并初始化
MyQueue* myQueueCreate()
{
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&obj->pushst);
    STInit(&obj->popst);
    return obj;
}

//将元素X推到队列的末尾
void myQueuePush(MyQueue* obj, int x)
{
    STPush(&obj->pushst, x);
}

//返回队列开头的元素
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);
}

//从队列的开头移除并返回元素
int myQueuePop(MyQueue* obj)
{
    int front = myQueuePeek(obj);
    STPop(&obj->popst);
    return front;
}

//如果队列为空，返回true；否则，返回false
bool myQueueEmpty(MyQueue* obj)
{
    return STEmpty(&obj->popst) && STEmpty(&obj->pushst);
}

//销毁队列
void myQueueFree(MyQueue* obj)
{
    STDestroy(&obj->popst);
    STDestroy(&obj->pushst);
    free(obj);
}

本文完

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

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

相关文章

选择排序：用C语言打造高效的排序算法

选择排序：用C语言打造高效的排序算法

本篇博客会讲解如何使用C语言实现选择排序。 下面我来画图讲解选择排序的思路。 假设有一个数组，其初始状态如下，我们想把这个数组排成升序。 首先我们标明范围，即[begin, end]，一开始begin(b)和end(e)分别表示数组的第一个位置…
阅读更多...
运维Shell脚本小试牛刀(一)

运维Shell脚本小试牛刀(一)

运维Shell脚本小试牛刀(一) 运维Shell脚本小试牛刀(二) 运维Shell脚本小试牛刀(三)::$(cd $(dirname $0)； pwd)命令详解 一: Shell中循环剖析 for 循环....... #!/bin/bash - # # # # FILE: countloop.sh # …
阅读更多...
【ES】笔记-集合介绍与API

【ES】笔记-集合介绍与API

集合是一种不允许值重复的顺序数据结构。 通过集合我们可以进行并集、交集、差集等数学运算， 还会更深入的理解如何使用 ECMAScript 2015(ES2015)原生的 Set 类。 构建数据集合 集合是由一组无序且唯一(即不能重复)的项组成的。该数据结构使用了与有限集合相同的数…
阅读更多...
文件修改时间能改吗？怎么改？

文件修改时间能改吗？怎么改？

文件修改时间能改吗？怎么改？修改时间是每个电脑文件具备的一个属性，它代表了这个电脑文件最后一次的修改时间，是电脑系统自动赋予文件的，相信大家都应该知道。我们右击鼠标某个文件，然后点击弹出菜单里面的…
阅读更多...
ELK安装、部署、调试（一）设计规划及准备

ELK安装、部署、调试（一）设计规划及准备

一、整体规划如图： 【filebeat】 需要收集日志的服务器，安装filebeat软件，用于收集日志。logstash也可以收集日志，但是占用的系统资源过大，所以使用了filebeat来收集日志。 【kafka】 接收filebeat的日志&#xff…
阅读更多...
【Java笔记】分布式id生成-雪花算法

【Java笔记】分布式id生成-雪花算法

随着业务的增长，有些表可能要占用很大的物理存储空间，为了解决该问题，后期使用数据库分片技术。将一个数据库进行拆分，通过数据库中间件连接。如果数据库中该表选用ID自增策略，则可能产生重复的ID，此时应该…
阅读更多...
【硬件设计】硬件学习笔记一--元器件的介绍与选型

【硬件设计】硬件学习笔记一--元器件的介绍与选型

硬件学习笔记一--元器件的选型 一、电阻1.1 电阻的分类1.2 电阻的选型 二、电容2.1 陶瓷电容2.2 钽电容2.3 铝电解电容2.4 电容选型 三、电感3.1 定义与介绍3.2 电感的分类3.3 电感的参数 四、磁珠4.1 磁珠的介绍4.2 磁珠的参数 五、二极管5.1 定义5.2 稳压管5.3 肖特基二极管5…
阅读更多...
无涯教程-聚类算法 - K-Means

无涯教程-聚类算法 - K-Means

K-均值聚类算法计算质心并进行迭代，直到找到最佳质心为止，它假定群集的数目是已知的，它也称为扁平聚类算法。通过算法从数据中识别出的簇数以K均值中的" K"表示。 在该算法中，将数据点分配给群集，以使数据点…
阅读更多...
五、Kafka消费者

五、Kafka消费者

目录 5.1 Kafka的消费方式5.2 Kafka 消费者工作流程1、总体流程2、消费者组原理3、消费者组初始化流程4、消费者组详细消费流程 5.3 消费者API1 独立消费者案例（订阅主题）2 独立消费者案例（订阅分区）3 消费者组案例 5.4 生产经验—…
阅读更多...
Anolis 8.6 下 Redis 7.2.0 集群搭建和配置

Anolis 8.6 下 Redis 7.2.0 集群搭建和配置

Redis 7.2.0 搭建和集群配置 一.Redis 下载与单机部署1.Redis 下载2.虚拟机配置3.Redis 单机源码安装和测试4.Java 单机连接测试1.Pom 依赖2.配置文件3.启动类4.配置类5.单元测试6.测试结果 二.Redis 集群部署1.主从1.从节点配置2.Java 测试 2.哨兵1.哨兵节点配置2.复制一个哨兵…
阅读更多...
eslint

eslint

什么是eslint ESLint 是一个根据方案识别并报告 ECMAScript/JavaScript 代码问题的工具，其目的是使代码风格更加一致并避免错误。 安装eslint npm init eslint/config执行后会有很多选项，按照自己的需求去选择就好，运行成功后会生成 .esli…
阅读更多...
linux创建进程

linux创建进程

linux创建进程 准备工作 准备工作 在Ubuntu64系统上 1、安装GCC和Make工具 编译器GCC：把C源码转为二进制程序 Make：自动编译多源文件项目 sudo apt-get update #更新存储库 sudo apt-get install build-essential #安装build-essential包 gcc --versio…
阅读更多...
前端 js实现 选中数据 动态 添加在表格中

前端 js实现 选中数据 动态 添加在表格中

如下图展示，表格上方有属性内容，下拉选中后，根据选中的内容，添加在下方的表格中。 实现方式，（要和后端约定，因为这些动态添加的字段都是后端返回的，后端自己会做处理&#xff0c…
阅读更多...
〔019〕Stable Diffusion 之 单图中绘制多人分区域写提示词 篇

〔019〕Stable Diffusion 之 单图中绘制多人分区域写提示词 篇

✨ 目录 🎈 下载区域绘制插件🎈 区域绘制使用🎈 参数讲解和基础使用🎈 Lora 自组🎈 Lora 自组的使用🎈 分区扩散🎈 分区域提示 🎈 下载区域绘制插件 在绘制图片时，经常绘…
阅读更多...
【数据结构】带头双向循环链表---C语言版（单链表我们分手吧，不要再找我玩了！！！）

【数据结构】带头双向循环链表---C语言版（单链表我们分手吧，不要再找我玩了！！！）

文章目录 🐸一、前言🐸二、链表的分类🍄1. 单向或者双向链表🍄2. 带头或者不带头链表🍄3. 循环或者非循环🍄4. 最常用链表 🐸三、带头双向循环链表详解🍎创建带头双向循环链表⭕接口…
阅读更多...
只考一门数据结构，计算机学硕复录比1：1的山东双非学校考情分析

只考一门数据结构，计算机学硕复录比1：1的山东双非学校考情分析

青岛理工大学 考研难度（☆） 内容：23考情概况（拟录取和复试分析）、院校概况、23专业目录、23复试详情、各专业考情分析、各科目考情分析。 正文1420字，预计阅读：3分钟 2023考情概况 青岛理工…
阅读更多...
CI/CD 持续集成 持续交付

CI/CD 持续集成 持续交付

CI（Continuous integration）持续集成 参考：https://www.jianshu.com/p/2132949ff84a 持续集成是指多名开发者在开发不同功能代码的过程当中，可以频繁的将代码行合并到一起并切相互不影响工作。 持续集成的目的，是让…
阅读更多...
ATF(TF-A)安全通告 TFV-2 (CVE-2017-7564)

ATF(TF-A)安全通告 TFV-2 (CVE-2017-7564)

安全之安全(security)博客目录导读 ATF(TF-A)安全通告汇总 目录 一、ATF(TF-A)安全通告 TFV-2 (CVE-2017-7564) 二、 CVE-2017-7564 一、ATF(TF-A)安全通告 TFV-2 (CVE-2017-7564) Title 启用安全自托管侵入式调试接口，可允许非安全世界引发安全世界panic CV…
阅读更多...
SpringCloud学习笔记(十二)_Zipkin全链路监控

SpringCloud学习笔记(十二)_Zipkin全链路监控

Zipkin是SpringCloud官方推荐的一款分布式链路监控的组件，使用它我们可以得知每一个请求所经过的节点以及耗时等信息，并且它对代码无任何侵入，我们先来看一下Zipkin给我们提供的UI界面都是提供了哪些信息。 如何使用Zipkin 虽然在SpringBoot…
阅读更多...
C语言练习题解析：挑战与突破，开启编程新篇章！（2）

C语言练习题解析：挑战与突破，开启编程新篇章！（2）

💓博客主页：江池俊的博客⏩收录专栏：C语言刷题专栏👉专栏推荐：✅C语言初阶之路 ✅C语言进阶之路💻代码仓库：江池俊的代码仓库🎉欢迎大家点赞👍评论📝收藏⭐ 文…
阅读更多...
最新文章

Copyright @ 2022~2023