【数据结构】如何用栈实现队列?图文解析(LeetCode)

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

【数据结构】如何用栈实现队列?图文解析(LeetCode),数据结构,数据结构,c语言,leetcode

LeetCode链接:232. 用栈实现队列 - 力扣(LeetCode)

注:本文默认读者已掌握栈与队列的基本操作

可以看这篇文章熟悉知识点:【数据结构】栈与队列_字节连结的博客-CSDN博客

目录

做题思路

代码实现

1. MyQueue

2. myQueueCreate

3. myQueuePush

4. myQueuePeek

5. myQueuePop

6. myQueueEmpty

7. myQueueFree

全部代码


做题思路

简单来说,就是把一个栈(栈1)的数据捯入另一个栈(栈2),此时(栈2)出数据的顺序就和队列是一样的。

为了更方便理解,我会画图来演示一下具体思路。

我们需要两个栈来实现队列:

  • push栈:专门入数据的栈
  • pop栈:专门出数据的栈

如下图:

【数据结构】如何用栈实现队列?图文解析(LeetCode),数据结构,数据结构,c语言,leetcode

插入数据:直接在push栈内插入即可

push栈内插入数据:1、2、3、4、5

【数据结构】如何用栈实现队列?图文解析(LeetCode),数据结构,数据结构,c语言,leetcode

删除数据:需要把push栈内的数据捯入pop栈

  • 栈是后入先出的
  • 当push栈的数据捯入pop栈后,数据顺序会改变

如下图:

【数据结构】如何用栈实现队列?图文解析(LeetCode),数据结构,数据结构,c语言,leetcode

可以看到数据顺序逆转了

但是的这些操作跟队列有什么联系呢?

不妨来看看pop栈队列的对比:

【数据结构】如何用栈实现队列?图文解析(LeetCode),数据结构,数据结构,c语言,leetcode

由此可见:pop栈出数据的顺序是和队列一样的

到这里思路已经很清晰了:我们需要两个栈,一个专门用来push,一个专门用来pop,捯数据后,pop栈出数据的顺序就跟队列是一样的。

那么如何用代码(C)来实现这个思路呢?


代码实现

由于我们使用的是C语言,不能直接使用栈的操作

所以先把之前模拟实现过的栈复制过来:

//C语言模拟实现栈

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

//初始化栈
void STInit(ST* ps);
//销毁栈
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//检测栈是否为空,如果为空返回非零结果,如果不为空返回0
bool STEmpty(ST* ps);

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

void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void STPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

void STPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

STDataType STTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

复制完成之后就是本题的重点内容了。

本题要求:

实现 MyQueue 类:

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空,返回 true ;否则,返回 false

1. MyQueue

由于我们是用两个栈实现队列

所以这里需要定义两个栈

//两个栈模拟实现队列
typedef struct
{
    ST pushst;
    ST popst;
} MyQueue;

2. myQueueCreate

这个函数要求我们开辟空间,并初始化栈

//开辟空间并初始化
MyQueue* myQueueCreate()
{
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&obj->pushst);
    STInit(&obj->popst);
    return obj;
}

3. myQueuePush

直接把数据插入到push栈即可

//将元素X推到队列的末尾
void myQueuePush(MyQueue* obj, int x)
{
    STPush(&obj->pushst, x);
}

4. myQueuePeek

本函数要求返回队列开头的元素

  • 如果pop栈为空:要把push栈的数据捯入pop栈才能找到队列的首元素
  • 如果pop栈不为空:pop栈的栈顶元素就是队列的首元素

【数据结构】如何用栈实现队列?图文解析(LeetCode),数据结构,数据结构,c语言,leetcode

//返回队列开头的元素
int myQueuePeek(MyQueue* obj)
{
    if (STEmpty(&obj->popst))
    {
        //捯数据
        while (!STEmpty(&obj->pushst))
        {
            STPush(&obj->popst, STTop(&obj->pushst));
            STPop(&obj->pushst);
        }
    }
    return STTop(&obj->popst);
}

5. myQueuePop

  • 要求删除队头元素,也就是pop栈的栈顶元素,直接删除即可
  • 并且要返回队头元素的值,需要先定义一个临时变量来保存队头元素的值
  • 最后返回这个临时变量
//从队列的开头移除并返回元素
int myQueuePop(MyQueue* obj)
{
    int front = myQueuePeek(obj);
    STPop(&obj->popst);
    return front;
}

6. myQueueEmpty

判断队列是否为空,返回一个bool值(true/false)

如果push栈pop栈都为空,则说明队列为空

//如果队列为空,返回true;否则,返回false
bool myQueueEmpty(MyQueue* obj)
{
    return STEmpty(&obj->popst) && STEmpty(&obj->pushst);
}

7. myQueueFree

销毁队列

  • 销毁push栈pop栈
  • 释放动态开辟的空间
//销毁队列
void myQueueFree(MyQueue* obj)
{
    STDestroy(&obj->popst);
    STDestroy(&obj->pushst);
    free(obj);
}

到这里全部函数已经实现完毕,提交代码:

【数据结构】如何用栈实现队列?图文解析(LeetCode),数据结构,数据结构,c语言,leetcode

成功通过

下面我会把本题的全部代码整合在一起发出来


全部代码

//C语言模拟实现栈

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

//初始化栈
void STInit(ST* ps);
//销毁栈
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//检测栈是否为空,如果为空返回非零结果,如果不为空返回0
bool STEmpty(ST* ps);

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

void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void STPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

void STPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

STDataType STTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

//=======================================================================

//两个栈模拟实现队列
typedef struct
{
    ST pushst;
    ST popst;
} MyQueue;

//开辟空间并初始化
MyQueue* myQueueCreate()
{
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&obj->pushst);
    STInit(&obj->popst);
    return obj;
}

//将元素X推到队列的末尾
void myQueuePush(MyQueue* obj, int x)
{
    STPush(&obj->pushst, x);
}

//返回队列开头的元素
int myQueuePeek(MyQueue* obj)
{
    if (STEmpty(&obj->popst))
    {
        //捯数据
        while (!STEmpty(&obj->pushst))
        {
            STPush(&obj->popst, STTop(&obj->pushst));
            STPop(&obj->pushst);
        }
    }
    return STTop(&obj->popst);
}

//从队列的开头移除并返回元素
int myQueuePop(MyQueue* obj)
{
    int front = myQueuePeek(obj);
    STPop(&obj->popst);
    return front;
}

//如果队列为空,返回true;否则,返回false
bool myQueueEmpty(MyQueue* obj)
{
    return STEmpty(&obj->popst) && STEmpty(&obj->pushst);
}

//销毁队列
void myQueueFree(MyQueue* obj)
{
    STDestroy(&obj->popst);
    STDestroy(&obj->pushst);
    free(obj);
}

本文完文章来源地址https://www.toymoban.com/news/detail-677259.html

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

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

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

相关文章

  • 数据结构之栈与队列的实现与详细解析

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶 欢迎大家点赞,评论,收藏。 一起努力,一起奔赴大厂。 目录 1.前言 2.栈 2.1栈的概念与性质 2.2栈的实现 3.队列 3.1队列的概

    2024年02月05日
    浏览(45)
  • 数据结构-如何实现一个队列?逐步解析与代码示例(超详细)

    在计算机科学中,队列是一种非常基础且广泛使用的数据结构。它的工作原理类似于现实生活中的排队:先来的先服务(FIFO, First-In-First-Out)。在本文中,我们将深入探讨如何在C语言中使用链表实现一个队列,并解析相关的代码实现。 队列是一种遵循先进先出原则的线性数

    2024年02月03日
    浏览(46)
  • 数据结构:图文详解 队列 | 循环队列 的各种操作(出队,入队,获取队列元素,判断队列状态)

    目录 队列的概念 队列的数据结构 队列的实现 入队 出队 获取队头元素 获取队列长度 循环队列的概念 循环队列的数据结构 循环队列的实现 判断队列是否为空 判断队列是否已满 入队 出队 得到队头元素 得到队尾元素 队列(Queue)是一种数据结构,是一种 先进先出 (First-

    2024年02月04日
    浏览(38)
  • 【数据结构】移除链表元素-图文解析(单链表OJ题)

    LeetCode链接:203. 移除链表元素 - 力扣(LeetCode) 本文导航 💭做题思路 🎨画图更好理解: ✍️代码实现 🗂️分情况讨论: ❄️极端情况: 遍历链表,找到值为 val 的节点删除 这里需要两个指针  cur 用来遍历链表  prev 指向 cur 的前一个位置,方便删除一个节点后,链接前

    2024年02月14日
    浏览(35)
  • 数据结构---队列的实现

    前言 一、什么是队列? 二、 队列接口的实现 1. 队列结构的定义 2. 接口实现 总结 队列是一种特殊的线性表。 特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。 进行插入操作的端称为

    2024年02月02日
    浏览(36)
  • 数据结构队列的实现

    本章介绍数据结构队列的内容,我们会从队列的定义以及使用和OJ题来了解队列,话不多说,我们来实现吧 队列 1。队列的概念及结构 队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出 FIFO(First In First Out) 入队列:进行插入

    2024年02月11日
    浏览(62)
  • 数据结构—队列的实现

    前言:上次我们已经学习了数据结构中一个重要的线性表—栈,那么我们这一次就来学习另外一个重要的线性表—队列。 一、 队列的概念 二、 队列的实现: 1.队列的创建 三、 队列的操作 1.初始化队列 2.队尾入队列 3.队头出队列 4.获取队列头部元素 5.获取队列队尾元素 6.获

    2024年02月04日
    浏览(37)
  • 【数据结构】队列的实现

    队列是一种常用的数据结构,也是一种操作受限制的线性表,特点是只允许在表的头部进行删除操作,在表的尾部进行插入操作,队列具有先进先出FIFO(First In First Out)。 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头 我们实现可以用数组和链表

    2024年02月02日
    浏览(38)
  • 数据结构——队列的实现

    队列 ,又称为伫列(queue),计算机科学中的一种抽象资料类型,是先进先出(FIFO, First-In-First-Out)的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端(称为rear)进行插入操作,在前端(称为front)进行删除操作。 这段代码使用 typedef 定义了一个

    2024年02月10日
    浏览(35)
  • 数据结构/队列实现栈

    在学习数据结构的过程当中,我们会学到栈和队列,在本篇文章中,重点讲解的是队列实现栈,在上篇文章中已经简单介绍过栈和队列的使用说明,以及栈实现队列。(2条消息) 数据结构/栈实现队列_Y君的进化史的博客-CSDN博客 关于一个队列的简单使用方式:    关于一个栈的

    2024年02月02日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包