两个队列实现一个栈
前言：
💥🎈个人主页:Dream_Chaser～ 🎈💥
✨✨刷题专栏:http://t.csdn.cn/UlvTc
⛳⛳本篇内容:力扣上栈与队列的面试OJ题目
队列的实现（前提准备）
#include<stdio.h> #include<assert.h> #include<stdbool.h> #include<stdlib.h> typedef int QDataType; typedef struct QueueNode { QDataType data; struct QueueNode* next; }QNode; typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue;//表示队列整体,一个是出数据，一个是入数据. void QueueInit(Queue* pq);// 初始化队列 void QueueDestroy(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);// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 void QueueInit(Queue* pq) { assert(pq);// 检查指针是否为空 pq->phead=NULL; // 将队列的头指针置为空 pq->ptail = NULL;// 将队列的头指针置为空 pq->size = 0;// 将队列的头指针置为空 } // void QPrint(Queue* pq) // { // assert(pq); // QNode* cur = pq->phead; // QNode* next = cur; // while (cur != NULL) // { // printf("%d ", cur->data); // cur = cur->next; // } // } void QueueDestroy(Queue* pq) { assert(pq);// 检查指针是否为空 QNode* cur = pq->phead;// 创建一个指针 cur，指向队列的头指针 while (cur) { QNode* next = cur->next;// 创建一个指针 cur，指向队列的头指针 free(cur);// 释放当前节点的内存 cur = next;// 将指针 cur 移动到下一个节点 } pq->phead = pq->ptail = NULL;// 将队列的头指针和尾指针置为空 pq->size = 0;// 将队列的大小置为0 } void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode));// 创建一个新的节点 if (newnode == NULL) { perror("malloc fail\n");// 检查内存分配是否成功 return; } newnode->data = x;// 设置新节点的数据为传入的元素值 newnode->next = NULL;// 将新节点的指针域置空 //一个节点 //多个节点 if (pq->ptail == NULL)// 判断队列是否为空 { //assert(pq->phead == NULL);// 如果队列为空，头指针也应为空 pq->phead = pq->ptail = newnode;// 将新节点同时设置为队列的头节点和尾节点 } else { pq->ptail->next = newnode;// 将新节点同时设置为队列的头节点和尾节点 pq->ptail = newnode;// 更新队列的尾指针为新节点 } pq->size++;// 增加队列的大小计数 } void QueuePop(Queue* pq) { assert(pq);// 检查指针是否为空 assert(!QueueEmpty(pq));// 检查队列是否非空 //assert(pq->phead);// 检查队列的头指针是否存在 //1.一个节点 if (pq->phead->next == NULL) // 队列只有一个节点的情况 { free(pq->phead); // 释放队列头节点的内存 pq->phead = pq->ptail = NULL;// 将队列的头指针和尾指针置为空 } else { //头删 QNode* next = pq->phead->next; //保存队列头节点的下一个节点指针 free(pq->phead);// 释放队列头节点的内存 pq->phead = next;// 更新队列的头指针为下一个节点 } pq->size--;//减少队列的大小计数 } QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq));// 检查队列是否非空 //assert(pq->phead);// 检查队列的头指针是否存在 return pq->phead->data;// 返回队列头节点的数据 } QDataType QueueBack(Queue* pq) { assert(pq);// 检查队列是否非空 assert(!QueueEmpty(pq));// 检查队列是否非空 //assert(pq->phead);// 检查队列的头指针是否存在 return pq->ptail->data;//返回队列尾节点的数据 } int QueueSize(Queue* pq) { assert(pq);//检查指针是否为空 return pq->size;//返回队列的大小（元素个数） } bool QueueEmpty(Queue* pq) { assert(pq); //方法一,将队列的头指针以及尾指针置空 //return pq->phead = NULL && pq->ptail==NULL; //方法二,将队列的有效元素置空 return pq->size == 0; }
一.题目描述
来源:225. 用队列实现栈 - 力扣（LeetCode）
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（
push、top、pop和empty）。实现
MyStack类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。
需要了解的知识：
栈(Stack)：
- 后进先出(LIFO)顺序:最后压入栈的元素,第一个弹出栈。它像一堆盘子,最后放上的盘子,先拿走。
- 在栈顶添加,在栈顶删除:所有新元素都放在栈顶,操作栈时只有栈顶元素可以被访问。
- 压栈和出栈操作不可逆:当一个元素被压入栈后,要等到它到栈顶位置才能将其弹出。栈不允许非栈顶元素先出栈。
- 有大小限制:每个栈都有最大容量限制,栈满时不能继续压入新元素。
- 主要操作:栈主要支持两种操作 - 入栈(push)和出栈(pop),所有元素都从栈顶压入/弹出。
- 适合处理后进先出的任务:栈这种后进先出的特性,适合模拟那些需要后操作的先完成的场景,如函数调用堆栈。
总结：是一种后进先出的线性表,只允许在表的一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据,先进入的元素最后才能取出,具有先进后出的逻辑顺序。
队列(Queue)：
- 先进先出(FIFO)顺序:先进入队列的元素会先出队列,后进入的元素后出队列。
- 在队尾添加,在队头删除:所有新元素都添加在队尾,删除元素时都从队头删除元素。
- 出队操作不可取消:已进入队列的元素不能中途删除,只能等待它到队头后再删除它。
- 有大小限制:队列通常有最大容量限制,队列满时不能再加入新元素,必须等待队头元素出队后才能加入。
- 主要操作:队列主要支持两种操作 - 入队(enqueue)和出队(dequeue),入队是将元素加入队尾,出队是从队头删除元素。
- 适合处理先进先出的任务:队列适合去处理需要先进先出顺序的任务,比如打印任务队列、排队等。
总结：是一个先进先出、有顺序的线性表,它只允许在一端进行插入,在另一端进行删除,遵循先进先出的原则。这使其非常适合模拟现实生活中的排队等情形。
1.自定义栈的结构
MyStack 这个结构体模拟了一个栈的数据结构,它使用两个队列 q1 和 q2 来实现栈的功能。
typedef struct { Queue q1; Queue q2; } MyStack;
2.自定义栈的初始化
使用malloc 函数为 MyStack 结构体对象分配内存空间。sizeof(MyStack) 表示要分配的内存大小等于 MyStack 结构体的大小。返回的指针类型是void* 。
因此需要进行类型转换为 MyStack*类型并将其赋值给 obj变量,初始化 obj 指向的 MyStack 结构体中的队列q1 和 q2。如果内存分配和初始化成功，最后，函数返回指向新创建的MyStack对象的指针obj
代码实现：
MyStack* myStackCreate() { MyStack *obj=(MyStack*)malloc(sizeof(MyStack)); if(obj == NULL) { perror("malloc fail"); return NULL; } //用于初始化 obj 指向的 MyStack 结构体中的队列 q1 和 q2 QueueInit(&obj->q1);//初始化q1队列 QueueInit(&obj->q2);//初始化q2队列 //返回指向已创建并初始化的 MyStack 结构体对象的指针 obj return obj; }
3.将元素压入栈顶
将元素推入栈时：
- 如果队列
q1不为空，就将元素直接推入q1中；- 如果
q1为空，就将元素推入q2中。
这样的实现方式可以确保在栈中的元素都集中在一个队列中（要么是 q1，要是 q2），而另一个队列则保持为空。这种实现方式的优势在于在执行出栈操作时，可以将非空队列中的元素转移到另一个空队列中，以便实现栈的先进后出特性。
void myStackPush(MyStack* obj, int x) { if (!QueueEmpty(&obj->q1))// 如果 q1 不为空，将元素推入 q1 { QueuePush(&obj->q1, x); } else// 如果 q1 为空，将元素推入 q2 { QueuePush(&obj->q2, x); } }
4.移除并返回栈顶元素
演示一遍出栈过程
演示全程出栈过程(只演示栈内部的队列)
代码实现:
int myStackPop(MyStack* obj)//栈出元素 { //假设q1队列是空队列,q2非空队列 Queue* pEmptyQ=&obj->q1; Queue* pNonEmptyQ=&obj->q2; if(!QueueEmpty(&obj->q1))//如果q1不为空 { //此时空队列指针指向q2 pEmptyQ=&obj->q2; pNonEmptyQ=&obj->q1;//非空队列指针指向q1 } //挪数据,结束条件是非空队列的元素个数为1 while(QueueSize(pNonEmptyQ)>1) { QueuePush(pEmptyQ,QueueFront(pNonEmptyQ));//获取非队列头部元素，把非空队列的元素入到空队列， QueuePop(pNonEmptyQ);//接着非空队列出元素 } //此时非空队列只有一个元素 int top=QueueFront(pNonEmptyQ);//获取此时非空队列的头部元素 QueuePop(pNonEmptyQ);//到这步,非空队列出完所有元素 // 返非空队列元素 return top; }
5.返回栈顶元素
q1队列如果不为空，那么返回q1队列的队尾元素当作自定义栈的栈顶元素，反之q2亦然。
int myStackTop(MyStack* obj)//返回栈顶元素 { if(!QueueEmpty(&obj->q1))//q1队列如果不为NULL { return QueueBack(&obj->q1);//返回q1队尾元素 } else//q2队列如果不为NULL { return QueueBack(&obj->q2);//返回q2队尾元素 } }
6.判断栈是否为空栈
判空就是要判断q1队列和q2队列都为空，才证明这个栈为空栈。
bool myStackEmpty(MyStack* obj)//判断自定义栈是否为空栈 { return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); }
7.栈的销毁
错误写法：内存泄露
正确写法：
先把q1和q2队列指向的节点free掉，接着再free掉整个MyStack，这样确保了不会内存泄露。
void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); free(obj); }
自定义栈的代码实现
typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack *obj=(MyStack*)malloc(sizeof(MyStack)); if(obj == NULL) { perror("malloc fail"); return NULL; } QueueInit(&obj->q1);//初始化q1队列 QueueInit(&obj->q2);//初始化q2队列 return obj; } // //注意以下写法 // typedef struct // { // Queue* q1; // Queue* q2; // }MyStack; // MyStack* myStackCreate() // { // MyStack* obj=(MyStack*)malloc(sizeof(MyStack)); // if(obj == NULL) // { // perror("malloc fail"); // return NULL; // } // obj->q1=(Queue*)malloc(sizeof(Queue)); // obj->q2=(Queue*)malloc(sizeof(Queue)); // 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); } } int myStackPop(MyStack* obj)//栈出元素 { //假设q1队列是空队列,q2非空队列 Queue* pEmptyQ=&obj->q1; Queue* pNonEmptyQ=&obj->q2; if(!QueueEmpty(&obj->q1))//如果q1不为空 { //此时空队列指针指向q2 pEmptyQ=&obj->q2; pNonEmptyQ=&obj->q1;//非空队列指针指向q1 } //挪数据,结束条件是非空队列的元素个数为1 while(QueueSize(pNonEmptyQ)>1) { QueuePush(pEmptyQ,QueueFront(pNonEmptyQ));//获取非队列头部元素，把非空队列的元素入到空队列， QueuePop(pNonEmptyQ);//接着非空队列出元素 } //此时非空队列只有一个元素 int top=QueueFront(pNonEmptyQ);//获取此时非空队列的头部元素 QueuePop(pNonEmptyQ);//到这步,非空队列出完所有元素 // 返非空队列元素 return top; } int myStackTop(MyStack* obj)//返回栈顶元素 { if(!QueueEmpty(&obj->q1))//q1队列如果不为NULL { return QueueBack(&obj->q1);//返回q1队尾元素 } else//q2队列如果不为NULL { return QueueBack(&obj->q2);//返回q2队尾元素 } } bool myStackEmpty(MyStack* obj)//判断自定义栈是否为空栈 { return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); } void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); free(obj); }
代码执行：
到这里文章就结束了，如有错误欢迎指正，感谢你的来访与支持！
