【力扣刷题实战】用队列实现栈
大家好，我是小卡皮巴拉
文章目录
目录
力扣题目： 用队列实现栈
题目描述
示例：
解题思路
问题理解
算法选择
具体思路
解题要点
完整代码（C语言）
兄弟们共勉 ！！！
每篇前言
博客主页：小卡皮巴拉
咱的口号：🌹小比特，大梦想🌹
作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请大佬们批评斧正。
力扣题目： 用队列实现栈
原题链接： 用队列实现栈
题目描述
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（
push、top、pop和empty）。实现
MyStack类：
void push(int x)将元素 x 压入栈顶。
int pop()移除并返回栈顶元素。
int top()返回栈顶元素。
boolean empty()如果栈是空的，返回true；否则，返回false。注意：
你只能使用队列的标准操作 —— 也就是
push to back、peek/pop from front、size和is empty这些操作。你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
示例：
输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]
解题思路
问题理解
题目要求通过两个队列（FIFO）来模拟一个栈（LIFO）的功能，包括四个基本操作：
push（入栈）、pop（出栈）、top（查看栈顶元素）和empty（检查栈是否为空）。由于栈是后入先出的数据结构，而队列是先进先出的，因此需要通过两个队列的协作来实现栈的后入先出行为。算法选择
使用两个队列：
queue1和queue2。queue1用于处理主要的入栈和出栈操作，而queue2作为辅助队列，用于在出栈和查看栈顶元素时重新排序queue1中的元素。具体思路
初始化栈：
使用两个队列
q1和q2来模拟栈。初始化栈时，同时初始化这两个队列。
入栈操作（push）：
总是向非空队列（或任意队列，如果两个队列都为空则选择任意一个）中插入新元素。
这样做是为了保持一个队列始终为空（或接近为空），以便在出栈时能够高效地转移元素。
出栈操作（pop）：
确定哪个队列是非空的（即包含栈顶元素的队列）。
将非空队列中的元素（除了最后一个）逐个转移到空队列中。
弹出非空队列中的最后一个元素（即栈顶元素），并返回其值。
（可选）交换两个队列的角色，以便下次出栈操作能够高效进行。但在此实现中，由于我们总是向非空队列插入新元素，因此这一步是多余的。
查看栈顶元素（top）：
确定哪个队列是非空的。
直接返回非空队列中的最后一个元素（即栈顶元素）。
不需要转移元素或交换队列角色。
检查栈是否为空（empty）：
同时检查两个队列是否为空。
如果两个队列都为空，则栈为空；否则，栈不为空。
销毁栈：
销毁两个队列，并释放栈结构所占用的内存。
解题要点
双队列协作：利用两个队列的先进先出特性来模拟栈的后入先出行为。
元素转移：在出栈和查看栈顶元素时，将一个队列中的元素转移到另一个队列中，以便保留栈顶元素。
角色交换（可选）：为了优化后续操作，可以在出栈后交换两个队列的角色，但这不是必需的，特别是在
top操作中。状态维护：确保在每次操作后，都能正确地反映栈的当前状态。
完整代码（C语言）
typedef int QDataType; //定义队列结点的结构 typedef struct QueueNode { QDataType data; struct QueueNode* next; }QueueNode; //定义队列的结构 typedef struct Queue { QueueNode* phead;//队头 QueueNode* ptail;//队尾 int size; //队列有效元素个数 }Queue; //初始化 void QueueInit(Queue* pq) { assert(pq); 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!\n"); exit(1); } newnode->data = x; newnode->next = NULL; //队列为空，队头和队尾都是newnode if (pq->phead == NULL) { pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = pq->ptail->next; } pq->size++; } //队列判空 bool QueueEmpty(Queue* pq) { assert(pq); //队列为空时，头为空或头和尾均为空 return pq->phead == NULL; } //队列有效元素个数 int QueueSize(Queue* pq) { return pq->size; } //出队列——从队列中删除数据 void QueuePop(Queue* pq) { assert(pq); assert(!(QueueEmpty(pq))); //只有一个结点 if (pq->phead == 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; } //销毁队列 void QueueDestory(Queue* pq) { assert(pq); QueueNode* pcur = pq->phead; while (pcur) { QueueNode* next = pcur->next; free(pcur); pcur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; } /上面是队列以及相关方法/ typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack* pst = (MyStack*)malloc(sizeof(MyStack)); QueueInit(&pst->q1); QueueInit(&pst->q2); return pst; } void myStackPush(MyStack* obj, int x) { //1.向不为空的队列中插入数据 if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1,x); } else { QueuePush(&obj->q2,x); } } int myStackPop(MyStack* obj) { //判断空队列和非空队列 Queue* emp = &obj->q1;//空队列 Queue* noneEmp = &obj->q2;//非空队列 if(QueueEmpty(&obj->q2)) { emp = &obj->q2; noneEmp = &obj->q1; } //把noneEmp前size-1个数据导入到emp while(QueueSize(noneEmp) > 1) { //先取队头的数据，再将队头的数据放到emp队列中 QueuePush(emp,QueueFront(noneEmp)); //删除非空队列中的队头数据 QueuePop(noneEmp); } int top = QueueFront(noneEmp); QueuePop(noneEmp); 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) { QueueDestory(&obj->q1); QueueDestory(&obj->q2); free(obj); obj == NULL; }
兄弟们共勉 ！！！
码字不易，求个三连
抱拳了兄弟们！
