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

💯💯💯

本篇总结利用队列如何实现栈的相关操作，不难观察，栈和队列是可以相互转化的，需要好好总结它们的特性，构造出一个恰当的结构来实现即可，所以本篇难点不在代码思维，而是对结构的理解。

  • ⏰1.用队列实现栈
    • 🕑"出栈"
    • 🕓"压栈"
    • 🕕"获取栈顶数据"
    • 🕖"判断是否为空"
    • 🕗"销毁栈"
  • ⏰2.整体代码

在这里插入图片描述 请添加图片描述

⏰1.用队列实现栈

在这里插入图片描述

做该种题要记住两个关键点：
一个队列用来插入数据。一个队列用来存数据

1.空队列用来导数据
2.非空队列用来插入数据

我们知道队列的特点：先进先出，只能在一端插入，一端删除。
而栈的特点是：先进后出，后进先出。

在这里插入图片描述

比如要让两个队列实现栈的功能，就拿出栈来说，如果要应该将栈顶元素5拿走。
但在队列1中，因为只能在队头进行删除，所以只能拿走元素1.
那该怎么办呢？

要想pop掉队列中的元素5，我们得想办法将它搞成队头元素才行，这样才可以删除掉它。而如果队列2是空队列的话，那么我们这样做：将元素5之前的4个元素都放到队列2中，队列1中就只剩下元素5了，那元素5就相当于队头元素，就可以进行pop操作最终将其删除掉了，删除后队列1又变成空队列了。
而队列2就是非空队列。而重复这样的操作就可以实现删除栈顶元素的操作了：首先将非空队列中前n-1个元素导入空队列中，然后再pop掉非空队列中的元素。
在这里插入图片描述

我们如果想要进行压栈操作，将元素6，7压入栈顶，那该如何插入呢？
在这里插入图片描述
其实只要在非空队列中尾插元素即可，也就是正常的入队即可
那我们来按照空与非空来区别两个队列，因为两个不同队列有着不同的功能：
非空队列：用来插入数据
空队列：用来导数据，存数据

首先我们需要将队列的数据结构写出来，然后定义两个队列。

//利用单链表来实现队列
typedef int QData;
typedef struct QNode
{
	struct QNode* next;
	int data;
}QNode;
//因为队列的数据结构操作需要找尾，这就需要传多个参数了，很麻烦，所以我们再分装个结构体将多个数据变成一个
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;
void QueueInit(Queue *pq);//初始化队列
void QueueDestroy(Queue *pq);//销毁队列
void QueuePush(Queue*pq ,QData x);//入队，从队尾插入一个数据，尾删
void QueuePop(Queue *pq);//出队，从队头删除数据，头删
bool QueueEmpty(Queue *pq);//判断队列是否为空
int QueueSize(Queue*pq);//获得队列有效数据个数大小
QData QueueFront(Queue*pq);//获取队头数据
QData QueueBack(Queue*pq);//获取队尾数据

void QueueInit(Queue* pq)//初始化队列
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}
void QueueDestroy(Queue* pq)//销毁队列
{
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}
void QueuePush(Queue* pq, QData x)//入队，从队尾插入一个数据，尾删
{
	assert(pq);
/*	QNode* cur = pq->head;
	*/QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc");
	}
	newnode->data=x;
	newnode->next = NULL;
	if (pq->head == NULL)
	{
		//赋值
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		//更新tail的位置
		pq->tail = newnode;
	}
	pq->size++;

}
void QueuePop(Queue* pq)//出队，从队头删除数据，头删
{
	assert(pq);
	//头删之前需要判断链队列是否为空
	assert(pq->head!=NULL);
	//改变头指针的指向
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
     //当headtail都指向一起是，把head指向的空间释放，那tail就变成野指针了
	//所以还需要考虑最后一个结点，需要将tail和head一起置空
	if (pq->head==NULL)//只管头删，最后再处理。
	{
		
		pq->tail=NULL;
	}
	pq->size--;
}
//链表哨兵卫里面可以存放大小吗？
//不能--可能不是int类型--如果我们像求一个链表的大小通常需要遍历链表

bool QueueEmpty(Queue* pq)//判断队列是否为空----主要size的作用
{
	assert(pq);
	return pq->size == 0;
	//return pq->head=pq->tailk=NULL;
}
int QueueSize(Queue* pq)//获得队列有效数据个数大小
{
	assert(pq);
	return pq->size;
}

QData QueueFront(Queue* pq)//获取队头数据
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

QData QueueBack(Queue* pq)//获取队尾数据
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

定义两个队列q1，q2


typedef struct //该重命名方式为匿名结构体，没有名字但有效
{
	Queue q1;
	Queue q2;
} MyStack;

然后要获得指向MyStack的指针


MyStack* myStackCreate() //注意这里最后要返回指向栈的指针，并且空间是可使用的，所以必须动态开辟空间，如果只是由栈上开辟空间，那么函数结束，空间就被销毁，而在堆上申请的空间不会被销毁，所以需要用malloc给这个结构体开辟空间
{
  
}

🕑"出栈"

Pop就需要导数据了，将非空的数据导入空队列中，这样才可以删除最后一个元素。
但一开始并不知道谁是空的谁是非空，所以我们需要先讨论下
所以步骤就是：
1.先判断哪个队列是非空，哪个队列是空。
2.将非空队列前n-1个元素导入空队列
3.删除非空队列元素


int myStackPop(MyStack* obj) 
{
	Queue* empty = &obj->q1;//假设一开始q1是空队列
	Queue* nonempty = &obj->q2;//假设q2是非空队列
	if (!QueueEmpty(empty))//如果假设错误那q1就是非空队列，q2是空队列
	{
		empty = &obj->q2;
		nonempty = &obj->q1;
	}
	//这样我们就不用管谁是空谁是非空了，empty就是空，nonempty就是非空
	//将非空队列前n-1个元素导入空队列中华
	//【导数据】
	while (QueueSize(nonempty) - 1 > 0)
	{
		QueuePush(empty, QueueFront(nonempty));
		       //插入空队列   //获取队头元素
		QueuePop(nonempty);//将数据pop掉
	}
	//走到这时说明非空队列就剩最后一个元素了，即栈顶元素
	//要求返回栈顶元素，所以我们需要保存下来
	int top = QueueFront(nonempty);
	QueuePop(nonempty);//删除最后一个元素
	return top;
}

🕓"压栈"

往非空队列里插入，哪个队列不为空就往哪里插，两个都为空，随便插入一个即可

void myStackPush(MyStack* obj, int x) 
{
	assert(obj);
	if (!QueueEmpty(&obj->q1))//如果q1不为空
	{
		QueuePush(&obj->q1, x);//就将数据插入q1中
	}
	else//如果q1为空，则q2不为空，就往q2中插入数据
	{
		QueuePush(&obj->q2, x);//或者都为空，随便进入一个
	}
}

🕕"获取栈顶数据"

取栈顶数据，其实就是非空队尾数据
但仍然不知道谁是非空谁是空，所以需要讨论下

int myStackTop(MyStack* obj) {
	assert(obj);
	
	if (!QueueEmpty(&obj->q1))//如果q1不为空
	{
		return QueueBack(&obj->q1);//队尾数据即栈顶数据
	}
	else//如果q1为空，则q2不为空，
	{
		return QueueBack(&obj->q2);//队尾数据即栈顶数据
	}
	
}

🕖"判断是否为空"

怎么算空呢？当然当两个队列都为空时才是真正的空。


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

🕗"销毁栈"

如何销毁用队列实现的栈呢？
这要求我们需要搞清楚这个栈的结构到底是什么样子：

栈是由两个队列构成，而队列又是由结点和一个size构成。结点又是由一个data数据和一个指针构成。
在这里插入图片描述
我们应该先从里面开始释放，不然先释放外面的里面的空间就找不到了，所以从里到外释放。先释放两个队列，然后再释放栈的空间。


void myStackFree(MyStack* obj) 
{
	assert(obj);
	QueueDestroy(&obj->q1);
	QueueDestroy(&obj->q2);
	free(obj);
	obj = NULL;
}

⏰2.整体代码



typedef int QData;
typedef struct QNode
{
	struct QNode* next;
	int data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;
void QueueInit(Queue *pq);//初始化队列
void QueueDestroy(Queue *pq);//销毁队列
void QueuePush(Queue*pq ,QData x);//入队，从队尾插入一个数据，尾删
void QueuePop(Queue *pq);//出队，从队头删除数据，头删
bool QueueEmpty(Queue *pq);//判断队列是否为空
int QueueSize(Queue*pq);//获得队列有效数据个数大小
QData QueueFront(Queue*pq);//获取队头数据
QData QueueBack(Queue*pq);//获取队尾数据

void QueueInit(Queue* pq)//初始化队列
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}
void QueueDestroy(Queue* pq)//销毁队列
{
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}
void QueuePush(Queue* pq, QData x)//入队，从队尾插入一个数据，尾删
{
	assert(pq);
/*	QNode* cur = pq->head;
	*/QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc");
	}
	newnode->data=x;
	newnode->next = NULL;
	if (pq->head == NULL)
	{
		//赋值
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		//更新tail的位置
		pq->tail = newnode;
	}
	pq->size++;

}
void QueuePop(Queue* pq)//出队，从队头删除数据，头删
{
	assert(pq);
	//头删之前需要判断链队列是否为空
	assert(pq->head!=NULL);
	//改变头指针的指向
	
	
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
     //当headtail都指向一起是，把head指向的空间释放，那tail就变成野指针了
	//所以还需要考虑最后一个结点，需要将tail和head一起置空
	if (pq->head==NULL)//只管头删，最后再处理。
	{
		pq->tail=NULL;
	}
	pq->size--;

}

bool QueueEmpty(Queue* pq)//判断队列是否为空----主要size的作用
{
	assert(pq);
	return pq->size == 0;
	//return pq->head=pq->tailk=NULL;
}
int QueueSize(Queue* pq)//获得队列有效数据个数大小
{
	assert(pq);
	return pq->size;
}

QData QueueFront(Queue* pq)//获取队头数据
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

QData QueueBack(Queue* pq)//获取队尾数据
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

//柔性数组与顺序表的区别
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;//用两个队列实现的栈
//匿名定义结构体

MyStack* myStackCreate()//发现没有传入参数并且返回值是指向栈的指针说明里面是用malloc开辟的内存而不是在栈上开辟的
 {
     MyStack*st=(MyStack*)malloc(sizeof(MyStack));//
     if(st==NULL)
     {
         perror("malloc");
     }
    //需要对两个队列进行初始化
    QueueInit(&st->q1);
    QueueInit(&st->q2);
     return st;
}

void myStackPush(MyStack* obj, int x)//压栈怎么压呢？直接在不为空的队列后面尾插即可
{
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj)//出栈怎么出呢？ 需要将不为空的队列前面的数据导入为空的队列中，再将最后一个数据删除掉，在删除之前保存删除的数据。//但不知道谁是空谁不是空所以需要判断一下
{
   Queue *empty=&obj->q1;//假设q1是空队列
   Queue *nonempty=&obj->q2;//假设q2是非空队列
   if(!QueueEmpty(&obj->q1))
   {
       empty=&obj->q2;
       nonempty=&obj->q1;
   }
   //现在不需要知道谁是空谁是非空了
   //将非空队列数据导入空队列中
   while(QueueSize(nonempty)-1>0)
   {
       QueuePush(empty,QueueFront(nonempty));
       QueuePop(nonempty);
   }
   //删除最后一个数据之前需要保存
   int top=QueueFront(nonempty);
   QueuePop(nonempty);
   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) 
{
   //从里到外释放，不能从外到里释放
   QueueDestroy(&obj->q1);
   QueueDestroy(&obj->q2);
   free(obj);
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/

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

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

相关文章

大数据应用——Hadoop运行模式（伪分布式运行）

大数据应用——Hadoop运行模式（伪分布式运行）

4.2 伪分布式运行模式4.2.1 启动HDFS并运行MapReduce程序1. 分析 （1）配置集群（2）启动、测试集群增、删、查没有改（多台机子麻烦）（3）执行WordCount案例2. 执行步骤（1&…
阅读更多...
前端vue实现导出pdf文件报告组件

前端vue实现导出pdf文件报告组件

大屏项目有一个需求，需要对展示的内容进行文件导出，但是目前后台没有相关的逻辑，所以只能前端硬上，在参考了其他许多的逻辑之后，目前我自己这边做了一套比较笨的组件，通过拼接标签这种方法来实现对你想需要…
阅读更多...
队列-我的基础算法刷题之路（六）

队列-我的基础算法刷题之路（六）

本篇博客旨在整理记录自已对队列的一些总结，以及刷题的解题思路，同时希望可给小伙伴一些帮助。本人也是算法小白，水平有限，如果文章中有什么错误之处，希望小伙伴们可以在评论区指出来，共勉 💪。…
阅读更多...
seaborn从入门到精通03-绘图功能实现02-分类绘图Categorical plots

seaborn从入门到精通03-绘图功能实现02-分类绘图Categorical plots

seaborn从入门到精通03-绘图功能实现02-分类绘图Categorical plots总结参考关系-分布-分类分类绘图-Visualizing categorical data图形级接口catplot--figure-level interface导入库与查看tips和diamonds 数据分类散点图参考分布散点图stripplot分布密度散点图-swarmplot&#…
阅读更多...
进程与线程

进程与线程

文章目录进程与线程进程什么是进程进程的组成程序段数据段程序控制块例子线程什么是线程线程的组成线程描述信息程序计数器栈内存例子进程与线程的区别进程与线程 进程 什么是进程 ​ 什么是进程呢？简单来说，进程是程序的一次启动执行。什么是 程序呢…
阅读更多...
【C#进阶】C# 集合类

【C#进阶】C# 集合类

序号系列文章16【C#进阶】C# 索引器17【C#进阶】C# 委托18【C#进阶】C# 事件文章目录前言1、集合类是什么2、动态数组（ArrayList）3、压缩数组（BitArray）4、哈希表（Hashtable）5、队列（Queue&…
阅读更多...
【数据结构】链表OJ题

【数据结构】链表OJ题

目录面试题 02.04 分割链表剑指 Offer II 027 回文链表160 相交链表141 环形链表142 环形链表 II138 复制带随机指针的链表面试题 02.04 分割链表 定义lesshead和greaterhead链接小于和大于等于k的值分别设置哨兵位和尾节点指针最后将两表去除哨兵位再链接 struct ListNode* p…
阅读更多...
内存泄漏和内存溢出的区别

内存泄漏和内存溢出的区别

参考答案 内存溢出(out of memory)：指程序在申请内存时，没有足够的内存空间供其使用，出现 out of memory。内存泄露(memory leak)：指程序在申请内存后，无法释放已申请的内存空间，内存泄露堆积会导致内存被…
阅读更多...
论文解读：PP-LiteSeg: A Superior Real-Time Semantic Segmentation Model

论文解读：PP-LiteSeg: A Superior Real-Time Semantic Segmentation Model

发表时间：2022 论文地址：https://arxiv.org/abs/2204.02681 项目地址：https://github.com/PaddlePaddle/PaddleSeg PP-LiteSeg，一个新的轻量级实时语义分割任务模型，在分割精度和推理速度之间实现了一种最先进的权衡…
阅读更多...
JVM垃圾回收机制

JVM垃圾回收机制

文章目录JVM垃圾回收机制如何确定该对象是垃圾引用计数可达性分析如何释放对象常用策略JVM垃圾回收机制 以对象为单位来进行回收 如何确定该对象是垃圾 Java 中使用 可达性分析方法 Python 中时使用 引用计数方法 引用计数 使用额外的计数器，来记录某个对象有多少个…
阅读更多...
【致敬未来的攻城狮计划】连续打卡第4天+物联网操作系统概述

【致敬未来的攻城狮计划】连续打卡第4天+物联网操作系统概述

开启攻城狮的成长之旅！这是我参与的由 CSDN博客专家 架构师李肯（http://yyds.recan-li.cn）和 瑞萨MCU （https://www.renesas.cn/cn/zh） 联合发起的「 致敬未来的攻城狮计划 」的第 4 天，点击查看活动计划详…
阅读更多...
【Vue3】用Element Plus实现列表界面

【Vue3】用Element Plus实现列表界面

🏆今日学习目标：用Element Plus实现列表界面 😃创作者：颜颜yan_ ✨个人格言：生如芥子，心藏须弥 ⏰本期期数：第四期 🎉专栏系列：Vue3 文章目录前言效果图目录简介修改vite…
阅读更多...
基于springboot框架实现心理健康心灵治愈交流平台【源码+论文】展示

基于springboot框架实现心理健康心灵治愈交流平台【源码+论文】展示

基于springboot框架实现心灵心理健康 【源码论文】开发语言：Java 框架：springboot JDK版本：JDK1.8 服务器：tomcat7 数据库：mysql 5.7 数据库工具：Navicat11 开发软件：eclipse/myeclipse/idea Ma…
阅读更多...
CSS 7种居中效果实现原理与案例

CSS 7种居中效果实现原理与案例

目录 1.标准盒子居中 2.定位-绝对定位实现居中 3.表格方式实现垂直居中 4.弹性盒子：实现垂直居中 5.通过行高line-height实现垂直居中 6.变形定位实现居中 7.网格实现垂直居中 1.标准盒子居中 不需要设置display，只能实现水平居中 效果&#xff1…
阅读更多...
代码随想录算法训练营第五十二天| ● 300.最长递增子序列 ● 674. 最长连续递增序列 ● 718. 最长重复子数组

代码随想录算法训练营第五十二天| ● 300.最长递增子序列 ● 674. 最长连续递增序列 ● 718. 最长重复子数组

300.最长递增子序列 看完题后的思路 dp[i] [0,i]子数组中,以nums[i]结尾的子序列的长度 dp[i]dp[j]1 j从i-1向0遍历,在所有nums[j]<nums[i]中dp[j]最大 初始化 dp[0]1 代码 class Solution {public int lengthOfLIS(int[] nums) {if (nums.length0){return 0;}int[] dpne…
阅读更多...
Gateway服务网关

Gateway服务网关

Spring Cloud Gateway为微服务架构提供一种简单有效的统一的 API 路由管理方式。Gateway网关是所有微服务的统一入口。网关的核心功能特性&#xff1a;请求路由和负载均衡&#xff1a;一切请求都必须先经过gateway&#xff0c;但网关不处理业务&#xff0c;而是根据某种规则&am…
阅读更多...
vue3自定义svg图标组件

vue3自定义svg图标组件

可参考&#xff1a; 未来必热&#xff1a;SVG Sprites技术介绍 懒人神器&#xff1a;svg-sprite-loader实现自己的Icon组件 在Vue3项目中使用svg-sprite-loader 前置知识 在页面中&#xff0c;虽然可以通过如下的方式使用img标签&#xff0c;来引入svg图标。但是&#xff0c;…
阅读更多...
架构的容错性设计

架构的容错性设计

面对程序故障&#xff0c;我们该做些什么 “容错性设计”&#xff08;Design for Failure&#xff09;是微服务的另一个核心原则&#xff0c;也是架构反复强调的开发观念的转变。 流量治理 流量治理所要解决的问题 1.某一个服务的崩溃&#xff0c;会导致所有用到这个服务的…
阅读更多...
Unity --- 三维数学 --- Vector类 --- 向量部分

Unity --- 三维数学 --- Vector类 --- 向量部分

1.注意每一个数字都表示一段有向位移 --- 有方向的距离 1.从尾到头那一段称为向量的模长 --- magnitude (direction对应的是向量的方向) 2.一个向量有大小 -- 模长(magnitude) &#xff0c; 有方向&#xff08;direction&#xff09; 1.向量的模长等于各分量的平方和的平方根…
阅读更多...
IO流你了解多少

IO流你了解多少

IO流你了解多少 &#x1f3e0;个人主页&#xff1a;shark-Gao &#x1f9d1;个人简介&#xff1a;大家好&#xff0c;我是shark-Gao&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f389;目前状况&#xff1a;23届毕业生&#xff0c;目前在某公…
阅读更多...
最新文章

Copyright @ 2022~2023