1. Toy模板网首页
  2. > Toy博客

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

8月前 作者：认真学习的小雅兰. 分类：Toy博客 阅读(21) 违法举报

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

各位CSDN的uu们你们好呀，好久没有更新本专栏啦，甚是想念！！！今天，小雅兰的学习内容是用队列实现栈，下面，让我们进入Leetcode的世界吧！！！

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

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

这是小雅兰写过的栈和队列的文章，有兴趣的可以看看：

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

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

如图所示： 

这里相当于 栈中的Push1 2 3 4这四个数据

Leetcode每日一题——“用队列实现栈”可以使用两个队列进行导数据

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

如果还想再导出一个数据，那么还是同样的方法：

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

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

这里相当于栈中两次连续的Pop 

如果还想Push5 6这两个数据，那么：

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

然后再Pop，还是一样的，这次Pop一次，Pop出的就是6啦

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

好的，那么我们的基本思路就是这样的啦，下面，我们开始用代码实现它吧

首先，我们用的是C语言的话，还要自己实现一个队列，直接上代码：

typedef int QDataType;
// 链式结构：表示队列 
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QueueNode;
// 队列的结构 
typedef struct Queue
{
	QueueNode* phead;//头指针
	QueueNode* ptail;//尾指针
	int size;
}Queue;
// 初始化队列
void QueueInit(Queue* pq);

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

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

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

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

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

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

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

// 初始化队列
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

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

// 队尾入队列 
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	//是空队列的情况
	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);
	return pq->phead == NULL && pq->ptail == NULL;
}

// 队头出队列 
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//1.一个结点
	//2.多个结点
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		//相当于头删
		QueueNode* 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;
}

 剩余的功能就按照Leetcode上面给定的来：

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

这是一个匿名结构体，把这个匿名结构体typedef成MyStack

MyStack* myStackCreate() {
  MyStack obj;
  return &obj;
}

这个程序能不能这样写呢？

答案当然是否定的。

MyStack是一个局部结构体变量，出了作用域，它就销毁了

它是存在栈帧里面的，栈帧已经销毁了

所以这就是一个野指针

正确的写法：

MyStack* myStackCreate() {
    MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
    if(obj==NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    //这里->的优先级更高，取地址是对obj->q1和obj->q2取地址
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);
    return obj;
}

这里->的优先级更高，取地址是对obj->q1和obj->q2取地址

有的人可能会觉得在QueueInit里面取地址比较麻烦，那么，就衍生出了另外一种写法：

typedef struct {
    Queue* q1;
    Queue* q2;
} MyStack;
MyStack* myStackCreate() {
    MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
    if(obj==NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    //两种写法
    obj->q1=(Queue*)malloc(sizeof(Queue));
    obj->q2=(Queue*)malloc(sizeof(Queue));
    QueueInit(obj->q1);
    QueueInit(obj->q2);
    return obj;
}

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

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

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

删除数据：

由于不知道数据在q1还是在q2

int myStackPop(MyStack* obj) {
    //由于不知道数据是在q1还是在q2
    //q1为空 q2不为空
    //这是一种假设 假设有可能错误
    Queue* pEmptyQ=&obj->q1;
    Queue* pNonEmptyQ=&obj->q2;
    //q1不为空
    if(!QueueEmpty(&obj->q1))
    {
        //q2为空 q1不为空
        pEmptyQ=&obj->q2;
        pNonEmptyQ=&obj->q1;
    }
    //导数据
    while(QueueSize(pNonEmptyQ)>1)
    {
        //非空里面的数据插入空
        QueuePush(pEmptyQ,QueueFront(pNonEmptyQ));
        //每区一个数据就把它Pop一下
        QueuePop(pNonEmptyQ);
    }
    int top=QueueFront(pNonEmptyQ);
    QueuePop(pNonEmptyQ);
    return top;
}

 

int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    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);
}

 如果不Destroy，可能会内存泄漏

这个题目完整代码如下：

typedef int QDataType;
// 链式结构：表示队列 
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QueueNode;
// 队列的结构 
typedef struct Queue
{
	QueueNode* phead;//头指针
	QueueNode* ptail;//尾指针
	int size;
}Queue;
// 初始化队列
void QueueInit(Queue* pq);

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

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

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

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

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

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

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

// 初始化队列
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

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

// 队尾入队列 
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	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);
	return pq->phead == NULL && pq->ptail == NULL;
}

// 队头出队列 
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//1.一个结点
	//2.多个节点
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		//相当于头删
		QueueNode* 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;
    }
    //这里->的优先级更高，取地址是对obj->q1和obj->q2取地址
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);
    return obj;
}

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

int myStackPop(MyStack* obj) {
    //由于不知道数据是在q1还是在q2
    //q1为空 q2不为空
    //这是一种假设 假设有可能错误
    Queue* pEmptyQ=&obj->q1;
    Queue* pNonEmptyQ=&obj->q2;
    //q1不为空
    if(!QueueEmpty(&obj->q1))
    {
        //q2为空 q1不为空
        pEmptyQ=&obj->q2;
        pNonEmptyQ=&obj->q1;
    }
    //导数据
    while(QueueSize(pNonEmptyQ)>1)
    {
        //非空里面的数据插入空
        QueuePush(pEmptyQ,QueueFront(pNonEmptyQ));
        //每区一个数据就把它Pop一下
        QueuePop(pNonEmptyQ);
    }
    int top=QueueFront(pNonEmptyQ);
    QueuePop(pNonEmptyQ);
    return top;
}

int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    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);
}

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

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

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

 

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

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

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • (栈和队列) 1047. 删除字符串中的所有相邻重复项 ——【Leetcode每日一题】

    (栈和队列) 1047. 删除字符串中的所有相邻重复项 ——【Leetcode每日一题】

    难度：简单 给出由小写字母组成的字符串 S ， 重复项删除操作 会选择两个相邻且相同的字母，并删除它们。 在 S 上反复执行重复项删除操作，直到无法继续删除。 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。 示例： 输入 ：“abbaca” 输出 ：“ca” 解释

    2024年02月08日
    浏览(32)

  • 每日一题之用两个栈实现队列

    题目：用两个栈实现队列 用两个栈来实现一个队列，使用 n 个元素来完成 n 次在队列尾部插入整数( push )和 n 次在队列头部删除整数( pop )的功能。队列中的元素为 int 类型。保证操作合法，即保证pop操作时队列内已有元素。 参考牛客的解题思路： 将 stack1 倒序写入 stack2 ，然

    2024年02月13日
    浏览(28)
  • ( “树” 之 Trie) 208. 实现 Trie (前缀树) ——【Leetcode每日一题】

    ( “树” 之 Trie) 208. 实现 Trie (前缀树) ——【Leetcode每日一题】

    知识点回顾 ： Trie ，又称 前缀树 或 字典树 ，用于判断字符串是否存在或者是否具有某种字符串前缀。 难度：中等 Trie （发音类似 “ try ”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补

    2024年02月01日
    浏览(29)
  • 蓝桥杯每日一题----单调栈和单调队列

    蓝桥杯每日一题----单调栈和单调队列

    单调栈即栈内的元素是单调递减或者单调递增的，我们通过一个题目来理解。 单调栈模板题 题目描述 给出项数为 n 的整数数列 a 1 … a n a_1…a_n a 1 ​ … a n ​ 。 定义函数 f ( i ) f(i) f ( i ) 代表数列中第 i 个元素之后第一个大于 a i a_i a i ​ 的元素的下标，即 f ( i ) = m i n i

    2024年02月19日
    浏览(30)

  • leetcode每日一题44

    图论 dfs/bfs dfs代码框架 思路：本题要求找到被x围绕的陆地，所以边界的陆地O肯定不符合条件。那么我们只要从周边找到陆地O然后 通过 dfs或者bfs 将周边靠陆地且相邻的陆地O都变成A，然后再去重新遍历地图的时候，把剩下的O变成X，再把所有的A变成O。 确认递归函数，参数

    2024年01月19日
    浏览(35)
  • 【LeetCode】每日一题：移除元素

    【LeetCode】每日一题：移除元素

    目录  题目： 思想1：暴力解法 思想2：创建一个temp数组  思想3：双指针 👻内容专栏：《LeetCode刷题专栏》 🐨本文概括： 27.移除元素 🐼本文作者：花 碟 🐸发布时间：2023.4.15 https://leetcode.cn/problems/remove-element/   点击跳转到LeetCode平台OJ页面(27.移除元素）  👉 示例1： 解

    2023年04月19日
    浏览(41)
  • Leetcode每日一题——“移除元素”

    Leetcode每日一题——“移除元素”

    各位CSDN的uu们你们好呀，小雅兰又来啦，今天，小雅兰的内容是移除元素，下面，让我们进入Leetcode的世界吧   说明: 为什么返回数值是整数，但输出的答案是数组呢? 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。 你可以

    2023年04月23日
    浏览(45)
  • leetcode每日一题：62. 不同路径

    leetcode每日一题：62. 不同路径

    系列：动态规划 语言：java 难度：中等 题目来源：Leetcode62. 不同路径 开启动态规划章节了！！欢迎您在留言和我一起完成每日打卡，以后每天8点半前发布每日一题。 原题链接：Leetcode62. 不同路径 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）

    2023年04月22日
    浏览(36)
  • 【LeetCode每日一题】——575.分糖果

    【LeetCode每日一题】——575.分糖果

    哈希表 简单 575.分糖果 Alice 有 n 枚糖，其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长，所以前去拜访了一位医生。 医生建议 Alice 要少摄入糖分，只吃掉她所有糖的 n / 2 即可（n 是一个偶数）。Alice 非常喜欢这些糖，她想要在遵循医生建议的情况下，尽可

    2024年02月13日
    浏览(60)

  • 每日一题(LeetCode)----二分查找（一）

    给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: 示例 2: 示例 3: 提示: 1 = nums.length = 104 -104 = nums[i] = 104 nums 为 无重复元素 的 升序 排列数

    2024年02月08日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包