Leetcode每日一题——“用栈实现队列”

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

各位CSDN的uu们你们好呀,今天,小雅兰的内容是用栈实现队列,这和小雅兰的上一篇博客“用队列实现栈”好像有点点关系噢,事实上,也确实是这样的,下面,让我们进入Leetcode的世界吧!!!


Leetcode每日一题——“用队列实现栈”_认真学习的小雅兰.的博客-CSDN博客


Leetcode每日一题——“用栈实现队列” 

Leetcode每日一题——“用栈实现队列” 

Leetcode每日一题——“用栈实现队列” 

 感兴趣的可以看看小雅兰写的栈和队列的内容:

栈——“数据结构与算法”_认真学习的小雅兰.的博客-CSDN博客

队列——“数据结构与算法”_认真学习的小雅兰.的博客-CSDN博客


Leetcode每日一题——“用栈实现队列” 

然后导数据,也就是Pop一下:

Leetcode每日一题——“用栈实现队列” 

如果还要继续Pop的话,就不需要和之前那个题目“用队列实现栈”那样,再导数据啦

这次Pop就可以直接在第二个队列里面Pop 

如果要Push5 6的话,那又该怎么办呢?

我们不妨这样:直接写“死”,把一个队列设为专门出数据的,另一个队列设为专门入数据的

Leetcode每日一题——“用栈实现队列”

如果是要Push5 6,那么,就这样:

Leetcode每日一题——“用栈实现队列” 

如果还要再Pop三次呢?

只要知道这样一个原则:只要popst(第二个队列)不为空,就可以一直出数据,如果popst为空了,就导数据,导了之后再出!!!

Leetcode每日一题——“用栈实现队列”

那么,这个题目的思路就是这样子了,下面,我们开始写代码吧!!!


首先,我们用C语言,得手撕一个栈

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;//栈顶
	int capacity;//容量
}Stack;

// 初始化栈 
void StackInit(Stack* pst);

// 销毁栈 
void StackDestroy(Stack* pst);

// 入栈 
void StackPush(Stack* pst, STDataType x);

// 出栈 
void StackPop(Stack* pst);

// 获取栈顶元素 
STDataType StackTop(Stack* pst);

// 获取栈中有效元素个数 
int StackSize(Stack* pst);

// 检测栈是否为空 
bool StackEmpty(Stack* pst);

// 初始化栈 
void StackInit(Stack* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}

// 销毁栈 
void StackDestroy(Stack* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}

// 入栈 
void StackPush(Stack* pst, STDataType x)
{
	assert(pst);
	//扩容
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	pst->a[pst->top] = x;
	pst->top++;
}

// 检测栈是否为空
bool StackEmpty(Stack* pst)
{
	assert(pst);
	if (pst->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
	//return pst->top==0;
}

// 出栈 
void StackPop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));
	pst->top--;
}

// 获取栈顶元素 
STDataType StackTop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));
	return pst->a[pst->top - 1];
}

// 获取栈中有效元素个数 
int StackSize(Stack* pst)
{
	assert(pst);
	return pst->top;
}

 剩余的功能跟着Leetcode上走就可以了

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

这仍然是一个匿名结构体,利用typedef重命名为MyQueue,在这个结构体中,定义了两个结构体,一个是专门出数据的popst,一个是专门入数据的pushst

MyQueue* myQueueCreate() {
    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
    if(obj==NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    StackInit(&obj->pushst);
    StackInit(&obj->popst);
    return obj;
}
void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->pushst,x);
}

Leetcode每日一题——“用栈实现队列” 

peek有“窥视”的意思 

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

//导数据了之后取顶上的数据
int myQueuePeek(MyQueue* obj) {
    //popst为空才需要导数据
    if(StackEmpty(&obj->popst))
    {
        //pushst不为空
        while(!StackEmpty(&obj->pushst))
        {
            //把pushst(栈顶)的数据导给popst
            StackPush(&obj->popst,StackTop(&obj->pushst));
            //然后把pushst的数据删掉
            StackPop(&obj->pushst);
        }
    }
    //popst本身就不为空
    return StackTop(&obj->popst);
}
int myQueuePop(MyQueue* obj) {
    int front=myQueuePeek(obj);
    StackPop(&obj->popst);
    return front;
}
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->pushst)&&StackEmpty(&obj->popst);
}
void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->popst);
    StackDestroy(&obj->pushst);
    free(obj);
}

这个题目的完整代码如下:

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;//栈顶
	int capacity;//容量
}Stack;
// 初始化栈 
void StackInit(Stack* pst);
// 销毁栈 
void StackDestroy(Stack* pst);
// 入栈 
void StackPush(Stack* pst, STDataType x);
// 出栈 
void StackPop(Stack* pst);
// 获取栈顶元素 
STDataType StackTop(Stack* pst);
// 获取栈中有效元素个数 
int StackSize(Stack* pst);
// 检测栈是否为空 
bool StackEmpty(Stack* pst);
// 初始化栈 
void StackInit(Stack* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}
// 销毁栈 
void StackDestroy(Stack* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}
// 入栈 
void StackPush(Stack* pst, STDataType x)
{
	assert(pst);
	//扩容
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	pst->a[pst->top] = x;
	pst->top++;
}
// 检测栈是否为空
bool StackEmpty(Stack* pst)
{
	assert(pst);
	if (pst->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
	//return pst->top==0;
}
// 出栈 
void StackPop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));
	pst->top--;
}
// 获取栈顶元素 
STDataType StackTop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));
	return pst->a[pst->top - 1];
}
// 获取栈中有效元素个数 
int StackSize(Stack* pst)
{
	assert(pst);
	return pst->top;
}
typedef struct {
    Stack pushst;
    Stack popst;
} MyQueue;

MyQueue* myQueueCreate() {
    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
    if(obj==NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    StackInit(&obj->pushst);
    StackInit(&obj->popst);
    return obj;
}

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

int myQueuePop(MyQueue* obj) {
    int front=myQueuePeek(obj);
    StackPop(&obj->popst);
    return front;
}
//导数据了之后取顶上的数据
int myQueuePeek(MyQueue* obj) {
    //popst为空才需要导数据
    if(StackEmpty(&obj->popst))
    {
        //pushst不为空
        while(!StackEmpty(&obj->pushst))
        {
            //把pushst(栈顶)的数据导给popst
            StackPush(&obj->popst,StackTop(&obj->pushst));
            //然后把pushst的数据删掉
            StackPop(&obj->pushst);
        }
    }
    //popst本身就不为空
    return StackTop(&obj->popst);
}

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

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

/**

 * Your MyQueue struct will be instantiated and called as such:

 * MyQueue* obj = myQueueCreate();

 * myQueuePush(obj, x);

 * int param_2 = myQueuePop(obj);

 * int param_3 = myQueuePeek(obj);

 * bool param_4 = myQueueEmpty(obj);

 * myQueueFree(obj);

*/


好啦,小雅兰今天的用栈实现队列的内容就到这里啦,还要继续加油刷题噢!!!

Leetcode每日一题——“用栈实现队列” 

 

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

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

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

相关文章

  • 【用队列实现栈】【用栈实现队列】Leetcode 232 225

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

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

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

    2024年02月14日
    浏览(38)
  • 栈和队列OJ题:LeetCode--232.用栈实现队列

    朋友们、伙计们,我们又见面了,今天给大家带来的是LeetCode--232.用栈实现队列 数 据 结 构 专 栏:数据结构 个    人   主    页 :stackY、 LeetCode 专  栏 :LeetCode刷题训练营 LeetCode--232.用栈实现队列:https://leetcode.cn/problems/implement-queue-using-stacks/ 目录 1.题目介绍 2.实例演示

    2024年02月05日
    浏览(49)
  • 【创作赢红包】LeetCode:232. 用栈实现队列

    🍎道阻且长,行则将至。🍓 🌻算法,不如说它是一种思考方式🍀 算法专栏: 👉🏻123 题目描述 :请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty): 实现 MyQueue 类: void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列

    2023年04月12日
    浏览(41)
  • Leetcode的AC指南 —— 栈与队列:232.用栈实现队列

    摘要: **Leetcode的AC指南 —— 栈与队列:232.用栈实现队列 **。题目介绍:请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty): 实现 MyQueue 类: void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int

    2024年01月20日
    浏览(42)
  • LeetCode 232.用栈实现队列(详解) (๑•̌.•๑)

    创建两个栈,一个用于入数据,一个用于出数据。分别是pushST和popST; 1.如果是入数据就直接入进pushST 2.如果是出数据,先检查popST中有无数据,如果有数据,就直接出。如果没数据,就将pushST中的数据放进popST中,再从popST中出数据。 当pushST中的数据入到popST时,数据是顺序的

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

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

    2024年02月13日
    浏览(40)
  • 【算法与数据结构】232、LeetCode用栈实现队列

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

    2024年02月12日
    浏览(43)
  • LeetCode·每日一题·1851. 包含每个查询的最小区间·优先队列(小顶堆)

        离线查询:  输入的结果数组queries[]是无序的。如果我们按照输入的queries[]本身的顺序逐个查看,时间复杂度会比较高。 于是,我们将queries[]数组按照数值大小,由小到大逐个查询,这种方法称之为离线查询。 位运算:  离线查询的时候,queries[]可以按照数值大小逐个

    2024年02月16日
    浏览(49)
  • (栈和队列) 150. 逆波兰表达式求值 ——【Leetcode每日一题】

    难度:中等 给你一个字符串数组 tokens ,表示一个根据 逆波兰表示法 表示的算术表达式。 请你计算该表达式。返回一个表示表达式值的整数。 注意 : 有效的算符为 ‘ + ’、‘ - ’、‘ * ’ 和 ‘ / ’ 。 每个操作数(运算对象)都可以是一个整数或者另一个表达式。 两个

    2024年02月08日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包