用两个栈实现一个队列&用两个队列实现一个栈

1. 两个栈实现一个队列

栈的先进后出特性非常适合处理多层闭合问题，比如括号处理、函数的递归调用、树的遍历、汉诺塔等。

Stack_Queue

要用两个栈实现一个队列，则需要两个容量相等的堆栈（不等的话合也可以，就是判断逻辑比较复杂，而且容量受较小堆栈的容量限制），记作S1和S2，堆栈容量记作c。

入队

如果S1未满，则push到S1；
如果S1满了，且S2为空，则将S1所有元素push到S2，再尝试push到S1；
如果以上条件都不成立，则队列已满。

出队

如果S2非空，则从S2中pop元素；
如果S2为空，且S1非空，则将S1所有元素push到S2，再尝试从S2中pop元素；
如果以上条件都不成立，则队列为空。

队列长度

这个队列的长度等于S1 S2深度之和，故最大长度为2c，但是存在长度不到2c就写满的情况。因为S1和S2之间必须保证数据的顺序性，所以每次S1和S2交换数据时必须保证S2为空且S1数据全部移动过去。即便队列长度没有达到2c，如果S1写满且无法移动到S2，仍然认为队列已满。

2. 两个队列实现一个栈

队列的结构则相对比较简单，先进的元素先出来，在进程、线程、消息管理等场景下经常用到队列。
要用 两个队列实现一个栈，则需要两个容量相等的队列（不等的话合成的堆栈的容量等于最小队列的容量），记作Q1和Q2，队列容量记作c。

Queue_Stack

入栈

取一个非空队列；
如果队列满了，则堆栈已满；
否则push_back一个元素（入栈）。

出栈

如果两个队列都为空，则堆栈为空；
否则取一个非空队列，将除队尾的那个元素全部pop_front到另一个队列，最后后将队尾元素取出（出栈）。

堆栈深度

堆栈深度即为c。