用队列实现栈
题目描述
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（
push、top、pop和empty）。实现
MyStack类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。
题目示例
示例：
输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]
解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
核心思路
1.入数据时，往不为空的队列入，保持另一个队列为空。
2.出数据时，依次出队头的数据，转移到另一个队列保存。直到剩下最后一个数据，用来出数据，则实现了栈的先进后出。
用C语言来解决这道题之前，应该先把队列的结构完成了。
解题过程
定义结构体
用队列实现栈，先定义一下这个栈的结构体类型。 题目中定义的是匿名结构体，这个栈的结构体包括了两个队列的结构体。（属于嵌套定义）
typedef struct { Queue q1; Queue q2; } MyStack;
创建栈结构体函数
这里的创建栈结构体的函数，是指调用这个函数之后，创建一个我们栈的结构体，再将这个结构体的地址返回。 但是它在函数内部，出了这个函数就会被销毁，要解决这个问题有两种方式：一是使用全局变量，二是申请空间。为了避免全局变量带来的一些问题，我们就用申请空间的方式来实现。 要注意的一点是：对这个结构体进行初始化时，要深入到它内部的两个队列结构体中，分别对两个队列进行初始化。 最终返回我们栈结构体的地址。
MyStack* myStackCreate() { MyStack* st = (MyStack*)malloc(sizeof(MyStack)); QueueInit(&st->q1); QueueInit(&st->q2); return st; }
入栈函数
按照之前的核心思路，将数据入到为空的队列中去，如果两个都为空则入到任意一个队列。
void myStackPush(MyStack* obj, int x) { if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1,x); } else { QueuePush(&obj->q2,x); } }
出栈函数
实现出栈函数，需要先将有数据的一方队列转移到空的另一方队列，保留最后一个数据。那么就要先判断哪一个队列为空，使用假设法：先假设q1为空，q2不为空，且创建两个变量记录下来，类似emptyQ和nonemptyQ；然后调用函数确认q1是否为空，为空则不变，不为空则交换q1和q2。 确认哪一方的队列为空之后，就可以对nonemptyQ(不为空的队列)进行数据转移了。
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); }
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列（核心思路、解题过程、完整题解）二：https://developer.aliyun.com/article/1530538
