题目一 用队列实现栈
请你仅使用两个队列实现一个后入先出（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（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
我们先来分析下题目
要求用两个队列实现一个栈 并且实现四种操作
我们来看第一个Push操作
栈的特点是什么？ 先进后出
队列的特点是什么？ 先进先出
来看图
有思路了
图上是两个队列
我们假设 注意啊 是假设
第一行的图 它就是一个栈
那么我们可以判断出 它的数据插入顺序就是 1 2 3 4
这个时候队列的头就是栈的尾
如果我们这个时候需要删除栈的头数据应该怎么办呢？
我们都知道队列的数据只能是从头开始出
也就是说 比如要将队列前面的1 2 3 全部出完之后才能开始出 4
但是我们不可能会抛弃之前的数据啊
这个时候我们就想到了第二个队列的用处了
只需要将我Pop的数据使用第二个队列来接受就可以
实现起来的图大概是这样子
这个时候我们就能删除掉头数据了
如果需要再删除一个怎么办呢？
那么只需要将上面的操作再重复一次就好了
这个时候的插入数据只需要往不为空的队列插入数据就可以了
要求首元素就是返回队列的尾
要求尾元素就是返回队列的头
也就是两个步骤
1.保持一个队列为空，一个队列存数据
2.出栈，把前面的数据倒入空队列
接下来我们来实现代码
把所有的队列代码以及接口函数拷贝进去
第一步 定义结构体
我们来看这个 我们应该怎么定义我们的Stack结构体呢？
既然是两个队列的实现的
那么是不是可以放两个队列的结构在里面？
仔细一想好像可行
我们来试试
typedef struct { Queue q1; Queue q2; } MyStack;
画个图方便大家理解
三个结构体的关系一目了然
第二步 实现创建（初始化）
MyStack* myStackCreate() { MyStack*pst = ( MyStack*)malloc(sizeof( MyStack)); if(pst==NULL) { perror("malloc fail"); return NULL; } QueueInit(&pst->q1); QueueInit(&pst->q2); return pst; }
第三步 插入数据
这里要判断队列是否为空，不为空就插入数据，两个都为空就随机一个队列插入数据
看代码：
void myStackPush(MyStack* obj, int x) { if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1,x); }else{ QueuePush(&obj->q2,x); } }
第四步 删除数据
这是最难的部分，需要我们倒数据
我们先写出两个指针来判断空和非空
如果说我们的判断不正确的话 那么我们就将这两个指针翻转一下就好了
代码整体表现不变
int myStackPop(MyStack* obj) { Queue*emptyQ = &obj->q1; Queue*nonemptyQ = &obj->q2; if(!QueueEmpty(&obj->q1)) { emptyQ = &obj->q2; nonemptyQ=&obj->q1; } //倒数据 while(QueueSize(nonemptyQ)>1) { QueuePush(emptyQ,QueueFront(nonemptyQ)); QueuePop(nonemptyQ); } //记录删除值 删掉 int top = QueueFront(nonemptyQ); QueuePop(nonemptyQ); return top; }
第五步 返回头的值
这里我们可以分两种情况讨论
如果1不为空就返回1的尾值
如果2不为空就返回2的尾值
int myStackTop(MyStack* obj) { if(!QueueEmpty(&obj->q1)) { return QueueBack(&obj->q1); }else{ return QueueBack(&obj->q2); } }
第六步 判空
这步就很简单，只需要判断1和2是否都为空，都为空即空
bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2); }
第七步 释放
这里要依次释放销毁，类似套娃
void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); free(obj); }
源码
typedef int QDateType; typedef struct QueueNode { struct QueueNode* next; QDateType date; }QNode; typedef struct Queue { QNode* head; QNode* tail; int size; }Queue; //初始化 void QueueInit(Queue* pq); //销毁 void QueueDestroy(Queue* pq); //队进 void QueuePush(Queue* pq, QDateType x); //队出 void QueuePop(Queue* pq); //判断为空 bool QueueEmpty(Queue* pq); //个数 int QueueSize(Queue* pq); //队尾 QDateType QueueBack(Queue* pq); //对头 QDateType QueueFront(Queue* pq); //初始化 void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; pq->size = 0; } //销毁 void QueueDestroy(Queue* pq) { assert(pq); //两个结构体依次销毁 先销毁QNode QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } //再置空Queue pq->head = pq->tail = NULL; pq->size = 0; } //队进 void QueuePush(Queue* pq, QDateType x) { assert(pq); //开辟新节点 QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } //赋值 newnode->next = NULL; newnode->date = x; //判断是否为空 if (pq->head == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } //个数要++ pq->size++; } //队出 void QueuePop(Queue* pq) { assert(pq); assert(pq->head!=NULL); //只有一个节点 if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { //保存下一位 QNode* next = pq->head->next; free(pq->head); pq->head = next;//迭代 } //个数要-- pq->size--; } //判断为空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->size == 0; } //大小 int QueueSize(Queue* pq) { assert(pq); return pq->size; } //队尾 QDateType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->date; } //对头 QDateType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->date; } typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack*pst = ( MyStack*)malloc(sizeof( MyStack)); if(pst==NULL) { perror("malloc fail"); return NULL; } QueueInit(&pst->q1); QueueInit(&pst->q2); return pst; } void myStackPush(MyStack* obj, int x) { if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1,x); }else{ QueuePush(&obj->q2,x); } } int myStackPop(MyStack* obj) { Queue*emptyQ = &obj->q1; Queue*nonemptyQ = &obj->q2; if(!QueueEmpty(&obj->q1)) { emptyQ = &obj->q2; nonemptyQ=&obj->q1; } //倒数据 while(QueueSize(nonemptyQ)>1) { QueuePush(emptyQ,QueueFront(nonemptyQ)); QueuePop(nonemptyQ); } //记录删除值 删掉 int top = QueueFront(nonemptyQ); QueuePop(nonemptyQ); 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) { QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); free(obj); }
以上便是本文所有内容了，如有错误请各位大佬不吝赐教，感谢留言
