LeetCode 232.用栈实现队列（详解） (๑•̌.•๑)

题目描述：

解题思路： 

创建两个栈，一个用于入数据，一个用于出数据。分别是pushST和popST;

1.如果是入数据就直接入进pushST

2.如果是出数据，先检查popST中有无数据，如果有数据，就直接出。如果没数据，就将pushST中的数据放进popST中，再从popST中出数据。

当pushST中的数据入到popST时，数据是顺序的，刚好满足队列的条件，直接出

用c语言实现栈，没法直接引用，这里需要自己创建一个栈，在完成上述操作。如果还不会栈的小伙伴可以看看我的这篇博客 【数据结构】栈【详解】૮₍ ˃ ⤙ ˂ ₎ა-CSDN博客 

栈的实现：

//栈的声明与定义
typedef int STDataType;//定义栈中的数据类型
struct Stack
{
	STDataType* a;//用于指向后续开辟的空间
	int top;       // 栈顶
	int capacity;  // 容量，方便增容
};

//typedef struct Stack ST;
typedef struct Stack Stack;
//初始化栈
void StackInit(Stack* pst);
//摧毁栈
void StackDestroy(Stack* pst);
//入栈
void StackPush(Stack* pst, STDataType x);
//出栈
void StackPop(Stack* pst);
//返回栈顶元素
STDataType StackTop(Stack* pst);

// 空返回1 非空返回0
//int StackEmpty(Stack* pst);
//栈的判空操作
bool StackEmpty(Stack* pst);
//返回栈的大小
int StackSize(Stack* pst);

void StackInit(Stack* pst)
{
	assert(pst);

	//pst->a = NULL;
	//pst->top = 0;
	//pst->capacity = 0;

	pst->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	pst->top = 0;
	pst->capacity = 4;
}

void StackDestroy(Stack* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->capacity = pst->top = 0;
}

// 性质就决定在栈顶出入数据
void StackPush(Stack* pst, STDataType x)
{
	assert(pst);
	if (pst->top == pst->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType)*pst->capacity * 2);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1); // 结束整个程序
		}

		pst->a = tmp;
		pst->capacity *= 2;
	}

	pst->a[pst->top] = x;
	pst->top++;
}

void StackPop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));
	pst->top--;
}

STDataType StackTop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));

	return pst->a[pst->top - 1];
}

// 空返回1 非空返回0
//int StackEmpty(Stack* pst);
bool StackEmpty(Stack* pst)
{
	assert(pst);

	return pst->top == 0;
}

int StackSize(Stack* pst)
{
	assert(pst);

	return pst->top;
}

队列的实现（需要用到前面的栈）： 

//用栈定义队列，其中包含两个栈，用于入数据和出数据
typedef struct {
	Stack pushST;
	Stack popST;
} MyQueue;

/** Initialize your data structure here. */
//队列的初始化
MyQueue* myQueueCreate() {
	MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
	StackInit(&q->pushST);
	StackInit(&q->popST);

	return q;
}

/** Push element x to the back of queue. */
//入队列
void myQueuePush(MyQueue* obj, int x) {
	StackPush(&obj->pushST, x);
}

/** Removes the element from in front of queue and returns that element. */
//出队列
int myQueuePop(MyQueue* obj) {
	/*if(StackEmpty(&obj->popST))
	{
	while(!StackEmpty(&obj->pushST))
	{
	StackPush(&obj->popST, StackTop(&obj->pushST));
	StackPop(&obj->pushST);
	}
	}
	*/
	int top = myQueuePeek(obj);
	StackPop(&obj->popST);
	return top;
}

/** Get the front element. */
//判断栈内数据的情况，并返回栈顶元素
int myQueuePeek(MyQueue* obj) {
	if (StackEmpty(&obj->popST))
	{
		while (!StackEmpty(&obj->pushST))
		{
			StackPush(&obj->popST, StackTop(&obj->pushST));
			StackPop(&obj->pushST);
		}
	}

	return StackTop(&obj->popST);
}

/** Returns whether the queue is empty. */
//队列的判空
bool myQueueEmpty(MyQueue* obj) {
	return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}
//摧毁队列
void myQueueFree(MyQueue* obj) {
	StackDestroy(&obj->pushST);
	StackDestroy(&obj->popST);
	free(obj);
}

 完整代码：

//栈的声明与定义
typedef int STDataType;//定义栈中的数据类型
struct Stack
{
	STDataType* a;//用于指向后续开辟的空间
	int top;       // 栈顶
	int capacity;  // 容量，方便增容
};

//typedef struct Stack ST;
typedef struct Stack Stack;
//初始化栈
void StackInit(Stack* pst);
//摧毁栈
void StackDestroy(Stack* pst);
//入栈
void StackPush(Stack* pst, STDataType x);
//出栈
void StackPop(Stack* pst);
//返回栈顶元素
STDataType StackTop(Stack* pst);

// 空返回1 非空返回0
//int StackEmpty(Stack* pst);
//栈的判空操作
bool StackEmpty(Stack* pst);
//返回栈的大小
int StackSize(Stack* pst);

void StackInit(Stack* pst)
{
	assert(pst);

	//pst->a = NULL;
	//pst->top = 0;
	//pst->capacity = 0;

	pst->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	pst->top = 0;
	pst->capacity = 4;
}

void StackDestroy(Stack* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->capacity = pst->top = 0;
}

// 性质就决定在栈顶出入数据
void StackPush(Stack* pst, STDataType x)
{
	assert(pst);
	if (pst->top == pst->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType)*pst->capacity * 2);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1); // 结束整个程序
		}

		pst->a = tmp;
		pst->capacity *= 2;
	}

	pst->a[pst->top] = x;
	pst->top++;
}

void StackPop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));
	pst->top--;
}

STDataType StackTop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));

	return pst->a[pst->top - 1];
}

// 空返回1 非空返回0
//int StackEmpty(Stack* pst);
bool StackEmpty(Stack* pst)
{
	assert(pst);

	return pst->top == 0;
}

int StackSize(Stack* pst)
{
	assert(pst);

	return pst->top;
}
//用栈定义队列，其中包含两个栈，用于入数据和出数据
typedef struct {
	Stack pushST;
	Stack popST;
} MyQueue;

/** Initialize your data structure here. */
//队列的初始化
MyQueue* myQueueCreate() {
	MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
	StackInit(&q->pushST);
	StackInit(&q->popST);
	return q;
}

/** Push element x to the back of queue. */
//入队列
void myQueuePush(MyQueue* obj, int x) {
	StackPush(&obj->pushST, x);
}

/** Removes the element from in front of queue and returns that element. */
//出队列
int myQueuePop(MyQueue* obj) {
	/*if(StackEmpty(&obj->popST))
	{
	while(!StackEmpty(&obj->pushST))
	{
	StackPush(&obj->popST, StackTop(&obj->pushST));
	StackPop(&obj->pushST);
	}
	}
	*/
	int top = myQueuePeek(obj);
	StackPop(&obj->popST);
	return top;
}

/** Get the front element. */
//判断栈内数据的情况，并返回栈顶元素
int myQueuePeek(MyQueue* obj) {
	if (StackEmpty(&obj->popST))
	{
		while (!StackEmpty(&obj->pushST))
		{
			StackPush(&obj->popST, StackTop(&obj->pushST));
			StackPop(&obj->pushST);
		}
	}

	return StackTop(&obj->popST);
}

/** Returns whether the queue is empty. */
//队列的判空
bool myQueueEmpty(MyQueue* obj) {
	return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}
//摧毁队列
void myQueueFree(MyQueue* obj) {
	StackDestroy(&obj->pushST);
	StackDestroy(&obj->popST);
	free(obj);
}

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

 

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

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

相关文章

Xcode15 升级问题记录

Xcode15 升级问题记录

这里写自定义目录标题 新版本Xcode15升级问题1：rsync error: some files could not be transferred (code 23) at ...参考 新版本Xcode15升级 下载地址：https://developer.apple.com/download/all/ 我目前使用的版本是Xcode15.2 我新创建了一个项目&…
阅读更多...
建立四叉树[中等]

建立四叉树[中等]

一、题目 给你一个n * n矩阵grid，矩阵由若干0和1组成。请你用四叉树表示该矩阵grid。你需要返回能表示矩阵grid的四叉树的根结点。四叉树数据结构中，每个内部节点只有四个子节点。此外，每个节点都有两个属性： 【1】val&#xff1…
阅读更多...
使用SpringCache操作Redis缓存数据

使用SpringCache操作Redis缓存数据

SpringCache概念 SpringCache是一个框架，实现了基于注解的缓存功能，只需要简单的加一个注解，就能实现缓存功能。 SpringCache提供了一层抽象，底层可以切换不同的缓存实现，例如： EHCacheCaffeineRedis 使…
阅读更多...
怎么在unity3D工程中导入Newtonsoft.Json

怎么在unity3D工程中导入Newtonsoft.Json

打开 Unity 编辑器。 转到菜单栏的 “Window”（窗口）选项，然后选择 “Package Manager”（包管理器） 在搜索框中输入 “Newtonsoft Json” 进行搜索。 注意：要选择Unity Registry 在搜索结果中&#xf…
阅读更多...
强化学习求解TSP（五）：Qlearning求解旅行商问题TSP（提供Python代码）

强化学习求解TSP（五）：Qlearning求解旅行商问题TSP（提供Python代码）

一、Qlearning简介 Q-learning是一种强化学习算法，用于解决基于奖励的决策问题。它是一种无模型的学习方法，通过与环境的交互来学习最优策略。Q-learning的核心思想是通过学习一个Q值函数来指导决策，该函数表示在给定状态下采取某个动作所获…
阅读更多...
Windows下安装mariadb10.5数据库及配置详细教程

Windows下安装mariadb10.5数据库及配置详细教程

1、简介 MariaDB数据库管理系统是一款MySQL的替代数据库。MariaDB由MySQL的创始人麦克尔维德纽斯主导开发，是可扩展的，可靠的SQL服务器的合乎逻辑的选择，MariaDB 10.5 是 MariaDB 当前的稳定系列。 2、下载 下载地址：Download M…
阅读更多...
【FPGA/verilog -入门学习17】vivado 实现串口自发自收程序

【FPGA/verilog -入门学习17】vivado 实现串口自发自收程序

1，需求 PC使用串口助手给FPGA板发送9600 波特率的数据，FPGA板接收到数据后，回复同样的数据给PC 2，需求分析 按模块可以划分为： rx接收模块，将输入的8位并行rx 数据转换成[7:0]rx_data 信号，当…
阅读更多...
圣诞老人遇见 GenAI：利用大语言模型、LangChain 和 Elasticsearch 破译手写的圣诞信件

圣诞老人遇见 GenAI：利用大语言模型、LangChain 和 Elasticsearch 破译手写的圣诞信件

在北极的中心地带，圣诞老人的精灵团队面临着巨大的后勤挑战：如何处理来自世界各地儿童的数百万封信件。 圣诞老人表情坚定，他决定是时候将人工智能纳入圣诞节行动了。 圣诞老人坐在配备了最新人工智能技术的电脑前，开始在 Jupyter…
阅读更多...
【Linux】Ubuntu 解压 zip、z01、z02等压缩文件的方法，Linux如何解压分卷压缩的

【Linux】Ubuntu 解压 zip、z01、z02等压缩文件的方法，Linux如何解压分卷压缩的

zip分卷压缩，在windows上压缩来的，如何解压这种文件： -rw-rw-r-- 1 20401094656 Dec 10 20:06 FFHQ.z01 -rw-rw-r-- 1 20401094656 Dec 10 20:10 FFHQ.z02 -rw-rw-r-- 1 20401094656 Dec 10 23:22 FFHQ.z03 -rw-rw-r-- 1 20401094656 Dec 10…
阅读更多...
docker微服务案例

docker微服务案例

文章目录 建立简单的springboot项目(boot3)boot2建立通过dockerfile发布微服务部署到docker容器编写Dockerfile打包成镜像运行镜像微服务 建立简单的springboot项目(boot3) 1.建立module 2. 改pom <?xml version"1.0" encoding"UTF-8"?> <…
阅读更多...
通过反射修改MultipartFile类文件名

通过反射修改MultipartFile类文件名

1、背景 项目上有这样一个需求&#xff0c;前端传文件过来&#xff0c;后端接收后按照特定格式对文件进行重命名。(修改文件名需求其实也可以在前端处理的) //接口类似于下面这个样子 PosMapping("/uploadFile") public R uploadFile(List<MultipartFile> fil…
阅读更多...
鸿蒙HarmonyOS学习手册_入门篇

鸿蒙HarmonyOS学习手册_入门篇

鸿蒙HarmonyOS学习手册_入门篇 文章目录 鸿蒙HarmonyOS学习手册_入门篇入门快速入门开发准备基本概念UI框架应用模型工具准备 构建第一个ArkTS应用&#xff08;Stage模型&#xff09;-快速入门-入门创建ArkTS工程ArkTS工程目录结构&#xff08;Stage模型&#xff09;构建第一个…
阅读更多...
day14 二叉树的遍历 递归遍历 迭代遍历 统一遍历

day14 二叉树的遍历 递归遍历 迭代遍历 统一遍历

题目1&#xff1a;递归遍历 题目链接1&#xff1a;144 二叉树的前序遍历 题意 根据二叉树的根节点root&#xff0c;返回它的前序遍历 递归法 前序遍历&#xff1a;中左右 递归三部曲 1) 确定递归函数的参数和返回值 2&#xff09;确定终止条件 3&#xff09;确定单层递…
阅读更多...
linux搭建SRS服务器

linux搭建SRS服务器

linux搭建SRS服务器 文章目录 linux搭建SRS服务器SRS说明实验说明搭建步骤推流步骤查看web端服务器拉流步骤final SRS说明 SRS&#xff08;simple Rtmp Server&#xff09;,是一个简单高效的实时视频服务器&#xff0c;支持RTMP/WebRTC/HLS/HTTP-FLV/SRT, 是国人自己开发的一款…
阅读更多...
计算机基础面试题 |22.精选计算机基础面试题

计算机基础面试题 |22.精选计算机基础面试题

&#x1f90d; 前端开发工程师&#xff08;主业&#xff09;、技术博主&#xff08;副业&#xff09;、已过CET6 &#x1f368; 阿珊和她的猫_CSDN个人主页 &#x1f560; 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 &#x1f35a; 蓝桥云课签约作者、已在蓝桥云…
阅读更多...
坑记（HttpInputMessage）

坑记（HttpInputMessage）

一、背景知识 public interface HttpInputMessage extends HttpMessage Represents an HTTP input message, consisting of headers and a readable body.Typically implemented by an HTTP request on the server-side, or a response on the client-side.Since: 3.0 Author:…
阅读更多...
windows安装Elasticsearch后使用ik分词器报错解决办法

windows安装Elasticsearch后使用ik分词器报错解决办法

最近在学习Elasticsearch&#xff0c;安装完成后下载了ik分词器压缩到plugins目录下启动es报错如下&#xff1a; java.security.AccessControlException: access denied (“java.io.FilePermission” “D:…\plugins\ik-analyzer\config\IKAnalyzer.cfg.xml” “read”)咋一看…
阅读更多...
03 - 系统调用

03 - 系统调用

---- 整理自 王利涛老师 课程 实验环境&#xff1a;宅学部落 www.zhaixue.cc 文章目录 1. 系统调用基本概念1.1 一个系统调用的例子1.2 什么是系统调用&#xff1f;软件复用的角度 2. 软中断&#xff1a;系统调用的入口2.1 权限管理2.2 系统调用号2.4 man 2 syscall2.5 实验&am…
阅读更多...
全自动网页生成系统网站源码重构版

全自动网页生成系统网站源码重构版

源码优点: 所有模板经过精心审核与修改&#xff0c;完美兼容小屏手机大屏手机&#xff0c;以及各种平板端、电脑端和360浏览器、谷歌浏览器、火狐浏览器等等各大浏览器显示。 免费制作 为用户使用方便考虑&#xff0c;全自动网页制作系统无需繁琐的注册与登入&#xff0c;直…
阅读更多...
MongoDB 设置账号密码_mongodb设置用户名和密码

MongoDB 设置账号密码_mongodb设置用户名和密码

MongoDB 设置账号密码_mongodb设置用户名和密码 1、安装 安装可以看我这篇文章：https://blog.csdn.net/u014641168/article/details/123937775 2、说明 由于默认安装的MongoDB是没有设置用户密码的，极其危险，所以需要设置一下用户密码 3、创建用户 用Navicat15连接Mon…
阅读更多...
最新文章

Copyright @ 2022~2023