题目描述
题目链接：225. 用队列实现栈 - 力扣（LeetCode）
题目分析
我们先把之前写的队列实现代码搬过来
用队列实现栈最主要的是实现栈后进先出的特点，而队列的特点是先进先出，那么我们可以用两个队列来实现
- 一个队列存数据
- 另一个队列在出数据的时候导数据
具体的接口有下面几个
初始化
我们先创建一个结构体来封装两个队列
初始化两个队列
销毁
我们要分析清楚这个结构，pst存q1,q2两个队列，需要先销毁q1和q2，然后释放pst
入栈
入栈我们入到不为空的队列中去，当q1不为空则入队列q1，否则入队列q2
出栈
出栈的时候就需要导数据了，比如数据都在q1中，q2为空，这时我们先判断空队列是哪一个，然后将非空队列前n-1个数据导入到空队列中，最后留一个数据就是栈顶数据，也是队列的队头数据，可以用QFront接口，先用top保存这个数据，接着pop掉这个数据，返回top
判空
返回栈顶元素
直接取不为空队列的队尾数据
代码示例
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <assert.h> //创建 typedef int QDataType; typedef struct QueueNode { QDataType val; struct QueueNode* next; }QNode; typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue; //把队列的头尾封装在一个结构体中 //初始化 void QInit(Queue* pq); //销毁 void QDestroy(Queue* pq); //入队列 void QPush(Queue* pq, QDataType x); //出队列 void QPop(Queue* pq); //取队头数据 QDataType QFront(Queue* pq); //取队尾数据 QDataType QBack(Queue* pq); //判空 bool QEmpty(Queue* pq); //返回队列有效元素个数 int QSize(Queue* pq); //初始化 void QInit(Queue* pq) { assert(pq); pq->phead = pq->ptail = NULL; pq->size = 0; } //销毁 void QDestroy(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 QPush(Queue* pq, QDataType x) { assert(pq); //创建newnode QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->val = x; newnode->next = NULL; if (pq->ptail == NULL) { pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; } //出队列 void QPop(Queue* pq) { assert(pq); assert(pq->phead); QNode* del = pq->phead; pq->phead = pq->phead->next; free(del); del = NULL; if (pq->phead == NULL) { pq->ptail = NULL; //防止ptail成为野指针 } pq->size--; } //取队头数据 QDataType QFront(Queue* pq) { assert(pq); assert(pq->phead); return pq->phead->val; } //取队尾数据 QDataType QBack(Queue* pq) { assert(pq); assert(pq->ptail); return pq->ptail->val; } //判空 bool QEmpty(Queue* pq) { assert(pq); return pq->phead == NULL; } //返回队列有效元素个数 int QSize(Queue* pq) { assert(pq); return pq->size; } typedef struct MyStack{ Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack* pst = (MyStack*)malloc(sizeof(MyStack)); QInit(&(pst->q1)); QInit(&(pst->q2)); return pst; } void myStackPush(MyStack* obj, int x) { if (!QEmpty(&(obj->q1))) { QPush(&(obj->q1), x); } else { QPush(&(obj->q2), x); } } int myStackPop(MyStack* obj) { Queue* empty = &(obj->q1); Queue* nonempty = &(obj->q2); if (!QEmpty(&(obj->q1))) { empty = &(obj->q2); nonempty = &(obj->q1); } while (QSize(nonempty) > 1) { QPush(empty, QFront(nonempty)); QPop(nonempty); } int top = QFront(nonempty); QPop(nonempty); return top; } int myStackTop(MyStack* obj) { if (!QEmpty(&(obj->q1))) { return QBack(&(obj->q1)); } else { return QBack(&(obj->q2)); } } bool myStackEmpty(MyStack* obj) { return QEmpty(&(obj->q1)) && QEmpty(&(obj->q2)); } void myStackFree(MyStack* obj) { QDestroy(&(obj->q1)); QDestroy(&(obj->q2)); free(obj); }
