用GIF软件做的GIF 超出网站限制/app安装下载

LeetCode刷题记录

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

---

✨前言✨

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

• 栈：

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
栈中的数据元素遵守后进先出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);
*/

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