栈和队列的习题详解(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

相关文章

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片,默认是输出到项目文件夹中,可以自己选择其他的文件夹,选择需要拆分的行数和列数,可以通过

一文详解SpringBoot中控制器的动态注册与卸载

《一文详解SpringBoot中控制器的动态注册与卸载》在项目开发中,通过动态注册和卸载控制器功能,可以根据业务场景和项目需要实现功能的动态增加、删除,提高系统的灵活性和可扩展性,下面我们就来看看Sp... 目录项目结构1. 创建 Spring Boot 启动类2. 创建一个测试控制器3. 创建动态控制器注

Python中将嵌套列表扁平化的多种实现方法

《Python中将嵌套列表扁平化的多种实现方法》在Python编程中,我们常常会遇到需要将嵌套列表(即列表中包含列表)转换为一个一维的扁平列表的需求,本文将给大家介绍了多种实现这一目标的方法,需要的朋... 目录python中将嵌套列表扁平化的方法技术背景实现步骤1. 使用嵌套列表推导式2. 使用itert

C#读写文本文件的多种方式详解

《C#读写文本文件的多种方式详解》这篇文章主要为大家详细介绍了C#中各种常用的文件读写方式,包括文本文件,二进制文件、CSV文件、JSON文件等,有需要的小伙伴可以参考一下... 目录一、文本文件读写1. 使用 File 类的静态方法2. 使用 StreamReader 和 StreamWriter二、二进

Python使用pip工具实现包自动更新的多种方法

《Python使用pip工具实现包自动更新的多种方法》本文深入探讨了使用Python的pip工具实现包自动更新的各种方法和技术,我们将从基础概念开始,逐步介绍手动更新方法、自动化脚本编写、结合CI/C... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

在Linux中改变echo输出颜色的实现方法

《在Linux中改变echo输出颜色的实现方法》在Linux系统的命令行环境下,为了使输出信息更加清晰、突出,便于用户快速识别和区分不同类型的信息,常常需要改变echo命令的输出颜色,所以本文给大家介... 目python录在linux中改变echo输出颜色的方法技术背景实现步骤使用ANSI转义码使用tpu

Conda与Python venv虚拟环境的区别与使用方法详解

《Conda与Pythonvenv虚拟环境的区别与使用方法详解》随着Python社区的成长,虚拟环境的概念和技术也在不断发展,:本文主要介绍Conda与Pythonvenv虚拟环境的区别与使用... 目录前言一、Conda 与 python venv 的核心区别1. Conda 的特点2. Python v

Spring Boot中WebSocket常用使用方法详解

《SpringBoot中WebSocket常用使用方法详解》本文从WebSocket的基础概念出发,详细介绍了SpringBoot集成WebSocket的步骤,并重点讲解了常用的使用方法,包括简单消... 目录一、WebSocket基础概念1.1 什么是WebSocket1.2 WebSocket与HTTP

Python使用python-can实现合并BLF文件

《Python使用python-can实现合并BLF文件》python-can库是Python生态中专注于CAN总线通信与数据处理的强大工具,本文将使用python-can为BLF文件合并提供高效灵活... 目录一、python-can 库:CAN 数据处理的利器二、BLF 文件合并核心代码解析1. 基础合

java中反射Reflection的4个作用详解

《java中反射Reflection的4个作用详解》反射Reflection是Java等编程语言中的一个重要特性,它允许程序在运行时进行自我检查和对内部成员(如字段、方法、类等)的操作,本文将详细介绍... 目录作用1、在运行时判断任意一个对象所属的类作用2、在运行时构造任意一个类的对象作用3、在运行时判断