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

这篇具有很好参考价值的文章主要介绍了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每日一题】

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

    2024年02月08日
    浏览(53)
  • 每日一题之用两个栈实现队列

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

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

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

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

    单调栈即栈内的元素是单调递减或者单调递增的,我们通过一个题目来理解。 单调栈模板题 题目描述 给出项数为 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日
    浏览(43)
  • leetcode每日一题44

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

    2024年01月19日
    浏览(45)
  • 每日一题:leetcode 57 插入区间

    给你一个  无重叠的  , 按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。 示例 1: 示例 2: 示例 3: 示例 4: 示例 5: 提示: 0 = intervals.length = 104 intervals[i].length == 2 0 = int

    2024年02月11日
    浏览(46)
  • 【每日一题】Leetcode - 283. 移动零

    Leetcode - 283. 移动零 从右向左遍历,遇到0,就将后面所有元素前移,同时更新长度,使其减1,因为移动n次,倒数n位就被0占据,后续操作可忽略 前面的操作,从右向左,每次遇到0移动都要跑半个数组,慢在整体前移; 换个思路,从左向右,记录首个0的位置,将后面的第一

    2024年02月11日
    浏览(45)
  • 【LeetCode每日一题】——566.重塑矩阵

    矩阵 简单 566.重塑矩阵 在 MATLAB 中,有一个非常有用的函数 reshape ,它可以将一个 m x n 矩阵重塑为另一个大小不同(r x c)的新矩阵,但保留其原始数据。 给你一个由二维数组 mat 表示的 m x n 矩阵,以及两个正整数 r 和 c ,分别表示想要的重构的矩阵的行数和列数。 重构后

    2024年02月14日
    浏览(47)
  • 【LeetCode每日一题】——575.分糖果

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

    2024年02月13日
    浏览(76)
  • 【LeetCode每日一题】——85.最大矩形

    矩阵 困难 85.最大矩形 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。 示例 1: 输入:matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“

    2024年02月13日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包