【力扣刷题实战】用队列实现栈
大家好，我是小卡皮巴拉
文章目录
目录
力扣题目： 用队列实现栈
题目描述
示例：
解题思路
问题理解
算法选择
具体思路
解题要点
完整代码（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;//队列为空，队头和队尾都是newnodeif (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个数据导入到empwhile(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; }
兄弟们共勉 ！！！
码字不易，求个三连
抱拳了兄弟们！
