Leetcode:栈和队列的互相实现_leetcode 两个队列实现栈

目录

一、用两个队列实现栈

题目：

分析：

代码实现：

 二、用两个栈实现队列

题目：

 分析：

代码：

总结：核心就在于先进先出和后进先出之间的一个灵活变换，两个栈能够先进先出，而两个队列能够后进先出 

一、用两个队列实现栈

题目：

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/implement-stack-using-queues/description/

分析：

首先，我们明确队列有几个接口，初始化、入队、出队、取队头、取队尾、判空、返回有效元素个数、销毁。

题目要求只使用队列标准操作实现栈的四种操作，push、pop、top、empty,实际要求我们主要要能够实现栈存储元素后进先出的特点即可。

那如何利用两个队列实现栈的后进先出呢？

代码实现：

（注释在代码中哦，一些错误的代码我给注释掉的不用管）

//两个队列，一个装元素，另一个用来倒typedef int QDataType;typedef struct QListNode{struct QListNode* next; QDataType data;}QNode;//定义一个包含队头和队尾的结构体typedef struct Queue{QNode* front;QNode* rear; int size;//标记队列中元素个数}Queue;void QueueInit(Queue* q){assert(q);/*QNode* tem = (QNode*)malloc(sizeof(QNode));if (tem == NULL){perror(\"malloc\");return;}*/q->front = q->rear = NULL;//q->front->next = NULL;//q->front->data = 0;q->size = 0;}//通过尾插在队尾入队列void QueuePush(Queue* q,QDataType x){assert(q);QNode* tem = (QNode*)malloc(sizeof(QNode));if (tem == NULL){assert(\"malloc\");return;} if (q->front == NULL)//第一个节点{q->front = q->rear = tem;q->front->data = x; tem->next=NULL;//别忘了tem的next置空}else//第二及以后节点{q->rear->next = tem;q->rear = tem;q->rear->next = NULL;q->rear->data = x;}q->size++; // tem->next = NULL; // tem->data = x; // if (q->rear == NULL) { // q->front = q->rear = tem; // } else { // q->rear->next = tem; // q->rear = tem; // 更新tail的指向 // } // q->size++; // push一下节点个数++}//通过头删实现在队头出队列void QueuePop(Queue* q){assert(q);assert(q->front);//头指针不为空才存在删QNode* tem = q->front;q->front = q->front->next;if (q->front == NULL)q->rear = NULL;//避免尾指针变成野指针free(tem);q->size--;}//获取队列头部元素QDataType QueueFront(Queue* q){assert(q);assert(q->front);return q->front->data;}//获取队列尾部元素QDataType QueueBack(Queue* q){assert(q);assert(q->rear);return q->rear->data;}//获取队列中有效元素个数int QueueSize(Queue* q){assert(q);return q->size;}// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 bool QueueEmpty(Queue* q){if (q->size == 0)return 1;elsereturn 0;}//销毁队列void QueueDestroy(Queue* q){ assert(q); while(q->front) { QNode* tem=q->front; q->front=q->front->next; free(tem); } q->rear=NULL; q->size=0; //assert(pq);// QNode* cur = pq->front;// while (cur)// {// QNode* next = cur->next;// free(cur);// cur = next;// }// pq->front = pq->rear = NULL;// pq->size = 0;}//上面都是队列的接口，因为此处是用C语言实现，所以得写一下//接下来才是栈的实现typedef struct { Queue q1;//定义两个队列 Queue q2;} MyStack;// typedef struct Stack// {// int* arr;// int top;// int capacity;// }//初始化//在本题由于栈的4种操作的实现完全依赖于队列，对栈的初始化就是对两个队列的初始化MyStack* myStackCreate() { MyStack* obj=(MyStack*)malloc(sizeof(MyStack)); QueueInit(&obj->q1);//->优先级高于& QueueInit(&obj->q2); return obj;}//压栈,把元素往不为空的队列压void myStackPush(MyStack* obj, int x) { if(!QueueEmpty(&obj->q1)) QueuePush(&obj->q1,x); else// QueuePush(&obj->q2,x);}//出栈//关键在于找到空队列，将不为空队列的前size-1个元素导到空队列，剩下的那1个元素则头删，从而实现栈的后进先出int myStackPop(MyStack* obj) { //假定q1为空队列 Queue* Empty=&obj->q1; Queue* No_Empty=&obj->q2; if(!QueueEmpty(Empty))//假定错误则调换 { Empty=&obj->q2; No_Empty=&obj->q1; } //找到了空队列和不为空队列，接下来实现不为空队列的前size-1个元素导到空队列 while(QueueSize(No_Empty)>1) { int tem=QueueFront(No_Empty); QueuePush(Empty,tem);//先将非空队列的元素压到空队列 QueuePop(No_Empty);//再头头删掉它 } //不为空队列的最后一个元素删除和返回 int tem=QueueFront(No_Empty); QueuePop(No_Empty); return tem;}//取栈顶元素int myStackTop(MyStack* obj) { // //假定q1为空队列 // Queue* Empty=&obj->q1; // Queue* No_Empty=&obj->q2; // if(!QueueEmpty(Empty))//假定错误则调换 // { // Empty=&obj->q2; // No_Empty=&obj->q1; // } // //找到了空队列和不为空队列，接下来实现不为空队列的前size-1个元素导到空队列 // while(QueueSize(No_Empty)>1) // { // int tem=QueueFront(No_Empty); // QueuePush(Empty,tem); // QueuePop(No_Empty); // } // //不为空队列的最后一个元素返回 // int tem=QueueBack(No_Empty); // //QueuePop(No_Empty); // return tem; if(!QueueEmpty(&obj->q1)) return QueueBack(&obj->q1); else return QueueBack(&obj->q2);}//判空bool myStackEmpty(MyStack* obj) { if(QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2)) return true; else return false; //return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);}//销毁栈//即销毁掉两个队列void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); free(obj);}

 二、用两个栈实现队列

题目：

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/implement-queue-using-stacks/description/

 分析：

与上面的思路类似，不同之处在于栈的的特点是后进先出，要实现队列的先进先出的话，除了要将后进的size-1个元素导到另一个栈，将最先进的元素通过出栈pop删除，为了以后能够继续重复此操作，还要再将导过去的元素再导回来。

注意在本题实现队列的出队pop时，最关键的就在于还要导回去！！！！

代码：

typedef int STDataType;typedef struct Stack{STDataType* arr;int top;//栈中元素个数int capacity;//栈容量}Stack;//扩容函数void Exp(Stack* p){if (p->capacity == p->top){int new_capacity = p->capacity == 0 ? 4 : p->capacity * 2;//三目运算STDataType* tem = (STDataType*)realloc(p->arr, new_capacity * sizeof(STDataType));//注意是p->arr，不是pif (tem == NULL)//对返回值判断{perror(\"realloc\");exit(1);}p->capacity = new_capacity;p->arr = tem;}}//初始化栈void InitStack(Stack* p){assert(p);p->arr = NULL;p->top = 0;p->capacity = 0;}//入栈void PushStack(Stack* p, STDataType x){assert(p);Exp(p);p->arr[p->top] = x;//元素入栈顶p->top++;}//出栈void PopStack(Stack* p){assert(p);assert(p->top > 0);//有元素才能出p->top--;}//取栈顶元素STDataType TopStack(Stack* p){assert(p);assert(p->top > 0);return p->arr[p->top - 1];//top相当于size，而数组下标是从0开始的}//获取栈中有效元素个数int SizeStack(Stack* p){assert(p);return p->top;}//判空bool EmptyStack(Stack* p){assert(p);//确实栈中元素为0则为true,否则为falsereturn !p->top;}void DestroyStack(Stack* p){assert(p);if (p->arr)//arr非空指针时才存在释放问题{free(p->arr);//释放掉动态申请的内存p->arr = NULL;//置空p->capacity = p->top = 0;}}//以上都是栈的接口//接下来才是用栈实现队列typedef struct { Stack s1;//定义两个栈 Stack s2;} MyQueue;//对队列的初始化即对两个栈的初始化MyQueue* myQueueCreate() { MyQueue* tem=(MyQueue*)malloc(sizeof(MyQueue)); InitStack(&tem->s1); InitStack(&tem->s2); return tem;//不要忘了返回！！！}//同样，始终保持一个栈为空，而另一个不为空,往不为空的栈压void myQueuePush(MyQueue* obj, int x) { if(!EmptyStack(&obj->s1)) PushStack(&obj->s1,x); else PushStack(&obj->s2,x);}//队列的头删//int myQueuePop(MyQueue* obj) { assert(obj); //assert((!EmptyStack(&obj->s1) || !EmptyStack(&obj->s2));//两个栈都为空就不存在后面问题 //假设 Stack* Empty=&obj->s1; Stack* No_Empty=&obj->s2; if(!EmptyStack(Empty))//假设错误调换 { Empty=&obj->s2; No_Empty=&obj->s1; } //实现头删 //1.找到先进的元素 while(SizeStack(No_Empty)>1) { int tem=TopStack(No_Empty);//取栈顶元素 PopStack(No_Empty);//删除栈顶元素 PushStack(Empty,tem);//压入另一个空栈 } //2。删除 int tem=TopStack(No_Empty); PopStack(No_Empty); //3.将在另一个栈中的元素导回去，以便下次头删 while(!EmptyStack(Empty)) { int tem=TopStack(Empty); PopStack(Empty); PushStack(No_Empty,tem); } return tem;}//返回队列开头元素int myQueuePeek(MyQueue* obj) { assert(obj); //assert((!EmptyStack(&obj->s1) || !EmptyStack(&obj->s2));//两个栈都为空就不存在后面问题 if(!EmptyStack(&obj->s1)) return (&obj->s1)->arr[0]; else return (&obj->s2)->arr[0];}//判空bool myQueueEmpty(MyQueue* obj) { return EmptyStack(&obj->s1) && EmptyStack(&obj->s2);}void myQueueFree(MyQueue* obj) { assert(obj);//销毁栈即销毁队列 DestroyStack(&obj->s1); DestroyStack(&obj->s2);}

总结：核心就在于先进先出和后进先出之间的一个灵活变换，两个栈能够先进先出，而两个队列能够后进先出 

 （栈和队列还不是很清楚的铁铁可以看我前面博客哦）