【数据结构与算法】用队列实现栈

文章目录

  • 😎前言
  • 如何用队列实现栈？
  • 用队列实现栈
  • 整体的实现代码
  • 😎写在最后

😎前言

😼前面我们相继实现了 栈 和 队列 ，是不是愁没有练手的地方呢？别担心，本章带大家用队列来实现一个栈！
😽我们都知道，栈和队列可以看作为兄弟，一个后进先出(LIFO)，一个先进先出(FIFO)，他们虽有不同的性质，但总的来说还是不分家的，因为，我们既可以用队列实现栈，也可以用栈实现队列，而本章就先来带大家来了解如何使用队列来实现栈。

如何用队列实现栈？

  • 前面废话这么多，那我们该如何用队列实现栈呢？一个队列当然不行，所以这里需要两个队列来实现。

  • 用两个队列，而每一个队列都是数据先进先出，我们仔细思考栈的后进先出这一性质，如何来操作这两个队列才能达到这样的一个性质？

  • 我们可以这样操作，一开始，两个队列都为空，所以我们随便在一个队列里进数据（就是入栈），当我们要出数据时，根据栈的性质，最后进的数据要出去，也就是在进数据的那个队列里最后进的数据要出去，但由于队列的性质只能先进的先出， 所以这里我们需要用到另外那个空的队列：我们将已有数据的队列依次出数据，并将出的数据入到那个空的队列中，当出数据的队列中只有一个数据时停止出数据，而此时最后剩下的那个数据，就是依据栈的性质所要删除的那个数据，这时，直接将那个数据出掉并不在入入另外一个队列即可。续：我们每次出栈都需要前面的操作，这是最难理解也是最核心的一个步骤。

在这里插入图片描述

  • 当然了，入栈操作又分两种情况：第一种就是前面所说开始两个队列都为空的情况；第二种就是当一个队列不为空时，我们只需要正常的往这个有数据的队列入栈即可。

  • 此外，用队列实现一个栈，还需要有判空，取栈顶元素，栈的销毁这些功能，不过这些都是小问题，我们可以巧用轮子 （轮子就是我们提前已经实现好的队列的一系列功能） 来灵活解决这些问题。

用队列实现栈

  • 这里我们直接以题目的方式来实现，题目链接：-> 传送门 <- 。

题目描述：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

该题提供的需要我们实现的接口：

typedef struct {

} MyStack;


MyStack* myStackCreate() {

}

void myStackPush(MyStack* obj, int x) {

}

int myStackPop(MyStack* obj) {

}

int myStackTop(MyStack* obj) {

}

bool myStackEmpty(MyStack* obj) {

}

void myStackFree(MyStack* obj) {

}
  • 由于这里我们用C语言实现，因此需要 “造轮子”，也就是将之前实现过的队列拷贝过去。

接下来，就是对栈的一系列功能接口的实现了：

1.

  • 首先当然是造轮子，有了轮子，我们对队列的一系列操作，只需要调用我们已经实现好的函数接口即可。

  • 我们将之前写的队列直接拷贝过来，拷贝的代码如下：

// 队列的数据的类型
typedef int QDataType;
// 节点结构	
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

// 队列结构
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Que;

// 初始化队列
void QInit(Que* pq);
// 销毁队列
void QDestroy(Que* pq);
// 数据入队列
void QPush(Que* pq, QDataType x);
// 数据出队列
void QPop(Que* pq);
// 获取队列中有效元素个数
int QSize(Que* pq);
// 队列判空
bool QEmpty(Que* pq);
// 取队头数据
QDataType QFront(Que* pq);
// 取队尾数据
QDataType QBack(Que* pq);

// 初始化队列
void QInit(Que* pq)
{
	assert(pq);

	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}

// 队列销毁
void QDestroy(Que* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}

// 数据入队列
void QPush(Que* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	assert(newnode);
	newnode->data = x;
	newnode->next = NULL;

	if (pq->size == 0) pq->head = pq->tail = newnode;
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}

	pq->size++;
}
// 数据出队列 
void QPop(Que* pq)
{
	assert(pq && !QEmpty(pq));

	if (pq->head == pq->tail)
	{
		free(pq->head);
		pq->head = NULL;
		pq->tail = NULL;
	}
	else
	{
		QNode* tmp = pq->head->next;
		free(pq->head);
		pq->head = tmp;
	}

	pq->size--;
}

// 获取队列中有效元素个数
int QSize(Que* pq)
{
	assert(pq);
	return pq->size;
}
// 队列判空
bool QEmpty(Que* pq)
{
	assert(pq);
	return pq->size == 0;
}

// 取队头数据
QDataType QFront(Que* pq)
{
	assert(pq && !QEmpty(pq));
	return pq->head->data;
}
// 取队尾数据
QDataType QBack(Que* pq)
{
	assert(pq && !QEmpty(pq));
	return pq->tail->data;
}

2.

  • 有了轮子之后，就是对栈的结构体的创建了，由于栈是由两个队列实现的，因此栈的结构体的成员也是两个队列：

相关代码实现：

// 匿名结构体
typedef struct {
    Que q1;
    Que q2;
} MyStack;   // 重命名为MyStack

3.

  • 然后是创建一个栈，就是开辟一个栈的空间，其间包含对栈里的两个队列的初始化操作。

相关代码实现：

MyStack* myStackCreate() {
	// 开辟一个栈空间
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
	assert(obj);

	// 对栈的两个成员队列调用队列的初始化函数接口初始化
	QInit(&obj->q1);
	QInit(&obj->q2);

	// 最后返回指向栈空间地址的指针
	return obj;
}

4.

  • 接着就是对入栈操作的实现。

  • 前面已经说过，如果开始两个队列都为空，随便入一个就好，后面往有数据的那个队列入即可。

相关代码实现：

void myStackPush(MyStack* obj, int x) {
	// 开始都为空，随便入，后面往不空的入
	if (!QEmpty(&obj->q1)) QPush(&obj->q1, x);
	else QPush(&obj->q2, x);

}

5.

  • 再接着就是最复杂的出栈操作。

  • 由前面的介绍，我们已经知道了思路，而现在最主要的，就是如何判断那个队列为空。

  • 我们首先假设q1为空q2不为空，然后判断一下q1是不是真的为空，如果是，什么事没有，如果不是，就换一下，变成q2为空，q1不为空，思路就是这样，具体还需看代码。

  • 知道谁为空谁不为空后，接下来就是前面所说的思路的操作了。

相关代码实现：

int myStackPop(MyStack* obj) {
	assert(!myStackEmpty(obj));
	
	// 假定q1为空，q2不为空
	Que* emptyQ = &obj->q1;
	Que* nonemptyQ = &obj->q2;
	
	// 判断q1是否真的为空，不为空则进去if，交换“身份”
	if (!QEmpty(emptyQ))
	{
		emptyQ = &obj->q2;
		nonemptyQ = &obj->q1;
	}
	
	// 然后就是前面所说的操作
	// 不为空的依次出队列，并将出队列的数据入到空的队列中
	// 直到出的还剩一个数据停止
	while (QSize(nonemptyQ) > 1)
	{
		int front = QFront(nonemptyQ);
		QPush(emptyQ, front);
		QPop(nonemptyQ);
	}
	
	// 最后将最后一个数据存起来
	int front = QFront(nonemptyQ);
	// 删除这个数据
	QPop(nonemptyQ);
	// 在返回存的这个数据
	return front;
}

6.

  • 当然还有获取栈顶数据的功能。

  • 我们先找到不为空的那个队列，然后调用其获取队尾数据的函数，最后将这个函数返回的结果返回即可。

相关代码实现：

int myStackTop(MyStack* obj) {
	assert(!myStackEmpty(obj));

	if (!QEmpty(&obj->q1)) return QBack(&obj->q1);
	else return QBack(&obj->q2);
}

7.

  • 论栈的功能怎么能少得了判空呢。

  • 对于该栈的判空，我们实际上只需要判断那两个队列是否为空即可。

相关代码实现：

bool myStackEmpty(MyStack* obj) {
	return QEmpty(&obj->q2) && QEmpty(&obj->q1);
}

8.

  • 最后就是栈的销毁了。

  • 将两个队列销毁（调用自己的销毁函数），然后将栈销毁即可。

相关代码实现：

void myStackFree(MyStack* obj) {
	QDestroy(&obj->q1);
	QDestroy(&obj->q2);
	free(obj);
}

整体的实现代码

// 队列的数据的类型
typedef int QDataType;
// 节点结构	
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

// 队列结构
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Que;

// 初始化队列
void QInit(Que* pq);
// 销毁队列
void QDestroy(Que* pq);
// 数据入队列
void QPush(Que* pq, QDataType x);
// 数据出队列
void QPop(Que* pq);
// 获取队列中有效元素个数
int QSize(Que* pq);
// 队列判空
bool QEmpty(Que* pq);
// 取队头数据
QDataType QFront(Que* pq);
// 取队尾数据
QDataType QBack(Que* pq);

// 初始化队列
void QInit(Que* pq)
{
	assert(pq);

	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}

// 队列销毁
void QDestroy(Que* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}

// 数据入队列
void QPush(Que* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	assert(newnode);
	newnode->data = x;
	newnode->next = NULL;

	if (pq->size == 0) pq->head = pq->tail = newnode;
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}

	pq->size++;
}
// 数据出队列 
void QPop(Que* pq)
{
	assert(pq && !QEmpty(pq));

	if (pq->head == pq->tail)
	{
		free(pq->head);
		pq->head = NULL;
		pq->tail = NULL;
	}
	else
	{
		QNode* tmp = pq->head->next;
		free(pq->head);
		pq->head = tmp;
	}

	pq->size--;
}

// 获取队列中有效元素个数
int QSize(Que* pq)
{
	assert(pq);
	return pq->size;
}
// 队列判空
bool QEmpty(Que* pq)
{
	assert(pq);
	return pq->size == 0;
}

// 取队头数据
QDataType QFront(Que* pq)
{
	assert(pq && !QEmpty(pq));
	return pq->head->data;
}
// 取队尾数据
QDataType QBack(Que* pq)
{
	assert(pq && !QEmpty(pq));
	return pq->tail->data;
}

typedef struct {
    Que q1;
    Que q2;
} MyStack;

bool myStackEmpty(MyStack* obj);

MyStack* myStackCreate() {
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
	assert(obj);

	QInit(&obj->q1);
	QInit(&obj->q2);

	return obj;
}

void myStackPush(MyStack* obj, int x) {

	if (!QEmpty(&obj->q1)) QPush(&obj->q1, x);
	else QPush(&obj->q2, x);

}

int myStackPop(MyStack* obj) {
	assert(!myStackEmpty(obj));

	Que* emptyQ = &obj->q1;
	Que* nonemptyQ = &obj->q2;

	if (!QEmpty(emptyQ))
	{
		emptyQ = &obj->q2;
		nonemptyQ = &obj->q1;
	}

	while (QSize(nonemptyQ) > 1)
	{
		int front = QFront(nonemptyQ);
		QPush(emptyQ, front);
		QPop(nonemptyQ);
	}

	int front = QFront(nonemptyQ);
	QPop(nonemptyQ);
	return front;
}

int myStackTop(MyStack* obj) {
	assert(!myStackEmpty(obj));

	if (!QEmpty(&obj->q1)) return QBack(&obj->q1);
	else return QBack(&obj->q2);
}

bool myStackEmpty(MyStack* obj) {
	return QEmpty(&obj->q2) && QEmpty(&obj->q1);
}

void myStackFree(MyStack* obj) {
	QDestroy(&obj->q1);
	QDestroy(&obj->q2);
	free(obj);
}

😎写在最后

💝学会了用队列实现栈，那么下一篇文章就是教大家如何用栈实现队列了。栈和队列还真是有趣呢！
❤️‍🔥后续将会持续输出有关数据结构的文章，你们的支持就是我写作的最大动力！

感谢阅读本小白的博客，错误的地方请严厉指出噢~

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

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

相关文章

synchronized 加锁 this 和 class 的区别

synchronized 加锁 this 和 class 的区别

synchronized 是 Java 语言中处理并发问题的一种常用手段&#xff0c;它也被我们亲切的称之为“Java 内置锁”&#xff0c;由此可见其地位之高。然而 synchronized 却有着多种用法&#xff0c;当它修饰不同对象时&#xff0c;其意义也是不同的&#xff0c;下面我们一起来看。 ​…
阅读更多...
云原生时代顶流消息中间件Apache Pulsar部署实操之Pulsar IO与Pulsar SQL

云原生时代顶流消息中间件Apache Pulsar部署实操之Pulsar IO与Pulsar SQL

文章目录Pulsar IO (Connector连接器)基础定义安装Pulsar和内置连接器连接Pulsar到Cassandra安装cassandra集群配置Cassandra接收器创建Cassandra Sink验证Cassandra Sink结果删除Cassandra Sink连接Pulsar到PostgreSQL安装PostgreSQL集群配置JDBC接收器创建JDBC Sink验证JDBC …
阅读更多...
【网络】网络层协议——IP

【网络】网络层协议——IP

目录网络层IP协议IP基础知识IP地址IP报头格式网段划分CIDR特殊的IP地址IP地址的数量限制私有IP地址和公有IP地址路由IP总结网络层 在复杂的网络环境中确定一个合法的路径。 IP协议 IP协议作为整个TCP/IP中至关重要的协议&#xff0c;主要负责将数据包发送给最终的目标计算机…
阅读更多...
多线程 (六) 单例模式

多线程 (六) 单例模式

&#x1f389;&#x1f389;&#x1f389;点进来你就是我的人了 博主主页&#xff1a;&#x1f648;&#x1f648;&#x1f648;戳一戳,欢迎大佬指点!人生格言&#xff1a;当你的才华撑不起你的野心的时候,你就应该静下心来学习! 欢迎志同道合的朋友一起加油喔&#x1f9be;&am…
阅读更多...
蓝桥杯刷题冲刺 | 倒计时19天

蓝桥杯刷题冲刺 | 倒计时19天

作者&#xff1a;指针不指南吗 专栏&#xff1a;蓝桥杯倒计时冲刺 &#x1f43e;马上就要蓝桥杯了&#xff0c;最后的这几天尤为重要&#xff0c;不可懈怠哦&#x1f43e; 文章目录1.抓住那头牛2.排列序数1.抓住那头牛 题目 链接&#xff1a; 抓住那头牛 - C语言网 (dotcpp.com…
阅读更多...
网络安全之防火墙

网络安全之防火墙

目录 网络安全之防火墙 路由交换终归结底是联通新设备 防御对象&#xff1a; 定义&#xff1a; 防火墙的区域划分&#xff1a; 包过滤防火墙 --- 访问控制列表技术 --- 三层技术 代理防火墙 --- 中间人技术 --- 应用层 状态防火墙 --- 会话追踪技术 --- 三层、四层 UTM …
阅读更多...
CrossOver零知识学习1 —— 初识

CrossOver零知识学习1 —— 初识

本文部分内容参考CrossOver22全新版功能简介 免费mac虚拟机工具_CoCo玛奇朵的博客-CSDN博客 特此致谢&#xff01; 一、CrossOver简介 CrossOver是由CODE WEAVERS公司开发的类虚拟机软件&#xff0c;目的是使Linux和Mac OS X操作系统和Window系统兼容。CrossOver英文原意为“…
阅读更多...
强烈推荐：0基础入门网安必备《网络安全知识图谱》

强烈推荐：0基础入门网安必备《网络安全知识图谱》

蚁景网安学院一直专注于网安实战技能培养&#xff0c;提供全方位的网安安全学习解决方案。我们集聚专业网安技术大佬资源&#xff0c;倾力打造了这本更全面更系统的“网络安全知识图谱”&#xff0c;让大家在网络安全学习路上不迷茫。 在这份网安技能地图册里&#xff0c;我们对…
阅读更多...
01 | Msyql系统架构

01 | Msyql系统架构

目录MySQL系统架构连接器查询缓存分析器优化器执行器MySQL系统架构 大体来说&#xff0c;MySQL分为Server层和引擎层两部分。 Server层包含链接器、查询缓存、分析器、优化器和执行器&#xff0c;而引擎层负责的是数据的存储和读取&#xff0c;支持InnoDB、Myisam、Memory等多…
阅读更多...
CSS实现文字凹凸效果

CSS实现文字凹凸效果

使用两个div分别用来实现凹凸效果&#xff1b;text-shadow语法 text-shadow: h-shadow v-shadow blur color; h-shadow&#xff1a;必需。水平阴影的位置。允许负值。 v-shadow &#xff1a;必需。垂直阴影的位置。允许负值。 blur&#xff1a;可选&#xff0c;模糊的距离。 co…
阅读更多...
【C语言】你真的了解结构体吗

【C语言】你真的了解结构体吗

引言✨我们知道C语言中存在着整形(int、short...)&#xff0c;字符型(char)&#xff0c;浮点型(float、double)等等内置类型&#xff0c;但是有时候&#xff0c;这些内置类型并不能解决我们的需求&#xff0c;因为我们无法用这些单一的内置类型来描述一些复杂的对象&#xff0c…
阅读更多...
k8s部署prometheus

k8s部署prometheus

k8s部署prometheus 版本说明&#xff1a; k8s&#xff1a;1.24.4 prometheus&#xff1a;release-0.12&#xff08;https://github.com/prometheus-operator/kube-prometheus.git&#xff09; 本次部署采用operator的方式将prometheus部署到k8s中&#xff0c;需对k8s和prom…
阅读更多...
springboot+vue驾校管理系统 idea科目一四预约考试,练车

springboot+vue驾校管理系统 idea科目一四预约考试,练车

加大了对从事道路运输经营活动驾驶员的培训管理力度&#xff0c;但在实际的管理过程中&#xff0c;仍然存在以下问题&#xff1a;(1)管理部门内部人员在实际管理过程中存在人情管理&#xff0c;不进行培训、考试直接进行发证。(2)从业驾驶员培训机构不能严格执行管理部门的大纲…
阅读更多...
SpringBoot解析指定Yaml配置文件

SpringBoot解析指定Yaml配置文件

再来个文章目录 文章目录前言1、自定义配置文件2、配置对象类3、YamlPropertiesSourceFactory下面还有投票&#xff0c;帮忙投个票&#x1f44d; 前言 最近在看某个开源项目代码并准备参与其中&#xff0c;代码过了一遍后发现多个自定义的配置文件用来装载业务配置代替数据库…
阅读更多...
使用 Python 从点云生成 3D 网格

使用 Python 从点云生成 3D 网格

从点云生成 3D 网格的最快方法 已经用 Python 编写了几个实现来从点云中获取网格。它们中的大多数的问题在于它们意味着设置许多难以调整的参数&#xff0c;尤其是在不是 3D 数据处理专家的情况下。在这个简短的指南中&#xff0c;我想展示从点云生成网格的最快和最简单的过程。…
阅读更多...
继承和派生

继承和派生

&#x1f436;博主主页&#xff1a;ᰔᩚ. 一怀明月ꦿ ❤️‍&#x1f525;专栏系列&#xff1a;线性代数&#xff0c;C初学者入门训练&#xff0c;题解C&#xff0c;C的使用文章&#xff0c;「初学」C &#x1f525;座右铭&#xff1a;“不要等到什么都没有了&#xff0c;才下…
阅读更多...
手撕数据结构—队列

手撕数据结构—队列

队列队列的话只允许在一端插入&#xff0c;在另外一端删除。插入数据的那一段叫做队尾&#xff0c;出数据的那一段叫做队头&#xff08;从尾巴插入&#xff09;。因此的话队列是先进先出的。入的顺序与出的顺序的话是一样的。这个与栈是不一样的&#xff0c;因为栈的话就是说如…
阅读更多...
问题【Java 基础】

问题【Java 基础】

基础1、成员变量与局部变量的区别2、静态变量有什么作用3、字符型常量和字符串常量的区别4、静态方法为什么不能调用非静态成员5、静态方法和实例方法有何不同6、重载和重写有什么区别7、什么是可变长参数8、Java 中的几种基本数据类型了解么9、基本类型和包装类型的区别10、包…
阅读更多...
【数据结构】树和二叉树的概念及结构

【数据结构】树和二叉树的概念及结构

目录 1.树概念及结构 1.1 树的概念 1.2 树的相关概念 1.3树的表示 1.4 树在实际中的应用 2.二叉树概念及结构 2.1 概念 2.2 特殊的二叉树 2.2.1 满二叉树 2.2.2 完全二叉树 1.树概念及结构 1.1 树的概念 树是一种非线性的数据结构&#xff0c;它是由n(n>0) 个有…
阅读更多...
一款专门为自动化测试打造的集成开发工具【Aqua】，“能快速构建自动化测试项目”，就问你爽不爽吧，，，

一款专门为自动化测试打造的集成开发工具【Aqua】，“能快速构建自动化测试项目”，就问你爽不爽吧，，，

你好&#xff0c;我是不二。 随着行业内卷越来越严重&#xff0c;自动化测试已成为测试工程师的必备技能&#xff0c;谈及自动化测试肯定少不了编程&#xff0c;说到编程肯定离不开集成开发工具&#xff0c;比如&#xff1a;IntelliJ IDEA可以帮助我们快速构建Maven项目、sprin…
阅读更多...
最新文章

Copyright @ 2022~2023