栈和队列的习题详解(3):用栈实现队列

2024-09-06 10:12

本文主要是介绍栈和队列的习题详解(3):用栈实现队列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言:

  小编在上一篇博客中写过了用队列实现栈的操作,可能很多读者朋友会好奇用两个栈是否可以实现队列呢》这是当然可以的,下面小编将要讲述用栈实现队列这个习题,废话不多说,开始今天的做题之旅~


目录

1.用栈实现队列

1.1.题干的解读

1.2.题目的解题思路

1.3.队列的功能实现

 1.3.1.队列的初始化(MyQueue* myQueueCreate()) 

 1.3.2.入队列操作(void myQueuePush(MyQueue* obj, int x)) 

 1.3.3.判断队列是否为空(myQueueEmpty(MyQueue* obj)) 

 1.3.4.出队列操作(int myQueuePop(MyQueue* obj)) 

 1.3.5.取队头操作(int myQueuePeek(MyQueue* obj))

 1.3.6.销毁队列的操作(void myQueueFree(MyQueue* obj)) 

1.4.代码展示

2.总结 


正文:

1.用栈实现队列

  老规矩,小编先把习题链接发过来:232. 用栈实现队列 - 力扣(LeetCode)

1.1.题干的解读

  可能很多读者朋友看到这个题的时候和小编当时想的一样,这个题是不是和用队列实现栈一样的思路来写呢?就是两个栈之间进行来回倒数据来实现,这个题的确也是按照类似的思路来实现的,不过此时小编还得再说一下栈和队列的各自的特点,栈是后进先出,队列是先进先出,所以队列是第一个进去的元素第一个出去,而栈反而是第一个进去的元素最后一个除出去,所以小编当时也是想了很久也没想明白这个题是如何来写的,因为倒数据似乎也是有一点麻烦的,于是乎小编在听完老师的讲解以后,便了解了这个题其中一个解法,下面小编将会讲述这个题目的大致思路:

 

1.2.题目的解题思路

  解决这个题目的思路类似倒数据,但是此时与上个题不一样的是,这里两个栈是分工明确的,我们可以让其中一个栈作为储存元素的,一个栈是用来进行出队列,取队头元素的;我们在使用队列实现栈的时候,两个队列是不确定的,有时候一个空一个不空,有时候一个不空另一个空,这么做是为了考虑各自的结构,栈是半封闭式,所以当我们想要删除队头元素的时候,我们仅需把那个储存数据的栈里面的数据通过提供栈顶元素之后出栈的方式,循环放入到另一个栈中,此时我们就可以发现第二个栈的元素和原来第一个栈的元素是倒置的,此时我们直接让第二个栈的元素出栈,这么做就可以实现出队列操作,因为出队列出的就是第一个,而我们将第一个栈的元素放入第二个栈以后,此时第一个栈的栈底元素就是第二个栈的栈顶元素,即进入栈的第一个因素,所以此时我们就可以实现出栈操作,而这也是小编为什么会讲两个栈的功能固定住,此时我们就实现了出队列操作,此时我们在现简单说一下队列每个功能的实现,对于入队列操作,我们直接把元素放入第一个栈就好;对于出队列操作,首先需要检测一下第二个栈是否有元素,如果有元素直接出栈就好,没有的话上面也说了,把第一个栈的元素循环放入第二个栈然后出栈;对于取栈顶元素,此时就和出队列是类似的,只不过我们直接返回第二个栈的栈顶元素就好了;至于初始化和销毁小编会在等会教写代码的时候说的,此时我们已经完成了队列的所有功能,可能很多读者朋友和我一样,光知道思路,但是代码不会写,下面小编将会讲述队列的功能如何用代码实现~

1.3.队列的功能实现

  再讲解功能之前,我们首先需要写出这个队列的结构体,其实这个在小编在上面写解题思路就有体现,我们需要准备两个栈,分别是用来存储数据和消除数据的,其代码如下:

typedef struct {ST q1;  //存放数据的ST q2;  //进行出队列或者取队头操作的
} MyQueue;
 1.3.1.队列的初始化(MyQueue* myQueueCreate()) 

  我们在写队列的时候肯定有初始化操作,首先我们需要先注意它的返回值,它的返回值是结构体指针,旨在说明我们需要创建一个队列指针,此时就要涉及动态内存的开辟了,我们需要开辟一个大小为结构体类型的变量的指针,在我们创建好以后,我们就要对里面的内容进行初始化,这时候我们仅需调用它们各自的初始化函数就好了,此时我们已经完成了初始化操作,我们直接返回这个指针即可,代码如下所示:

MyQueue* myQueueCreate() {MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));STInit(&pq -> q1);STInit(&pq -> q2);return pq;
}
 1.3.2.入队列操作(void myQueuePush(MyQueue* obj, int x) 

  入队列操作其实是很简单就可以实现的,此时我们讲我们想要的数据直接放入第一个栈就好,我们仅需调用一下入栈操作,把元素放入第一个栈即可,此时我们就实现了入队列操作,代码如下所示:

void myQueuePush(MyQueue* obj, int x) {STPush(&obj -> q1,x);
}
 1.3.3.判断队列是否为空(myQueueEmpty(MyQueue* obj)) 

  我们在进行出队列操作之前,我们需要去判断队列是否为空或者取队头数据的时候,如果为空的话我们就不可以再去进行出队列操作了,所以我们需要一个函数判断队列是否为空,此时队列为空的条件就是两个栈均为空,可能很多读者朋友要说,如果第二个栈就是空的,我们直接返回空不就好了,那样就大错特错了,还记着小编在上面的习题思路说过吗,对于出队列操作,我们首先需要判断第二个栈是否为空,如果第二个栈为空的话,我们直接把第一个栈的数据导入到第二个栈中,然后在出栈,所以第二个栈为空队列不一定就是空的,但如果第一个和第二个都是空的,那队列指定就是空的了,因为此时第一个栈就没元素倒入到第二个栈,第二个栈自然就无法实现出栈操作了,以上就是队列是否为空的实现,下面给予代码:

bool myQueueEmpty(MyQueue* obj) {return panduan(&obj -> q1) && panduan(&obj -> q2);
}
 1.3.4.出队列操作(int myQueuePop(MyQueue* obj)) 

  这个操作便是所有功能实现最为复杂的部分了,不过小编会将它简单化的教给大家,首先我们需要先判断队列是否为空的,之后我们需要先判断第二个栈是否为空,此时我们可以直接调用判断栈是否为空的函数来检查此时第二个栈是不是空的,如果不为空,我们先保存栈顶数据,然后进行出栈操作,返回栈顶元素就好了;如果为空,此时我们需要进行倒数据,我们需要把第一个栈的数据通过循环的方式倒入到第二个栈,然后在进行不为空情况的操作,此时循环的条件就是栈中元素的个数,当栈中的元素个数为0时,此时我们就实现了数据的倒入,之后我们在进行保存栈顶的元素,然后出栈操作,返回栈顶元素即可,以上就是此函数功能的实现,可能很多读者朋友还是不明白其中原理,小编通过图文进行解释,此时我们栈里面依次放入1,2,3,如下图所示:

  下面展示代码:

int myQueuePop(MyQueue* obj) {assert(!myQueueEmpty(obj));int size = STSize(&obj -> q1);if(STSize(&obj -> q2)){int b = STTop(&obj -> q2);STPop(&obj -> q2);return b;}//如果q2里面是空的,那么就执行下面操作while(size){int front = STTop(&obj -> q1);STPush(&obj -> q2,front);STPop(&obj -> q1);size--;}int c = STTop(&obj -> q2);STPop(&obj -> q2);return c;
}
 1.3.5.取队头操作(int myQueuePeek(MyQueue* obj))

  取队头操作其实是最简单的操作,当然是我建立在写完了出队列操作才说的,其实仔细看一看我们在写出队列操作的时候就已经展现出了取队头的操作,所以此时我们仅需把上面的代码复制下来,在把出队列操作删掉就好了,这便是这个操作的实现,是不是很简单,下面给出代码:

int myQueuePeek(MyQueue* obj) {assert(!myQueueEmpty(obj));int size = STSize(&obj -> q1);if(STSize(&obj -> q2)){int b = STTop(&obj -> q2);return b;}//如果q2里面是空的,那么就执行下面操作while(size){int front = STTop(&obj -> q1);STPush(&obj -> q2,front);STPop(&obj -> q1);size--;}int c = STTop(&obj -> q2);return c;
}
 1.3.6.销毁队列的操作(void myQueueFree(MyQueue* obj)) 

  销毁队列操作其实就是和上一篇写过的销毁栈操作是类似的,此时我们需要先把结构体里面的开辟出来的空间给释放掉,此时我们需要调用它们各自的销毁函数就好,操作结束后,由于此时的队列结构体也是开辟出来的,我们也需要释放掉,然后把它指向空就好,养成良好的习惯,减少野指针,这便是销毁操作的实现,下面给出代码:

void myQueueFree(MyQueue* obj) {STDestroy(&obj -> q1);STDestroy(&obj -> q2);free(obj);obj = NULL;
}

  以上便就是此队列所有结构函数的实现,现在肯定有很多读者朋友想要知道完整的代码怎么去写,下面小编就给出完整的代码:

1.4.代码展示

typedef int STDataType;
typedef struct Strak {STDataType* arr;   //存放的数据int caoticity;  //总空间大小int top;
}ST;void STInit(ST* ps)
{ps->arr = NULL;ps->caoticity = ps->top = 0;
}void STDestroy(ST* ps)
{if (ps->arr){free(ps -> arr);}ps->arr = NULL;ps->caoticity = ps->top = 0;
}void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->caoticity == ps->top){int newcaseasd = ps->caoticity == 0 ? 4 : 2 * ps->caoticity;STDataType* arr1 = (STDataType*)realloc(ps->arr, sizeof(STDataType) * newcaseasd);assert(arr1);ps->caoticity = newcaseasd;ps->arr = arr1;}//空间满了就进行扩容操作ps->arr[ps->top++] = x;
}bool panduan(ST * ps)
{assert(ps);return ps->top == 0;
}
void STPop(ST* ps)
{assert(ps);assert(!panduan(ps));ps->top--;
}STDataType STTop(ST* ps)
{assert(ps);assert(!panduan(ps));return ps->arr[ps -> top - 1];
}int STSize(ST* ps)
{return ps->top;
}typedef struct {ST q1;  //存放数据的ST q2;  //进行出队列或者取队头操作的
} MyQueue;MyQueue* myQueueCreate() {MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));STInit(&pq -> q1);STInit(&pq -> q2);return pq;
}bool myQueueEmpty(MyQueue* obj) {return panduan(&obj -> q1) && panduan(&obj -> q2);
}void myQueuePush(MyQueue* obj, int x) {STPush(&obj -> q1,x);
}int myQueuePop(MyQueue* obj) {assert(!myQueueEmpty(obj));int size = STSize(&obj -> q1);if(STSize(&obj -> q2)){int b = STTop(&obj -> q2);STPop(&obj -> q2);return b;}//如果q2里面是空的,那么就执行下面操作while(size){int front = STTop(&obj -> q1);STPush(&obj -> q2,front);STPop(&obj -> q1);size--;}int c = STTop(&obj -> q2);STPop(&obj -> q2);return c;
}int myQueuePeek(MyQueue* obj) {assert(!myQueueEmpty(obj));int size = STSize(&obj -> q1);if(STSize(&obj -> q2)){int b = STTop(&obj -> q2);return b;}//如果q2里面是空的,那么就执行下面操作while(size){int front = STTop(&obj -> q1);STPush(&obj -> q2,front);STPop(&obj -> q1);size--;}int c = STTop(&obj -> q2);return c;
}void myQueueFree(MyQueue* obj) {STDestroy(&obj -> q1);STDestroy(&obj -> q2);free(obj);obj = NULL;
}

2.总结 

  以上便是此题目的讲解,这个题目也是非常重要的,各位读者朋友一定要好好的去理解这个题目的做法,可能后期小编写的C嘎嘎文章会再次涉及到这个知识,如果文章有错误,请各位在评论区指出,小编一定会及时的去回复和更正,那么,我们下一篇博客见啦!

这篇关于栈和队列的习题详解(3):用栈实现队列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1141732

相关文章

MySQL 8 中的一个强大功能 JSON_TABLE示例详解

《MySQL8中的一个强大功能JSON_TABLE示例详解》JSON_TABLE是MySQL8中引入的一个强大功能,它允许用户将JSON数据转换为关系表格式,从而可以更方便地在SQL查询中处理J... 目录基本语法示例示例查询解释应用场景不适用场景1. ‌jsON 数据结构过于复杂或动态变化‌2. ‌性能要

Python实现终端清屏的几种方式详解

《Python实现终端清屏的几种方式详解》在使用Python进行终端交互式编程时,我们经常需要清空当前终端屏幕的内容,本文为大家整理了几种常见的实现方法,有需要的小伙伴可以参考下... 目录方法一:使用 `os` 模块调用系统命令方法二:使用 `subprocess` 模块执行命令方法三:打印多个换行符模拟

SpringBoot+EasyPOI轻松实现Excel和Word导出PDF

《SpringBoot+EasyPOI轻松实现Excel和Word导出PDF》在企业级开发中,将Excel和Word文档导出为PDF是常见需求,本文将结合​​EasyPOI和​​Aspose系列工具实... 目录一、环境准备与依赖配置1.1 方案选型1.2 依赖配置(商业库方案)二、Excel 导出 PDF

Python实现MQTT通信的示例代码

《Python实现MQTT通信的示例代码》本文主要介绍了Python实现MQTT通信的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 安装paho-mqtt库‌2. 搭建MQTT代理服务器(Broker)‌‌3. pytho

MySQL字符串常用函数详解

《MySQL字符串常用函数详解》本文给大家介绍MySQL字符串常用函数,本文结合实例代码给大家介绍的非常详细,对大家学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql字符串常用函数一、获取二、大小写转换三、拼接四、截取五、比较、反转、替换六、去空白、填充MySQL字符串常用函数一、

Java中Arrays类和Collections类常用方法示例详解

《Java中Arrays类和Collections类常用方法示例详解》本文总结了Java中Arrays和Collections类的常用方法,涵盖数组填充、排序、搜索、复制、列表转换等操作,帮助开发者高... 目录Arrays.fill()相关用法Arrays.toString()Arrays.sort()A

使用zip4j实现Java中的ZIP文件加密压缩的操作方法

《使用zip4j实现Java中的ZIP文件加密压缩的操作方法》本文介绍如何通过Maven集成zip4j1.3.2库创建带密码保护的ZIP文件,涵盖依赖配置、代码示例及加密原理,确保数据安全性,感兴趣的... 目录1. zip4j库介绍和版本1.1 zip4j库概述1.2 zip4j的版本演变1.3 zip4

Python 字典 (Dictionary)使用详解

《Python字典(Dictionary)使用详解》字典是python中最重要,最常用的数据结构之一,它提供了高效的键值对存储和查找能力,:本文主要介绍Python字典(Dictionary)... 目录字典1.基本特性2.创建字典3.访问元素4.修改字典5.删除元素6.字典遍历7.字典的高级特性默认字典

MySQL 主从复制部署及验证(示例详解)

《MySQL主从复制部署及验证(示例详解)》本文介绍MySQL主从复制部署步骤及学校管理数据库创建脚本,包含表结构设计、示例数据插入和查询语句,用于验证主从同步功能,感兴趣的朋友一起看看吧... 目录mysql 主从复制部署指南部署步骤1.环境准备2. 主服务器配置3. 创建复制用户4. 获取主服务器状态5

python生成随机唯一id的几种实现方法

《python生成随机唯一id的几种实现方法》在Python中生成随机唯一ID有多种方法,根据不同的需求场景可以选择最适合的方案,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习... 目录方法 1:使用 UUID 模块(推荐)方法 2:使用 Secrets 模块(安全敏感场景)方法