【C语言实现：用队列模拟栈与用栈模拟队列（LeetCode 225 232）】

news/2024/12/14 6:43:15/

在这里插入图片描述

LeetCode刷题记录
  • 🌐 我的博客主页：iiiiiankor
  • 🎯 如果你觉得我的内容对你有帮助，不妨点个赞👍、留个评论✍，或者收藏⭐，让我们一起进步！
  • 📝 专栏系列：LeetCode 刷题日志
  • 🌱 文章内容来自我的学习与实践经验，如果你有任何想法或问题，欢迎随时在评论区交流讨论。让我们一起探索更多的可能！🚀

💚文章目录💚

  • ✨前言✨
  • ☢️注意☢️
  • 🚀LeetCode225.用队列实现栈
    • 一、🌟题目描述🌟
    • 二、🎨分析🎨
    • 三、💥题解💥
      • 栈"的结构定义
      • Push接口
      • Pop接口
      • 获取栈顶元素
      • 判断栈是否为空
      • 释放free
      • ✏️总代码✏️
  • 🚀LeetCode232.用栈实现队列
    • 一、🌟题目描述🌟
    • 二、🎨分析🎨
    • 三、💥题解💥
      • 模拟队列的结构
      • 初始化队列
      • Push
      • Pop
      • 获取队头元素
      • 判断是不是空
      • 释放
      • ✏️总代码✏️

✨前言✨

首先我们可以先复习一下相关性质：

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶
实现方法：1. 数组（顺序表） 2.链表
在这里插入图片描述

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
实现：1.链表（更优）2.数组（较差）

在这里插入图片描述

☢️注意☢️

C语言中并不想C++或者Java等高级语言那样，库中有封装好的栈和队列
所以我们用C做这些题的时候，都必须先把栈或者队列写出来，才能做题！
这也是用C刷题的很恶心的地方
但是 也能巩固我们的知识不是嘛？

🚀LeetCode225.用队列实现栈

链接：LeetCode225.用队列实现栈

一、🌟题目描述🌟

在这里插入图片描述

二、🎨分析🎨

我们知道，队列是先进先出，而栈是后进先出，那么怎么用队列实现栈呢？
我们通过画图来分析：

如果给你一个不为空的队列，我们叫他noempty：
在这里插入图片描述
这个队列是 按照 1 2 3 4 的顺序放入的数据
所以 如果是队列的话 那么出队列的顺序也是 1 2 3 4
但是如果想要实现栈，那么第一个出去的数据应该是4
我们怎么实现呢？
如果我们还有一个空的队列，我们叫他empty
我们把1 2 3 放到empty里面，那么noempty里就只剩下了 4，如图：
在这里插入图片描述
这样，noempty的队头就是4 我们直接对noempty进行pop
然后 队列的性质是先进先出，所以在empty中也是 原来的1 2 3顺序
empty出队列的顺序也是1 2 3
所以 我们只需要把empty中的元素再倒回noempty中
我们再观察noempty，是不是就完成了栈的后进先出的性质！！！
(因为 4 是最后进入的）
在这里插入图片描述
综上所述，其实empty就是用来倒数据的！
因此我们要时刻保证一个是空队列，另一个是非空队列
这道题目实际上就是利用一个空队列和队列的相关性质，来实现栈的 后进先出的！

三、💥题解💥

栈"的结构定义

这里的“栈” 是我们目标实现的那个栈

  • 结构需要包含两个队列

    注意： 此类型题目的结构比较复杂
    因为我们使用链表实现的栈，所以“栈”中包含的队列的结构中还有

  • 链表头节点

  • 链表尾节点

“栈”的结构

//这里是匿名结构体 因为有typedef 后面可以使用匿名结构体
typedef struct {//结构中包含两个队列Queue q1;Queue q2;
} MyStack;

队列的结构：

typedef struct Queue {size_t size;//利用一个变量去标识队列的大小QNode* head;//队列的头节点QNode* tail;//队列的尾节点
}Queue;

Push接口

由于我们需要保持一个队列为空，另一个队列不为空
对于push接口，我们只需要判断哪一个队列不为空
然后向该队列push数据就可以了

Pop接口

如果要pop数据，如1 2 3 4 5
模拟实现栈，所以要出栈，也就是删除栈顶
而栈顶就是队列的队尾
所以要删除5
只需要把前面一个个数据挪动到空队列
直接让5出队就可以了

注意这里题目让你返回pop掉的元素！

获取栈顶元素

显示栈顶元素
只需要找到不为空的队列就可以了
这里我们不需要考虑如果两个队列都为空了怎么办
只要完成他给的接口就可以了！
测试用例一定是正确合理的！ 不会出现空了还让你调用这个函数的情况
： 测试用例就是看你逻辑正不正确！

判断栈是否为空

因为我们的栈是用两个队列来实现的
所以 如果两个队列都为空，那么说明栈为空！

释放free

  1. 首先把结构中包含的两个队列释放掉
  2. 然后把该结构释放掉

✏️总代码✏️

// 用队列实现栈typedef int QDataType;
//定义队列节点的结构  
typedef struct QueueNode {struct QueueNode* next;QDataType val;//队列中的数据
}QNode;//利用封装一个结构
typedef struct Queue {size_t size;//利用一个变量去标识队列的大小QNode* head;//队列的头节点QNode* tail;//队列的尾节点
}Queue;//初始化
void QueueInit(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 QueueDestory(Queue* pq);//初始化
void QueueInit(Queue* pq)
{assert(pq);//头节点和尾节点都设置为空即可pq->head = pq->tail = NULL;pq->size = 0;}
//入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){printf("malloc fail!");exit(-1);}newnode->next = NULL;newnode->val = x;//如果队列为空if (pq->tail == NULL)//也可以使用head==NULL{pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;//更新尾部}pq->size++;
}
//出队列
void QueuePop(Queue* pq)
{assert(pq);//如果只有一个节点if (pq->head->next == NULL)//这里需要用head的next{free(pq->head);pq->head = pq->tail = NULL;pq->size--;//队列元素个数减一}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;pq->size--;}
}
//获取队头元素
QDataType QueueFront(Queue* pq)
{assert(pq);//如果队列为空 无法获取！assert(!QueueEmpty(pq));return pq->head->val;
}
//获取队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->val;
}
//获取队列中元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
//检测队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);//如果 head为空 返回真 否则返回假return pq->head == NULL;
}
//销毁队列
void QueueDestory(Queue* pq)
{assert(pq);//只需要逐个释放就可以了QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}/*****************************************/
/*  题解代码   */
typedef struct {//结构中包含两个队列Queue q1;Queue q2;
} MyStack;//初始化
MyStack* myStackCreate() {//首先需要开辟一个stackMyStack* obj = (MyStack*)malloc(sizeof(MyStack));//然后对开辟的Mystack中的q1和q2初始化QueueInit(&obj->q1);QueueInit(&obj->q2);//然后需要返回objreturn obj;
}void myStackPush(MyStack* obj, int x) {//如果q1不为空 那么就向q1里面插入数据if (!QueueEmpty(&obj->q1)){QueuePush(&obj->q1, x);}else//否则就向q2里面插入数据{QueuePush(&obj->q2, x);}
}int myStackPop(MyStack* obj) {//首先需要判断哪一个不为空//先假设q1为空 q2不为空Queue* empty = &obj->q1;Queue* noempty = &obj->q2;//如果假设错了 就改一下if (!QueueEmpty(&obj->q1)){empty = &obj->q2;noempty = &obj->q1;}//然后就把非空队列的数据导入到空队列 知道非空队列还有一个数据while (QueueSize(noempty) > 1){//把非空队列的队头 push到空队列QueuePush(empty, QueueFront(noempty));QueuePop(noempty);}//因为对于栈顶元素需要返回和删除//所以先把栈顶元素记录一下啊int top = QueueFront(noempty);QueuePop(noempty);return top;
}int myStackTop(MyStack* obj) {//既然是显示栈顶元素//那就需要找到非空队列//显示非空队列的队尾就可以了//如果队列q1不为空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) {//1. 释放Mystackj里面包含的q1 和 q2 （他们里面也有malloc的节点）//2. 释放 MystackQueueDestory(&obj->q1);QueueDestory(&obj->q2);free(obj);
}

🚀LeetCode232.用栈实现队列

链接：LeetCode232.用栈实现队列

一、🌟题目描述🌟

在这里插入图片描述

二、🎨分析🎨

思考：
这个题会不会和上一道题很类似？
我们知道 栈的性质是 后进先出，而队列的性质是先进先出
那么怎么让最先进去的最先出来呢？
画图分一下：
在这里插入图片描述

显然 最先入栈的是：1，那么如何让1 先出栈呢？
那么我们是不是可以这样？
把左边的栈的元素全部push到右边的空栈，因为栈是从栈顶出栈
所以 入右边的栈的顺序是4-3-2-1
变成了这样：
在这里插入图片描述
这时候，如果想溢出1，只需要pop一下右边的栈就可以了！
然后，我们是不是还要把 剩下的元素倒回原来的左边的栈呢？
注意，这里和上面那个题不一样的地方就在这里！
如果我们把右边的栈的数据倒回左边的栈，变成这样：
在这里插入图片描述
这时候如果再出栈，是不是还要重复把左边的栈的数据 重新push到右边的栈？
这无疑增加了工作量！
由于栈有着后进先出的特殊性质，所以 我们只要把左边的栈的数据push到右边的栈，右边的栈中就可以不断的pop（因为此时元素的顺序已经颠倒了！，符合先进先出了）
所以，导入到右边的栈之后，不需要再回来了！！！
然后 怎么push呢？，我们直接向左边的栈中push就可以了！！
也就是说：左边的栈用来push,我们叫做pushst,右边的栈用来pop，我们叫做popst
如果，popst已经空了，那么再把pushst里面的数据push到popst 就可以了！

总结：

	- 栈的性质和队列不一样，因为队列是先进先出
所以把一个数据从一个队列push到另一个队列之后，原来的元素顺序不会发生改变
所以需要在倒回来- 而栈的性质不一样，栈是后进先出
所以把`pushst`里的数据导入到`popst`之后，数据的顺序发生颠倒
所以，由于已经颠倒过来，把`popst`里的数据进行pop，就相当于队列的出队！
而不需要再倒回`pushst`的原因是因为： 这时候的`popst`里的数据顺序恰好是出队顺序
而如果重新导入`pushst`，那么再pop数据的时候，还需要把数据先push到`popst`中- 这样，如果我们想push数据，直接push到`pushst`中，
当`popst`空的时候，把`pushst`中数据导入到`popst`中，从而实现继续出队！

也就是说： pushst控制入队，popst控制出队

这个结构就相当于
在这里插入图片描述

三、💥题解💥

模拟队列的结构

包含两个栈

//匿名结构体的使用 可以利用typedef！
typedef struct {ST pushst;ST popst;
} MyQueue;

初始化队列

首先malloc一个 ‘队列’
然后要初始化 队列中的两个栈
pushst用来push
popst用来pop

MyQueue* myQueueCreate() {MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));//初始化两个栈StackInit(&obj->pushst);StackInit(&obj->popst);return obj;
}

Push

这样其实 push就很简单了
只需要向栈pushst里直接push就可以了！

void myQueuePush(MyQueue* obj, int x) {//入队统一在push栈中入数据StackPush(&obj->pushst,x);
}

Pop

pop比较麻烦，但也很简单
因为我们首先判断popst是不是为空
如果为空，那么pushst中的数据push到popst
否则直接poppopst

int myQueuePop(MyQueue* obj) {//出栈 是对pop进行的//如果popst为空 那么首先把pushst里的数据导入到popstif(StackEmpty(&obj->popst)){while(!StackEmpty(&obj->pushst)){StackPush(&obj->popst,StackTop(&obj->pushst));StackPop(&obj->pushst);}}//需要记录队尾 并返回int qtail=StackTop(&obj->popst);//出队StackPop(&obj->popst);//返回队尾元素return qtail;}

获取队头元素

由于popst的栈顶就相当于队头，所以直接返回popst的栈顶就可以了！
注意：需要判断一下popst是不是为空！
如果为空 需要把pushst中的数据 先 push到popst

int myQueuePeek(MyQueue* obj) {//队列的头相当于 popst的栈顶//首先判断是不是空 如果是空 导入到popstif(StackEmpty(&obj->popst)){while(!StackEmpty(&obj->pushst)){StackPush(&obj->popst,StackTop(&obj->pushst));StackPop(&obj->pushst);}}return StackTop(&obj->popst);
}

判断是不是空

显然如果两个栈都为空 说明队列为空

bool myQueueEmpty(MyQueue* obj) {//什么时候为空呢？//显然 如果两个栈都为空 说明队列为空return StackEmpty(&obj->pushst) && StackEmpty(&obj->popst);
}

释放

  1. 首先释放两栈
  2. 然后释放队列结构
void myQueueFree(MyQueue* obj) {//首先释放两个栈//然后释放MyQueueStackDestory(&obj->pushst);StackDestory(&obj->popst);free(obj);
}

✏️总代码✏️

typedef int STDataType;
typedef struct Stack {//动态开辟数组STDataType* a;int top;//栈顶int capacity;//容量
}ST;
//初始化
void StackInit(ST* ps);
//压栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
//获取栈中有效元素个数
int StackSize(ST* ps);
//显示栈顶元素
STDataType StackTop(ST* ps);
//检测栈是否为空
bool StackEmpty(ST* ps);
//销毁
void StackDestory(ST* ps);//初始化
void StackInit(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = ps->top = 0;
}
//压栈
void StackPush(ST* ps, STDataType x)
{assert(ps);//首先检查是不是需要扩容if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * newCapacity);if (tmp == NULL){printf("realloc fail");exit(-1);}ps->capacity = newCapacity;ps->a = tmp;}ps->a[ps->top] = x;ps->top++;
}
//出栈
void StackPop(ST* ps)
{assert(ps);//有元素才能出栈assert(ps->top > 0);//只需要ps--就可以了ps->top--;}
//获取栈中有效元素个数
int StackSize(ST* ps)
{assert(ps);return ps->top;
}
//获取栈顶元素
STDataType StackTop(ST* ps)
{assert(ps);return ps->a[ps->top-1];
}
//检测栈是否为空
bool StackEmpty(ST* ps)
{				assert(ps);return ps->top == 0;
}
//销毁
void StackDestory(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;//ps->a 不用了 所以置空就可以了ps->capacity = ps->top = 0;
}//匿名结构体的使用 可以利用typedef！
typedef struct {ST pushst;ST popst;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));//初始化两个栈StackInit(&obj->pushst);StackInit(&obj->popst);return obj;
}void myQueuePush(MyQueue* obj, int x) {//入队统一在push栈中入数据StackPush(&obj->pushst,x);
}int myQueuePop(MyQueue* obj) {//出栈 是对pop进行的//如果popst为空 那么首先把pushst里的数据导入到popstif(StackEmpty(&obj->popst)){while(!StackEmpty(&obj->pushst)){StackPush(&obj->popst,StackTop(&obj->pushst));StackPop(&obj->pushst);}}//需要记录队尾 并返回int qtail=StackTop(&obj->popst);//出队StackPop(&obj->popst);//返回队尾元素return qtail;}int myQueuePeek(MyQueue* obj) {//队列的头相当于 popst的栈顶//首先判断是不是空 如果是空 导入到popstif(StackEmpty(&obj->popst)){while(!StackEmpty(&obj->pushst)){StackPush(&obj->popst,StackTop(&obj->pushst));StackPop(&obj->pushst);}}return StackTop(&obj->popst);
}bool myQueueEmpty(MyQueue* obj) {//什么时候为空呢？//显然 如果两个栈都为空 说明队列为空return StackEmpty(&obj->pushst) && StackEmpty(&obj->popst);
}void myQueueFree(MyQueue* obj) {//首先释放两个栈//然后释放MyQueueStackDestory(&obj->pushst);StackDestory(&obj->popst);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);
*/

✨感谢阅读~ ✨
❤️码字不易，给个赞吧~❤️

在这里插入图片描述


http://www.ppmy.cn/news/1554950.html

相关文章

[源码+调试+讲解]微信小程序的成都美食分享系统springboot

[源码+调试+讲解]微信小程序的成都美食分享系统springboot

摘 要 当今社会已经步入了科学技术进步和经济社会快速发展的新时期，国际信息和学术交流也不断加强，计算机技术对经济社会发展和人民生活改善的影响也日益突出，人类的生存和思考方式也产生了变化。传统成都美食分享采取了人工的管理方法&am…
阅读更多...
Spring Boot 简介与快速入门指南

Spring Boot 简介与快速入门指南

目录 主要特点 核心组件 Spring Boot 应用的基本结构 1. 创建主应用类 2. 创建一个简单的控制器 3. 配置文件（application.properties） 如何运行 优势 总结 Spring Boot 是一个开源的 Java 框架，基于 Spring Framework，旨…
阅读更多...
ip地址获取失败啥意思？ip地址获取失败怎么回事

ip地址获取失败啥意思？ip地址获取失败怎么回事

在日常的网络使用中，我们时常依赖于稳定的IP地址来确保数据的顺畅传输和设备的正常识别。然而，有时我们会遇到“IP地址获取失败”的困扰，这不仅阻碍了我们的网络访问，还可能带来一系列的网络连接问题。那么，IP地址获取…
阅读更多...
免费开源的微信开发框架

免费开源的微信开发框架

删除好友 请求参数 Header 参数 export interface ApifoxModel {"X-GEWE-TOKEN": string;[property: string]: any; } Body 参数application/json export interface ApifoxModel {/*** 设备ID*/appId: string;/*** 删除好友的wxid*/wxid: string;[property: str…
阅读更多...
飞书解除复制，下载文件限制终极方案

飞书解除复制，下载文件限制终极方案

1.通过移除copy 事件，可以复制文档内容，但是飞书表格增加了键盘按键事件，表格无法复制，下载 2.通过chrome插件，可以复制clould document converter 可以实现下载飞书文档，但是无法下载表格 而且无法识别自定…
阅读更多...
小红书笔记采集链接版 | 同步飞书

小红书笔记采集链接版 | 同步飞书

一、下载影刀： https://www.winrobot360.com/share/activity?inviteUserUuid595634970300317698 二、加入应用市场 https://www.yingdao.com/share/accede/?inviteKeyb2d3f22a-fd6c-4a10-93a4-7de3492ee7fe 三、下载谷歌浏览器 （如果电脑已有谷歌…
阅读更多...
【Python系列】异步 Web 服务器

【Python系列】异步 Web 服务器

???欢迎来到我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老…
阅读更多...
Jenkins参数化构建详解(This project is parameterized)

Jenkins参数化构建详解(This project is parameterized)

本文详细介绍了Jenkins中不同类型的参数化构建方法，包括字符串、选项、多行文本、布尔值和git分支参数的配置，以及如何使用ActiveChoiceParameter实现动态获取参数选项。通过示例展示了传统方法和声明式pipeline的语法 文章目录 1. Jenkins的参数化构建1…
阅读更多...
最新文章

Copyright @ 2022~2023