栈和队列OJ题:LeetCode--225.用队列实现栈

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

 朋友们、伙计们,我们又见面了,今天给大家带来的是LeetCode--225.用队列实现栈

数 据 结 构 专 栏:数据结构

个    人   主    页 :stackY、

LeetCode 专  栏 :LeetCode刷题训练营

LeetCode--225.用队列实现栈:https://leetcode.cn/problems/implement-stack-using-queues/

目录

1.题目介绍

2.实例演示

3.解题思路

3.1创建栈

3.2出栈操作

3.3压栈操作

3.4获取栈顶元素

3.5判断栈是否为空

3.6释放栈 

 4.完整代码


1.题目介绍

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。

实现 MyStack 类:

        1. void push(int x) 将元素 x 压入栈顶。
        2. int pop() 移除并返回栈顶元素。
        3. int top() 返回栈顶元素。
        4. boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。

注意:

        1. 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
        2. 你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。 

栈和队列OJ题:LeetCode--225.用队列实现栈

2.实例演示

栈和队列OJ题:LeetCode--225.用队列实现栈

3.解题思路

3.1创建栈

使用两个队列来实现栈的功能,首先我们得写出一个队列,队列的功能是先进先出,栈的功能是后进先出,在创建栈的时候需要有两个队列,然后为栈创建一块空间,并且将两个队列都进行初始化:

代码演示:

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() {
    //先为栈创建一块空间
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
    if(obj == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    //分别对两个队列进行初始化
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);
    return obj;
}

3.2出栈操作

栈和队列OJ题:LeetCode--225.用队列实现栈

 题目要求删除之后返回栈顶的元素。

栈的功能是先入后出,然而队列的功能是先入先出,那么我们该怎么操作呢?我们现在有两个队列,出栈是出的最后一个数据(第n个数据),我们可以先将一个队列的前n-1个数据依次插入到另外一个队列中(每插入一个然后再删除一个),这时原来的队列中就剩下最后一个数据,这时再将最后一个数据删除,这样子就达成了出栈时出最后一个数据的操作:我们在这里先假设第一个队列为空,第二个队列不为空,然后进行判断,如果不符合就交换,然后就是导数据的过程,然后就可以进行删除了:

栈和队列OJ题:LeetCode--225.用队列实现栈

 代码演示:

int myStackPop(MyStack* obj) {
    //假设q1为空
    //q2不为空
    Queue* pEmptyQ = &obj->q1;
    Queue* pNoEmptyQ = &obj->q2;
    //判断是否正确,不正确则交换
    if(!QueueEmpty(&obj->q1))
    {
        pEmptyQ = &obj->q2;
        pNoEmptyQ = &obj->q1;
    }
    //导数据
    //一直取到第Size-1个,这时就剩下的最后一个数据
    while(QueueSize(pNoEmptyQ) > 1)
    {
        //将不为空的队列中的数据插入到为空的队列
        QueuePush(pEmptyQ, QueueFront(pNoEmptyQ));
        QueuePop(pNoEmptyQ);
    }
    //删除最后一个数据
    int top = QueueFront(pNoEmptyQ);
    QueuePop(pNoEmptyQ);
    return top;
}

3.3压栈操作

由于我们是用两个队列来实现栈的功能,所以压栈操作也就是插入数据的操作需要将数据插入到队列中,那么怎么插入呢?对应前面的删除,我们需要将数据插入到不为空的队列中,那么第一次插入的时候两个队列都为空,这时随便插入即可:

代码演示:

void myStackPush(MyStack* obj, int x) {
    //判断是否为空
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1, x);
    }
    else
    {
        QueuePush(&obj->q2, x);
    }
}

3.4获取栈顶元素

这里的栈顶的元素就表示的是不为空的队列中的队尾的数据,所以只需要将不为空的队列的队尾的数据直接返回:

代码实现:

int myStackTop(MyStack* obj) {
    //q1不为空返回q1的队尾数据
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    //q2不为空返回q2的队尾数据
    else
    {
        return QueueBack(&obj->q2);
    }
}

3.5判断栈是否为空

判断栈是否为空就是判断两个队列是否为空:

代码演示:

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1)
        && QueueEmpty(&obj->q2);
}

3.6释放栈 

对栈的释放我们先要销毁实现栈的两个队列,然后再将栈空间释放:

代码实现:

void myStackFree(MyStack* obj) {
    //先销毁两个队列
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    //再释放栈空间
    free(obj);
}

 4.完整代码

//链式结构:表示队列
typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

//队列的结构
typedef struct Queue
{
	//头指针
	QNode* phead;
	//尾指针
	QNode* ptail;
	//队列中有效元素个数
	int size;
}Queue;


//初始化队列
void QueueInit(Queue* pq);

//销毁队列
void QueueDestroy(Queue* pq);

//队尾入队列
void QueuePush(Queue* pq, QDataType x);

//检测队列是否为空
bool QueueEmpty(Queue* pq);

//对头出队列
void QueuePop(Queue* pq);

//获取队头的元素
QDataType QueueFront(Queue* pq);

//获取队尾的元素
QDataType QueueBack(Queue* pq);

//获取队列有效元素的个数
int QueueSize(Queue* pq);

//初始化队列
void QueueInit(Queue* pq)
{
	assert(pq);

	pq->phead = NULL;
	pq->ptail= NULL;
	pq->size = 0;
}

//销毁队列
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

//队尾入队列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	
	//创建新的结点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->next = NULL;
	newnode->data = x;

	//第一次尾插
	if (pq->ptail == NULL)
	{
		assert(pq->phead == NULL);

		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	//有效元素++
	pq->size++;
}

//检测队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);

	//1.判断头、尾指针
	/*
	return pq->phead == NULL
		&& pq->ptail == NULL;
	*/

	//2.判断有效元素个数
	return pq->size == 0;
}

//队头出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	//判空
	assert(!QueueEmpty(pq));

	//一个结点
	if (pq->phead->next == NULL)
	{
		//直接释放
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	//多个结点
	else
	{
		//记录头的下一个
		QNode* Next = pq->phead->next;
		//释放
		free(pq->phead);
		//更新头结点
		pq->phead = Next;
	}
	
	pq->size--;
}

//获取队头的元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	//先判空
	assert(!QueueEmpty(pq));

	return pq->phead->data;
}

//获取队尾的元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	//先判空
	assert(!QueueEmpty(pq));

	return pq->ptail->data;
}

//获取队列有效元素的个数
int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}


typedef struct {
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() {
    //先为栈创建一块空间
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
    if(obj == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    //分别对两个队列进行初始化
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);
    return obj;
}

void myStackPush(MyStack* obj, int x) {
    //判断是否为空
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1, x);
    }
    else
    {
        QueuePush(&obj->q2, x);
    }
}

int myStackPop(MyStack* obj) {
    //假设q1为空
    //q2不为空
    Queue* pEmptyQ = &obj->q1;
    Queue* pNoEmptyQ = &obj->q2;
    //判断是否正确,不正确则交换
    if(!QueueEmpty(&obj->q1))
    {
        pEmptyQ = &obj->q2;
        pNoEmptyQ = &obj->q1;
    }
    //导数据
    //一直取到第Size-1个,这时就剩下的最后一个数据
    while(QueueSize(pNoEmptyQ) > 1)
    {
        //将不为空的队列中的数据插入到为空的队列
        QueuePush(pEmptyQ, QueueFront(pNoEmptyQ));
        QueuePop(pNoEmptyQ);
    }
    //删除最后一个数据
    int top = QueueFront(pNoEmptyQ);
    QueuePop(pNoEmptyQ);
    return top;
}

int myStackTop(MyStack* obj) {
    //q1不为空返回q1的队尾数据
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    //q2不为空返回q2的队尾数据
    else
    {
        return QueueBack(&obj->q2);
    }
}

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1)
        && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
    //先销毁两个队列
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    //再释放栈空间
    free(obj);
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/

今天的博客就分享到这里,喜欢的老铁留下你的三连,感谢感谢!我们下期再见!!文章来源地址https://www.toymoban.com/news/detail-461428.html

到了这里,关于栈和队列OJ题:LeetCode--225.用队列实现栈的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【LeetCode】225. 用队列实现栈

    思路 要使用一个队列来实现栈的功能。 具体来说,实现了以下几个方法: push(int x):将元素 x 入栈,即将元素 x 插入到队列的末尾。 pop():弹出栈顶元素,即将队列中 除了最后一个元素外 的其他元素 依次弹出并重新入队 ,然后返回最后一个元素。 top():获取栈顶元素,即

    2024年02月12日
    浏览(40)
  • 【用队列实现栈】【用栈实现队列】Leetcode 232 225

    ---------------🎈🎈题目链接 用队列实现栈🎈🎈------------------- ---------------🎈🎈题目链接 用栈实现队列🎈🎈-------------------

    2024年01月20日
    浏览(45)
  • Day10|LeetCode232.用栈实现队列、LeetCode 225. 用队列实现栈

    栈和队列理论基础: 队列是先进先出,栈是先进后出。如图所示: 栈和队列是STL(C++标准库)里面的两个数据结构。 栈是以底层容器完成其所有的工作,对外提供统一的接口,底层容器是可插拔的(也就是说我们可以控制使用哪种容器来实现栈的功能)。  栈的内部结构,

    2024年02月14日
    浏览(39)
  • 栈和队列OJ题思路分享之栈和队列互换(C语言实现)

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:刷题分享⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你刷更多C语言和数据结构的题!   🔝🔝 我们紧接上一章的刷题分享来把后面两个题给搞定,它们分别是: 1. 用队列实现栈: 力扣225题— 2. 用栈实现队列: 力扣232题.

    2024年02月03日
    浏览(39)
  • 栈和队列OJ题合集(包含循环队列的两种实现)

    目录 一:前言 二:有效的括号(括号匹配) 三:用队列实现栈 四:用栈实现队列 五:设计循环队列 对栈和队列的 基本性质和实现 有问题的可以看上一期  链接: http://t.csdn.cn/YQMBA​​​​  注意:本文用数据的大小来表示入栈入队的先后。 题目链接:https://leetcode.cn/problems/valid-paren

    2023年04月15日
    浏览(32)
  • 算法训练day9Leetcode232用栈实现队列225用队列实现栈

    https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html 见我的博客 https://blog.csdn.net/qq_36372352/article/details/135470438?spm=1001.2014.3001.5501 在push数据的时候,只要数据放进输入栈就好,但在pop的时候,操作就复杂一些, 输出栈如果为空,就把进栈数据全部导

    2024年01月24日
    浏览(64)
  • 栈和队列OJ题讲解

    💓博主个人主页:不是笨小孩👀 ⏩专栏分类:数据结构与算法👀 刷题专栏👀 C语言👀 🚚代码仓库:笨小孩的代码库👀 ⏩社区:不是笨小孩👀 🌹欢迎大家三连关注,一起学习,一起进步!!💓 队列是先进先出,而栈是先进后出,那我们怎么用两个队列来实现一个栈呢?

    2024年02月11日
    浏览(35)
  • 力扣在线OJ——栈和队列

    目录 🍁一、用两个队列实现栈 🌕(一)、题目(力扣链接:用队列实现栈 ) 🌕(二)、注意 🌕(三)、解答 ⭐️1.注意事项 ⭐️2.第一个接口——匿名结构体 ⭐️3.第二个接口——MyStack* myStackCreate() ⭐️4.第三个接口——void myStackPush(MyStack* obj, int x) ⭐️5.第四个接口

    2024年02月07日
    浏览(31)
  • 数据结构——栈和队列OJ题

    欢迎来到专项提升小课堂! 今天的题目稍稍有难度哦! 但是只要用心,是难不倒同学们的! 题目链接:OJ链接 提示: 1 = x = 9; 最多调用100 次 push、pop、top 和 empty ; 每次调用 pop 和 top 都保证栈不为空; 核心思想: 用队列模拟出栈的先入后出这一特性! 解题思路: 此题可

    2024年02月11日
    浏览(40)
  • 数据结构OJ题——栈和队列

    题目描述:请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty) void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty() 如果队列为空,返回 true ;否则,返回 fal

    2024年04月11日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包