数据结构刷题训练:用栈实现队列(力扣OJ)

这篇具有很好参考价值的文章主要介绍了数据结构刷题训练:用栈实现队列(力扣OJ)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

前言

1. 题目:用栈实现队列

2. 思路

3. 分析

 3.1 定义 “ 队列 ”

 3.2 创建队列

3.3 入队

 3.4 队头数据

 3.5 出队

 3.6 判空和销毁

4.题解

总结


前言

        栈和队列是数据结构中的两个重要概念,它们在算法和程序设计中都有着广泛的应用。本文将带你深入了解如何使用栈来模拟实现队列,让你在解决问题时更加灵活和创新,便于大家更深入的理解栈和队列。


1. 题目:用栈实现队列

 题目描述:数据结构刷题训练:用栈实现队列(力扣OJ),数据结构,leetcode,算法,链表,c语言

 题目链接:

用栈实现队列https://leetcode.cn/problems/implement-queue-using-stacks/description/

2. 思路

         这道题目的解题思路于队列实现栈有很大的相似点。这道题也是给了两个栈,要求使用两个栈来实现队列。这里我们可以使用两边倒的方式来模拟实现队列。

        假设入栈:1、2、3、4那么出栈的顺序就是4、3、2、1,如果我们按照出栈的顺序再入栈到另一个栈中(空栈),再次出栈就可以达到队列出队的效果(1、2、3、4)

3. 分析

        根据上述的思路我们就可以利用两个栈模拟实现队列。思路的大概过程:

数据结构刷题训练:用栈实现队列(力扣OJ),数据结构,leetcode,算法,链表,c语言

         那么我们来考虑一下特殊的情况,如果我们入队了1、2、3、4,出队了1和2,然后再入队5和6,这时候我们考虑一下是否还需要倒一次(将剩下的3和4入栈到原栈中,然后入栈5和6,再将3、4、5、6依次出栈,入栈到另外一个栈中)?

        这里其实是不需要在倒一次,入队1、2、3、4。出队1和2,然后再入队5和6,然后再出队,出队的顺序是:1、2、3、4、5、6。我们可以将5和6入栈到原栈中,然后将3和4继续出栈,当一个栈为空时再入栈原栈中的数据。过程如下:

数据结构刷题训练:用栈实现队列(力扣OJ),数据结构,leetcode,算法,链表,c语言

         好的过程分析完之后,我们来对每个接口进行实现。题目中依然是没有现成的栈,所以我们依然需要 “ 造轮子 ” 前边我们已经实现的栈可以复制过来使用。

 3.1 定义 “ 队列 ”

         由于我们再模拟队列时需要用到两个栈,但调用函数时传两个栈又太麻烦,这里我们就使用结构体来定义两个栈(MyQueue),这样传参时就可以直接传结构体(MyQueue)指针就可以了。

typedef struct {
    Stack pushst;
    Stack popst;
} MyQueue;

 3.2 创建队列

         创建队列就非常简单了,我们只需要调用前边实现的InItStack函数将两个栈进行初始化就可以了:

MyQueue* myQueueCreate() {
    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
    InItStack(&obj->pushst);
    InItStack(&obj->popst);

    return obj;
}

         可能对结构体不熟练的同学会有疑惑:

问题一:

        为什么要malloc一个空间?这里注意:前边我们仅仅只是定义了一个模拟实现的队列,定义的是类型,并没有创建结构体变量,这里malloc也仅仅只是创建一个结构体变量。

 问题二:

        那为什么不直接MyQueue obj;这样定义?这是在函数内部,如果这样创建结构体变量它是创建在栈区,一旦出了函数1就会被销毁,为了后续的传参,所以最好使用malloc在堆区开辟空间。

问题三:

        初始化两个栈时需要取地址,那我们可不可以在定义时直接定义成指针类型例如:

Stack* pushst;
Stack* popst;

         这当然可以,但是如果按照这样的写法,那么在创建 “队列” 时就需要malloc给两个栈开辟空间(在调用的初始化函数中并没有开辟空间给栈)。如果是这样定义:

typedef struct {
    Stack pushst;
    Stack popst;
} MyQueue;

 那么在malloc,obj时就已经将两个栈的空间开辟好了。这样也更简单便捷。

3.3 入队

         入队就很简单了,直接将数据入栈到pushst中。

void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->pushst,x);
}

 3.4 队头数据

         这里为什么先写队头数据呢?那是因为出队时不仅需要将队头移除,还需要返回被移除队头的数据。所以这里我们先实现队头数据的接口。

        想要得到队头数据,那就需要将pushst中的元素按照出栈顺序入栈到popst中,然后返回popst这个栈的栈顶元素即可,过程如下:

数据结构刷题训练:用栈实现队列(力扣OJ),数据结构,leetcode,算法,链表,c语言

 

int myQueuePeek(MyQueue* obj) {
    if(IsEmpty(&obj->popst))
    {
        while(!IsEmpty(&obj->pushst))
        {
            StackPush(&obj->popst,TopData(&obj->pushst));
            StackPop(&obj->pushst);
        }
    }
    return TopData(&obj->popst);
}

         这里注意:入栈到popst中的条件是popst为空,这也与上述的分析对应,popst栈为空时才可以继续将pushst中入队元素倒到popst中。

 3.5 出队

        有了队头数据的接口,出队接口的实现就非常简单了,在出队前保存一下队头数据(popst栈顶数据),然后将popst中的栈顶元素出栈,最后返回front即可

int myQueuePop(MyQueue* obj) {
    int front=myQueuePeek(obj);
    StackPop(&obj->popst);

    return front;
}

 3.6 判空和销毁

         判空和销毁的接口也非常简单,当两个栈都为空时就表明队列为空,代码如下:

bool myQueueEmpty(MyQueue* obj) {
    return (IsEmpty(&obj->pushst)&&IsEmpty(&obj->popst));
}

         接下来是销毁,销毁队列前我们需要先将两个栈销毁,最后销毁obj。代码如下:

void myQueueFree(MyQueue* obj) {
    DestoryStack(&obj->popst);
    DestoryStack(&obj->pushst);
    free(obj);
}

4.题解

整体代码如下:

typedef int Datatype;
typedef struct Stack
{
	Datatype* a;
	int top;
	int capacity;
}Stack;

void InItStack(Stack* ps);

void DestoryStack(Stack* ps);

void StackPush(Stack* ps, Datatype x);

void StackPop(Stack* ps);

int Stacksize(Stack* ps);

Datatype TopData(Stack* ps);

bool IsEmpty(Stack* ps);


void InItStack(Stack* ps)
{
	assert(ps);
	ps->top = 0;
	ps->a = NULL;
	ps->capacity = 0;
}

void DestoryStack(Stack* ps)
{
	assert(ps);
	ps->top = ps->capacity = 0;
	free(ps->a);
	ps->a = NULL;
}
void StackPush(Stack* ps, Datatype x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = (ps->capacity == 0 ? 4 : ps->capacity * 2);
		Datatype* tmp = (Datatype*)realloc(ps->a, sizeof(Datatype) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}
int Stacksize(Stack* ps)
{
	assert(ps);
	return ps->top;
}
Datatype TopData(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);

	return ps->a[ps->top - 1];
}
bool IsEmpty(Stack* ps)
{
	assert(ps);
	return (ps->top == 0);
}


typedef struct {
    Stack pushst;
    Stack popst;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
    InItStack(&obj->pushst);
    InItStack(&obj->popst);

    return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->pushst,x);
}


int myQueuePeek(MyQueue* obj) {
    if(IsEmpty(&obj->popst))
    {
        while(!IsEmpty(&obj->pushst))
        {
            StackPush(&obj->popst,TopData(&obj->pushst));
            StackPop(&obj->pushst);
        }
    }
    return TopData(&obj->popst);
}

int myQueuePop(MyQueue* obj) {
    int front=myQueuePeek(obj);
    StackPop(&obj->popst);

    return front;
}

bool myQueueEmpty(MyQueue* obj) {
    return (IsEmpty(&obj->pushst)&&IsEmpty(&obj->popst));
}

void myQueueFree(MyQueue* obj) {
    DestoryStack(&obj->popst);
    DestoryStack(&obj->pushst);
    free(obj);
}

 

总结

        使用栈模拟实现队列,让我们在实践中深入思考了数据结构的本质和应用,为我们的编程思维和算法设计能力提供了挑战和提升。希望本期内容对你有些许帮助,最后,感谢阅读!文章来源地址https://www.toymoban.com/news/detail-643520.html

到了这里,关于数据结构刷题训练:用栈实现队列(力扣OJ)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】7、队列(Queue)的实现【用栈实现队列】

    ☘️ 队列 (Queue)是一种特殊的 线性表 , 只能在头尾两端进行操作 🎁 队尾(rear):只能从 队尾添加 元素,一般叫做 enQueue , 入队 🎁 队头(front):只能从 队头移除 元素,一般叫做 deQueue , 出队 🎁 先进先出 的原则, F irst I n F irst O ut, FIFO ☘️ 队列内部的实现可

    2024年02月12日
    浏览(43)
  • 【LeetCode】数据结构题解(12)[用栈实现队列]

    所属专栏:玩转数据结构题型❤️ 🚀 博主首页:初阳785❤️ 🚀 代码托管:chuyang785❤️ 🚀 感谢大家的支持,您的点赞和关注是对我最大的支持!!!❤️ 🚀 博主也会更加的努力,创作出更优质的博文!!❤️ 🚀 关注我,关注我,关注我,重要的事情说三遍!!!!!

    2024年02月13日
    浏览(42)
  • 《数据结构初阶》用队列实现栈&&用栈实现队列的细致解析

    目录 一、⏱️本章重点 二、⏱️队列实现栈 三、⏱️栈实现队列 四、⏱️解题思路总结 用两个队列实现栈 用两个栈实现队列 解题思路总结  我们有两个队列:  入栈数据1、 2、 3 可以将数据入队列至队列一或者队列二。 如何出栈?  但出栈要先出1,怎么办? 第一步 :

    2023年04月25日
    浏览(37)
  • 【算法与数据结构】232、LeetCode用栈实现队列

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :这道题要求我们用栈模拟队列(工作上一定没人这么搞)。程序当中,push函数很好解决,直接将元素push进输入栈当中。pop函数需要实现队列先进先出的操作,而栈是先进后出。只

    2024年02月12日
    浏览(43)
  • 【数据结构】队列篇| 超清晰图解和详解:循环队列模拟、用栈实现队列、用队列实现栈

    博主简介: 努力学习的22级计算机科学与技术本科生一枚🌸 博主主页: @是瑶瑶子啦 每日一言🌼: 每一个不曾起舞的日子,都是对生命的辜负。——尼采 🔗622. 设计循环队列 👧🏻 思路: 🍊数据结构: 使用数组为数据结构,且采用牺牲一个空间的方法来包装判空和判满的

    2024年02月11日
    浏览(39)
  • 数据结构刷题训练:设计循环队列(力扣OJ)

    目录 文章目录 前言 1. 题目:设计循环队列 2. 思路 3. 分析  3.1 定义循环队列  3.2 创建队列  3.3 判空和判满  3.4 入队  3.5 出队  3.6 取队头队尾数据  3.7 销毁队列  4. 题解 总结         当谈到队列数据结构时,很多人可能会想到普通的队列,即先进先出(FIFO)的数据结

    2024年02月13日
    浏览(47)
  • 速学数据结构 | 我不允许还有人不会用栈实现队列!

    🎬 鸽芷咕 :个人主页  🔥个人专栏 :《Linux深造日志》《C++干货基地》 ⛺️生活的理想,就是为了理想的生活!    🌈 hello! 各位铁铁们大家好啊,不知道大家对栈和队列的学习都学过了吧?那么用栈来实现队列你会做嘛?    ⛳️ 栈和队列我们前面说了都是一种特殊

    2024年02月02日
    浏览(41)
  • 第10天-代码随想录刷题训练-第五章 栈和队列- ● 理论基础 ● 232.用栈实现队列 ● 225. 用队列实现栈

    栈和队列对应的三个不同的STL版本,底层实现方式不一样, 为我们所知道的是 SGI STL 栈 栈提供 pop和push等接口, 不提供走访功能 也不提供迭代器, 不像map和set可以使用迭代器遍历,往往不被归类为容器,而是容器适配器 栈的内部实现结构可以使用 verctor、list 和 deque(默认)

    2024年02月04日
    浏览(41)
  • (※)力扣刷题-栈和队列-用栈实现队列

    使用栈实现队列的下列操作: push(x) – 将一个元素放入队列的尾部。 pop() – 从队列首部移除元素。 peek() – 返回队列首部的元素。 empty() – 返回队列是否为空。 说明: 你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。 你所使用

    2024年02月07日
    浏览(40)
  • 算法刷题Day 10 用栈实现队列+用队列实现栈

    之前做过,但现在还是卡壳了,想了有一会儿才想出来。 其实使用一个队列就可以实现栈

    2024年02月16日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包