网站和h5,网页设计培训点,好看模板大全,最简单的网站建设语音LeetCode刷题记录 #x1f310; 我的博客主页#xff1a;iiiiiankor#x1f3af; 如果你觉得我的内容对你有帮助#xff0c;不妨点个赞#x1f44d;、留个评论✍#xff0c;或者收藏⭐#xff0c;让我们一起进步#xff01;#x1f4dd; 专栏系列#xff1a;LeetCode…
LeetCode刷题记录 我的博客主页iiiiiankor 如果你觉得我的内容对你有帮助不妨点个赞、留个评论✍或者收藏⭐让我们一起进步 专栏系列LeetCode 刷题日志 文章内容来自我的学习与实践经验如果你有任何想法或问题欢迎随时在评论区交流讨论。让我们一起探索更多的可能 文章目录 ✨前言✨☢️注意☢️LeetCode225.用队列实现栈一、题目描述二、分析三、题解栈的结构定义Push接口Pop接口获取栈顶元素判断栈是否为空释放free✏️总代码✏️ LeetCode232.用栈实现队列一、题目描述二、分析三、题解模拟队列的结构初始化队列PushPop获取队头元素判断是不是空释放✏️总代码✏️ ✨前言✨ 首先我们可以先复习一下相关性质 栈 栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。 栈中的数据元素遵守后进先出LIFOLast 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 首先把结构中包含的两个队列释放掉然后把该结构释放掉 ✏️总代码✏️
// 用队列实现栈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)//也可以使用headNULL{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 qtailStackTop(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);
}释放 首先释放两栈然后释放队列结构 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 qtailStackTop(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);
*/✨感谢阅读~ ✨ ❤️码字不易给个赞吧~❤️
