栈和队列的转换

  在之前的博客当中我们已经学习了栈和队列。在本次的博客当中我们就来学习一下怎么将栈和队列进行相互转换。

  栈和队列的相互转换其实是两道OJ题。如果在leetcode上面刷过题的小伙伴们可能早就见过这两种数据结构的相互转换。下面我们就来分别讲解一下这两道OJ题目的编写思路。

    🌵用队列实现栈

题目详情如下：

bd2fc494ee6b41dd9f8a39df07f85587.png   题目中要求我们使用两个队列实现栈的结构。我们在这里重新来梳理一下队列和栈的结构特点。

    ⭐队列：队列只能在队尾插入数据，只能从队头输出数据。先进入队列的数据也就会先被读取。 

39901254e458435d838e82d789a132ff.png      ⭐栈：栈只能从队头插入数据，也只能从对头输出数据。所以在咋还能当中我们只能够取出最近插入的数据。

596144df079a48b7877756115e9e431f.png   在结构上面栈和队列还是有很大的区别的，所以我们需要使用一定的方式进行栈和队列的相互转换。回到我们本题。

  使用队列实现栈。也就是利用我们先入先出的数据存储方式实现先入后出的数据存储方式。题目中也给了我们一些相应的思路：使用两个队列。

  我们先来构建两个队列：

d0daae3ccf6a4236821b304c6bdd84c6.png   我们直接来说解题思路：我们构建完成两个队列之后可以尝试向一个队列当中插入数据。当我们想要取出数据的时候，根据栈的性质我们需要取得我们队列当中位于队尾的数据。但是又根据队列的性质我们只允许从对头拿出数据，所以我们可以先将队列1当中的数据除了最后一个之外都全部拿到另一个空队列当中。897fd9d80d9242088a38d44ec5da5e48.png  当我们的队列当中是剩下最后一个元素的时候，这个元素就是我们队列当中的队尾元素，也就是栈中需要出栈的元素。我们可以所以我们如果想要出栈的话只需要重复上述的操作即可。fc30231c179845b3bb5f7714704b4007.png   所以在队列实现栈的代码的编写当中我们需要实现一个队列的结构，进而构建出两个队列，之后根据上面分析的思路进一步的编写代码。其中我们的队列可以复用以前实现过的队列当中的代码。


typedef int DataType;

typedef struct QNode
{
	struct QNode* next;
	DataType data;
}QNode;

typedef struct Queue
{
	struct QNode* head;
	struct QNode* tail;
	int size;
}Queue;

//初始化队列
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

//开辟一个新的节点
QNode* BuyNewNode(DataType x)
{
	QNode* ret = (QNode*)malloc(sizeof(QNode));
	if (ret == NULL)
	{
		perror("malloc");
		return NULL;
	}
	ret->data = x;
	ret->next = NULL;
	return ret;
}

//向队列当中插入数据
void QueuePush(Queue* pq, DataType x)
{
	assert(pq);
	QNode* newnode = BuyNewNode(x);
	assert(newnode);
	if (pq->size == 0)
	{
		pq->head = newnode;
		pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}

//删除队列当中的数据
void QueuePop(Queue* pq)
{
	assert(pq);
	if (pq->size == 0)
	{
		printf("队列为空不能进行数据删除。");
		return;
	}
	QNode* ret = pq->head;
	pq->head = pq->head->next;
	free(ret);
	ret = NULL;
	pq->size--;
}

//判断队列的大小
DataType QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

//队列的判空操作
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	if (pq->size == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

//返回队列的队头元素
DataType QueueFront(Queue* pq)
{
	assert(pq);
	return pq->head->data;
}

//返回队列的队尾元素
DataType QueueBack(Queue* pq)
{
	assert(pq);
	return pq->tail->data;
}

//销毁队列
void QueueDestory(Queue* pq)
{
	assert(pq);
	while (pq->head)
	{
		QNode* ret = pq->head;
		pq->head = pq->head->next;
		free(ret);
		ret = NULL;
	}
}


typedef struct {
    Queue s1;
    Queue s2;
} MyStack;

MyStack* myStackCreate() {
    MyStack*ret=(MyStack*)malloc(sizeof(MyStack));
    assert(ret);
    QueueInit(&(ret->s1));
    QueueInit(&(ret->s2));
    return ret;
}

void myStackPush(MyStack* obj, int x) 
{
    //当第二个队列为空时，向第一个队列当中插入数据
    if(QueueEmpty(&obj->s2))
    {
        QueuePush(&obj->s1,x);
    }
    //当第二个队列不为空的时候就向第一个队列当中插入数据
    else
    {
        QueuePush(&obj->s2,x);
    }

}

int myStackPop(MyStack* obj) {
    //将不为空的队列数据除了最后一个全部移到另一个队列当中
    if(QueueEmpty(&obj->s1))
    {
        //判断当前数据是否为最后一个要删除的数据
        while(QueueSize(&obj->s2)!=1)
        {
            DataType ret=QueueFront(&obj->s2);
            QueuePush(&obj->s1,ret);
            QueuePop(&obj->s2);
        }
        DataType tmp=QueueFront(&obj->s2);
        QueuePop(&obj->s2);
        return tmp;
    }
    else
    {
        while(QueueSize(&obj->s1)!=1)
        {
            DataType ret=QueueFront(&obj->s1);
            QueuePush(&obj->s2,ret);
            QueuePop(&obj->s1);
        }
        DataType tmp=QueueFront(&obj->s1);
        QueuePop(&obj->s1);
        return tmp;
    }
}

int myStackTop(MyStack* obj) 
{
    if(QueueEmpty(&obj->s1))
    {
        //判断当前数据是否为最后一个数据
        while(QueueSize(&obj->s2)!=1)
        {
            DataType ret=QueueFront(&obj->s2);
            QueuePush(&obj->s1,ret);
            QueuePop(&obj->s2);
        }
        DataType tmp=QueueFront(&obj->s2);
        QueuePush(&obj->s1,tmp);
        QueuePop(&obj->s2);
        return tmp;
    }
    else
    {
        while(QueueSize(&obj->s1)!=1)
        {
            DataType ret=QueueFront(&obj->s1);
            QueuePush(&obj->s2,ret);
            QueuePop(&obj->s1);
        }
        DataType tmp=QueueFront(&obj->s1);
        QueuePush(&obj->s2,tmp);
        QueuePop(&obj->s1);
        return tmp;
    }
}

bool myStackEmpty(MyStack* obj) 
{
    if(QueueEmpty(&obj->s1)&&QueueEmpty(&obj->s2))
    {
        return true;
    }
    return false;
}

void myStackFree(MyStack* obj) 
{
    //当队列1不为空时，释放队列1当中的所有元素
   while(!QueueEmpty(&obj->s1))
   {
       QueuePop(&obj->s1);
   }
   while(!QueueEmpty(&obj->s2))
   {
       QueuePop(&obj->s2);
   }
}

   我们使用队列实现栈的代码的逻辑如上所示。15e0152b6a544f87bb61af24dafd3b33.png

     🌵用栈实现队列

  使用队列实现完栈之后就轮到使用栈实现队列了。577310271c764e4f84b1912f95fd6007.png

  根据题目中的要求我们同样需要构建出两个栈以实现我们队列当中的功能。1c8d701e98c84c348de3a27906e9b614.png   我们的栈每次只能从栈顶插入数据从栈顶拿出数据，当我们想要以队列的形式拿出数据的时候，也就是从栈的底端拿出数据，我们就必须一个一个将数据全部搬运到另一个栈当中。我们剩下的最后一个数据也就是我们以队列的形式想要出的数据。d4396d51f2074507a23ab0236a2e6b75.png   我们会发现我们移入栈2当中的数据全部已经是排好顺序的了，那么我们每次出数据的时候只需要从栈2当中拿出数据得到的就是我们队头的数据。

  但是我们想要继续插入数据应该怎么办呢？如果直接插入栈2当中会是我们栈中元素顺序混乱，那么假如我们将全部数据都转入栈2当中呢？栈1就会为空，之后我们想要输入数据就向栈1当中输入，想要拿出数据据从栈2当中拿，当我们栈2当中的数据全部拿完时，我们再将栈1当中的数据全部转入栈2当中即可。

944965626e4d43b8b4324f03e976d4c0.png   重复上述步骤之后我们就可以使用栈实现一个队列了。具体的代码如下：

typedef int DataType;

typedef struct STstack
{
	DataType* data;
	int top;
	int capicity;
}ST;

//栈的初始化
void STInit(ST* s1)
{
	assert(s1);
	s1->data = (ST*)malloc(sizeof(ST)*4);
	s1->capicity = 4;
	s1->top = 0;
}

//判断是否需要扩容
void checkcapicity(ST* s1)
{
	if (s1->capicity > s1->top)
	{
		return;
	}
	else
	{
		//需要扩容进行扩容
		ST*tmp= (ST*)realloc(s1->data,sizeof(ST) * s1->capicity*2);
		if (tmp == NULL)
		{
			perror("malloc");
			return;
		}
		s1->data = tmp;
		s1->capicity *= 2;
	}
}

//入栈函数
void STPush(ST* s1, DataType x)
{
	assert(s1);
	//判断是否需要扩容
	checkcapicity(s1);
	s1->data[s1->top] = x;
	s1->top++;
}

//出栈函数
void STPop(ST* s1)
{
	assert(s1);
	//判断栈中是否存在数据，如果不存在数据就不可以进行删除
	if (s1->top == 0)
	{
		printf("空栈不允许进行删除。");
		return;
	}
	//如果不是空栈就删除栈顶元素
	s1->top--;
}

//返回栈顶元素
DataType STTop(ST* s1)
{
	assert(s1);
	//判断栈中是否存在数据
	assert(s1->top);
	return s1->data[s1->top-1];
}

//判断栈为空
bool STEmpty(ST* s1)
{
	assert(s1);
	if (s1->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

//返回链表的大小
int STSize(ST* s1)
{
	assert(s1);
	return s1->top;
}

//销毁栈
void STDestory(ST* s1)
{
	assert(s1);
	free(s1->data);
	s1->data == NULL;
	s1->top = 0;
	s1->capicity = 0;
}

typedef struct {
    ST s1;
    ST s2;
} MyQueue;


MyQueue* myQueueCreate() 
{
    MyQueue*ret=(MyQueue*)malloc(sizeof(MyQueue));
    assert(ret);
    STInit(&ret->s1);
    STInit(&ret->s2);
    return ret;
}

void myQueuePush(MyQueue* obj, int x) 
{
    //两个栈只在左边插入数据
    STPush(&obj->s1,x);
}

int myQueuePop(MyQueue* obj) 
{
    if(STEmpty(&obj->s2))
    {
        while(!STEmpty(&obj->s1))
        {
            //将左边栈中数据导入右栈当中
            DataType ret=STTop(&obj->s1);
            STPop(&obj->s1);
            STPush(&obj->s2,ret);
        }
    }
    DataType tmp=STTop(&obj->s2);
    STPop(&obj->s2);
    return tmp;
}

int myQueuePeek(MyQueue* obj) 
{
    if(STEmpty(&obj->s2))
    {
        while(!STEmpty(&obj->s1))
        {
            //将左边栈中数据导入右栈当中
            DataType ret=STTop(&obj->s1);
            STPop(&obj->s1);
            STPush(&obj->s2,ret);
        }
    }
    DataType tmp=STTop(&obj->s2);
    return tmp;
}

bool myQueueEmpty(MyQueue* obj) 
{
    if(STEmpty(&obj->s1)&&STEmpty(&obj->s2))
    {
        return true;
    }
    return false;
}

void myQueueFree(MyQueue* obj) 
{
    while(!STEmpty(&obj->s1))
    {
        STDestory(&obj->s1);
    }
    while(!STEmpty(&obj->s2))
    {
        STDestory(&obj->s2);
    }
}

   运行结果：

ea95e9661f1f43ed8e7ab7935c1505d3.png

  那么我们栈与队列的相互转换也就实现完毕了，本次博客的内容也就到此结束了。感谢您的观看，再见。 

 

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

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

相关文章

如何基于vue实现倒计时效果

如何基于vue实现倒计时效果

如何基于vue实现倒计时效果 基于vue2 element实现画面效果代码 基于vue2 element 实现画面效果 代码 <template><div><div class"Box"><div style"position: relative;"><el-progress type"circle" :width"…
阅读更多...
使用注解实现REDIS分布式锁

使用注解实现REDIS分布式锁

一、业务背景 有些业务请求&#xff0c;属于耗时操作&#xff0c;需要加锁&#xff0c;防止后续的并发操作&#xff0c;同时对数据库的数据进行操作&#xff0c;需要避免对之前的业务造成影响。 二、分析流程 使用 Redis 作为分布式锁&#xff0c;将锁的状态放到 Redis 统一…
阅读更多...
基于SpringBoot+Vue+Java的社区医院管理服务系统（附源码+数据库）

基于SpringBoot+Vue+Java的社区医院管理服务系统（附源码+数据库）

摘 要 在Internet高速发展的今天&#xff0c;我们生活的各个领域都涉及到计算机的应用&#xff0c;其中包括社区医院管理服务系统的网络应用&#xff0c;在外国线上管理系统已经是很普遍的方式&#xff0c;不过国内的管理系统可能还处于起步阶段。社区医院管理服务系统具有社区…
阅读更多...
一道经典的小学数学题，和它背后的贪心算法(35)

一道经典的小学数学题，和它背后的贪心算法(35)

小朋友们好&#xff0c;大朋友们好&#xff01; 我是猫妹&#xff0c;一名爱上Python编程的小学生。 欢迎和猫妹一起&#xff0c;趣味学Python。 今日主题 这个五一小长假&#xff0c;你玩得怎么样&#xff1f; 今天&#xff0c;咱们先做一道经典的小学数学题&#xff0c;…
阅读更多...
智慧物流信息系统开发需具备哪些功能？

智慧物流信息系统开发需具备哪些功能？

智慧物流软件开发公司在制作管理系统的时候&#xff0c;需要具备的功能有哪些呢&#xff1f; 一、采集跟踪功能。 &#xff08;1&#xff09;、信息采集&#xff1a;信息采集跟踪系统是智能物流系统的重要组成部分。物流信息采集系统主要由RFID射频识别系统和Savan…
阅读更多...
2022年度项目管理软件排名揭晓：哪些软件在市场中脱颖而出？

2022年度项目管理软件排名揭晓：哪些软件在市场中脱颖而出？

在项目管理软件的选择过程中&#xff0c;用户会倾向于参考一些软件排名来辅助自己进行选择。软件排名方面推荐参考G2&#xff0c;一个国外的靠谱软件评测网站&#xff0c;类似于软件版的“大众点评”&#xff0c;软件评价来自于真实用户&#xff0c;网站通过多维度的算法&#…
阅读更多...
JAVA入坑之GUI编程

JAVA入坑之GUI编程

一、相关概述 GUI编程是指通过图形化的方式来实现计算机程序的编写&#xff0c;它可以让用户通过鼠标、键盘等设备来操作计算机&#xff0c;而不是通过命令行来输入指令。在Java中&#xff0c;GUI编程主要使用的是Swing和AWT两种技术 二、AWT 2.1介绍 AWT是Java提供的用来建立…
阅读更多...
八部门联合推动IPv6创新发展 知道创宇助力IPv6快速安全改造

八部门联合推动IPv6创新发展 知道创宇助力IPv6快速安全改造

近日&#xff0c;工业和信息化部、中央网信办、国家发展改革委、教育部、交通运输部、人民银行、国务院国资委、国家能源局等八部门联合印发《关于推进IPv6技术演进和应用创新发展的实施意见》&#xff08;以下简称“《实施意见》”&#xff09;&#xff0c;提出到2025年底&…
阅读更多...
密歇根大学Python 系列之三：Python 数据科学应用项目

密歇根大学Python 系列之三：Python 数据科学应用项目

Python在数据科学领域的应用已经成为了趋势&#xff0c;同时也在不断地发展和演化。对于从事数据科学相关工作的从业者来说&#xff0c;熟练掌握Python已经成为了必备技能之一。而对于其他从业者来说&#xff0c;了解Python在数据科学领域的应用也可以帮助他们更好地理解数据科…
阅读更多...
必知的Facebook广告兴趣定位技巧，更准确地找到目标受众

必知的Facebook广告兴趣定位技巧，更准确地找到目标受众

在Facebook广告投放中&#xff0c;兴趣定位是非常重要的一环。兴趣定位不仅可以帮助我们找到我们想要的目标受众&#xff0c;还可以帮助我们避免一些常见的坑。今天&#xff0c;就让我们一起来看看必知的Facebook广告兴趣定位技巧&#xff0c;更准确地找到目标受众。 1.不要只关…
阅读更多...
pwm调节亮度

pwm调节亮度

文章目录 运行环境&#xff1a;1.1 pwm1)占空比2)A板原理图3)PE11引脚配置4)定时器Timers配置 2.1代码解释1)定时器1初始化函数2)启动定时器中断3)启动PWM/设置占空比4)launch设置5) 编译调试 3.1实验效果 运行环境&#xff1a; ubuntu18.04.melodic 宏基暗影骑士笔记本 stm32…
阅读更多...
VSCode 上的 swift 开发配置

VSCode 上的 swift 开发配置

安装Xcode和VsCode 在下列网址下载安装即可 VsCode: https://code.visualstudio.com/ Xcode:https://developer.apple.com/xcode/resources/ 或者apptore 打开xcode要求安装的东西都允许安装一下 启用 Swift 语言支持 确保你已经安装了 Xcode 和 VSCode。这是开始运行的最简…
阅读更多...
爬虫（requsets）笔记

爬虫（requsets）笔记

1、request_基本使用 pip install requests -i https://pypi.douban.com/simple 一个类型六个属性 r.text 获取网站源码 r.encoding 访问或定制编码方式r.url 获取请求的urlr.content 响应的字节类型r.status_code 响应的状态码r.headers 响应的头信息 import requestsurl…
阅读更多...
【C++入门第四期】类和对象 （ 上 ）

【C++入门第四期】类和对象 （ 上 ）

前言类的使用类的定义类的两种定义方式&#xff1a;成员变量名的定义建议 类的访问限定符类的作用域类的实列化如何计算类的大小结构体内存对齐规则 this指针this指针的特性 前言 C语言是面向过程的&#xff0c;关注的是过程&#xff0c;分析出求解问题的步骤&#xff0c;通过…
阅读更多...
2.2 定点加法 减法运算

2.2 定点加法 减法运算

学习前的建议 以下是一些学习定点加法和减法运算的建议&#xff1a; 掌握定点数的表示方法&#xff1a;在进行定点加法和减法运算之前&#xff0c;需要先了解定点数的表示方法&#xff0c;包括定点数的位数、小数点位置以及符号位等信息。 理解定点加法和减法的原理&#xf…
阅读更多...
五、C++内存管理机制 —— primitives（侯捷）

五、C++内存管理机制 —— primitives（侯捷）

侯捷 C八部曲笔记汇总 - - - 持续更新 ! ! ! 一、C 面向对象高级开发 1、C面向对象高级编程(上) 2、C面向对象高级编程(下) 二、STL 标准库和泛型编程 1、分配器、序列式容器 2、关联式容器 3、迭代器、 算法、仿函数 4、适配器、补充 三、C 设计模式 四、C 新标准 五、C 内存管…
阅读更多...
微服务---分布式事务Seata(XA,AT,TCC,SAGA模式基本使用)

微服务---分布式事务Seata(XA,AT,TCC,SAGA模式基本使用)

分布式事务 1.分布式事务问题 1.1.本地事务 本地事务&#xff0c;也就是传统的单机事务。在传统数据库事务中&#xff0c;必须要满足四个原则&#xff1a; 1.2.分布式事务 分布式事务&#xff0c;就是指不是在单个服务或单个数据库架构下&#xff0c;产生的事务&#xff0c…
阅读更多...
2023牛客五一集训派对day2部分题解

2023牛客五一集训派对day2部分题解

D Duration DDuration 题目大意 给你两个 AA:BB:CC 格式的时间&#xff0c;请你计算它们直接的时间插值&#xff08;秒&#xff09; 解题思路 模拟 代码示例 #include<bits/stdc.h> using namespace std;int h, m, s;int main(){scanf("%d:%d:%d", &…
阅读更多...
跨域问题解决方案

跨域问题解决方案

什么是跨域问题 跨域问题本质上是由浏览器的同源策略造成的&#xff0c;是浏览器对javascript施加的安全限制。 它指的服务A对服务B发起请求时&#xff0c;如果传输协议&#xff08;http、https&#xff09;、ip 地址&#xff08;域名&#xff09;、端口号有任意一个不同&…
阅读更多...
一键轻松拥有自己专属的 ChatGPT 网页版，搭建一个私人的可随时随地访问的ChatGPT网站

一键轻松拥有自己专属的 ChatGPT 网页版，搭建一个私人的可随时随地访问的ChatGPT网站

前言 ChatGPT是一种基于Transformer架构的自然语言处理模型&#xff0c;由OpenAI开发。GPT是“Generative Pre-trained Transformer”的缩写&#xff0c;意为“预训练生成式Transformer模型”。 ChatGPT模型是一种无监督学习模型&#xff0c;它可以在大规模文本数据上进行预训…
阅读更多...
最新文章

Copyright @ 2022~2023