朋友们、伙计们，我们又见面了，今天给大家带来的是LeetCode--225.用队列实现栈
数 据 结 构 专 栏：数据结构
个 人 主 页 ：stackY、
LeetCode 专 栏 ：LeetCode刷题训练营
LeetCode--225.用队列实现栈：https://leetcode.cn/problems/implement-stack-using-queues/
目录
1.题目介绍
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
1. void push(int x) 将元素 x 压入栈顶。
2. int pop() 移除并返回栈顶元素。
3. int top() 返回栈顶元素。
4. boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
1. 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
2. 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
编辑
2.实例演示
编辑
3.解题思路
3.1创建栈
使用两个队列来实现栈的功能，首先我们得写出一个队列，队列的功能是先进先出，栈的功能是后进先出，在创建栈的时候需要有两个队列，然后为栈创建一块空间，并且将两个队列都进行初始化：
代码演示：
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); QueueInit(&obj->q2); return obj; }
3.2出栈操作
编辑
题目要求删除之后返回栈顶的元素。
栈的功能是先入后出，然而队列的功能是先入先出，那么我们该怎么操作呢？我们现在有两个队列，出栈是出的最后一个数据（第n个数据），我们可以先将一个队列的前n-1个数据依次插入到另外一个队列中（每插入一个然后再删除一个），这时原来的队列中就剩下最后一个数据，这时再将最后一个数据删除，这样子就达成了出栈时出最后一个数据的操作：我们在这里先假设第一个队列为空，第二个队列不为空，然后进行判断，如果不符合就交换，然后就是导数据的过程，然后就可以进行删除了：
编辑
代码演示：
int myStackPop(MyStack* obj) { //假设q1为空 //q2不为空 Queue* pEmptyQ = &obj->q1; Queue* pNoEmptyQ = &obj->q2; //判断是否正确，不正确则交换 if(!QueueEmpty(&obj->q1)) { pEmptyQ = &obj->q2; pNoEmptyQ = &obj->q1; } //导数据 //一直取到第Size-1个，这时就剩下的最后一个数据 while(QueueSize(pNoEmptyQ) > 1) { //将不为空的队列中的数据插入到为空的队列 QueuePush(pEmptyQ, QueueFront(pNoEmptyQ)); QueuePop(pNoEmptyQ); } //删除最后一个数据 int top = QueueFront(pNoEmptyQ); QueuePop(pNoEmptyQ); return top; }
3.3压栈操作
由于我们是用两个队列来实现栈的功能，所以压栈操作也就是插入数据的操作需要将数据插入到队列中，那么怎么插入呢？对应前面的删除，我们需要将数据插入到不为空的队列中，那么第一次插入的时候两个队列都为空，这时随便插入即可：
代码演示：
void myStackPush(MyStack* obj, int x) { //判断是否为空 if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1, x); } else { QueuePush(&obj->q2, x); } }
3.4获取栈顶元素
这里的栈顶的元素就表示的是不为空的队列中的队尾的数据，所以只需要将不为空的队列的队尾的数据直接返回：
代码实现：
int myStackTop(MyStack* obj) { //q1不为空返回q1的队尾数据 if(!QueueEmpty(&obj->q1)) { return QueueBack(&obj->q1); } //q2不为空返回q2的队尾数据 else { return QueueBack(&obj->q2); } }
3.5判断栈是否为空
判断栈是否为空就是判断两个队列是否为空：
代码演示：
bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); }
3.6释放栈
对栈的释放我们先要销毁实现栈的两个队列，然后再将栈空间释放：
代码实现：
void myStackFree(MyStack* obj) { //先销毁两个队列 QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); //再释放栈空间 free(obj); }
4.完整代码
//链式结构：表示队列 typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }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); //检测队列是否为空 bool QueueEmpty(Queue* pq); //对头出队列 void QueuePop(Queue* pq); //获取队头的元素 QDataType QueueFront(Queue* pq); //获取队尾的元素 QDataType QueueBack(Queue* pq); //获取队列有效元素的个数 int QueueSize(Queue* pq); //初始化队列 void QueueInit(Queue* pq) { assert(pq); pq->phead = NULL; pq->ptail= NULL; pq->size = 0; } //销毁队列 void QueueDestroy(Queue* pq) { assert(pq); QNode* cur = pq->phead; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; } //队尾入队列 void QueuePush(Queue* pq, QDataType x) { assert(pq); //创建新的结点 QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->next = NULL; newnode->data = x; //第一次尾插 if (pq->ptail == NULL) { assert(pq->phead == NULL); pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } //有效元素++ pq->size++; } //检测队列是否为空 bool QueueEmpty(Queue* pq) { assert(pq); //1.判断头、尾指针 /* return pq->phead == NULL && pq->ptail == NULL; */ //2.判断有效元素个数 return pq->size == 0; } //队头出队列 void QueuePop(Queue* pq) { assert(pq); //判空 assert(!QueueEmpty(pq)); //一个结点 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)); return pq->phead->data; } //获取队尾的元素 QDataType QueueBack(Queue* pq) { assert(pq); //先判空 assert(!QueueEmpty(pq)); return pq->ptail->data; } //获取队列有效元素的个数 int QueueSize(Queue* pq) { assert(pq); return pq->size; } 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); 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* pNoEmptyQ = &obj->q2; //判断是否正确，不正确则交换 if(!QueueEmpty(&obj->q1)) { pEmptyQ = &obj->q2; pNoEmptyQ = &obj->q1; } //导数据 //一直取到第Size-1个，这时就剩下的最后一个数据 while(QueueSize(pNoEmptyQ) > 1) { //将不为空的队列中的数据插入到为空的队列 QueuePush(pEmptyQ, QueueFront(pNoEmptyQ)); QueuePop(pNoEmptyQ); } //删除最后一个数据 int top = QueueFront(pNoEmptyQ); QueuePop(pNoEmptyQ); return top; } int myStackTop(MyStack* obj) { //q1不为空返回q1的队尾数据 if(!QueueEmpty(&obj->q1)) { return QueueBack(&obj->q1); } //q2不为空返回q2的队尾数据 else { return QueueBack(&obj->q2); } } bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); } void myStackFree(MyStack* obj) { //先销毁两个队列 QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); //再释放栈空间 free(obj); } /** * Your MyStack struct will be instantiated and called as such: * MyStack* obj = myStackCreate(); * myStackPush(obj, x); * int param_2 = myStackPop(obj); * int param_3 = myStackTop(obj); * bool param_4 = myStackEmpty(obj); * myStackFree(obj); */
今天的博客就分享到这里，喜欢的老铁留下你的三连，感谢感谢！我们下期再见！！
