一、队列实现栈核心算法概述
之前已经描述过了用栈实现队列的功能，见栈系列之-实现队列，那么同样队列也可以用来实现栈，而且原理也不复杂，本文主要讲解这个。和栈实现队列的算法一样，队列实现栈需要两个队列。队列是一种先进先出的数据结构，但是栈是先进后出的数据结构，其实你仔细想就会发现，两个队列，不管怎么导入导出，也无法颠倒其进入队列的顺序。这正是队列的特性决定的。
队列实现栈，其实进队列操作和栈是一样的，关键就是出队列的时候，栈是从栈顶弹栈出去，而队列是从队头出去，要用队列实现这一点，既然队列的导入导出做不到，那么只能是找到要弹栈出去的元素，然后返回，其他元素在一次插入到另外一个队列当中。用图例解释一下这一段话。
1：假设Queue1现在依次进去1,2,3,4，四个元素
image.png
2：现在要出队一个元素，就将Queue1的所有元素都依次放到Queue2上，直至
到Queue1的最后一个元素，直接返回就好了。
image.png
其实上述只是一个出队的过程，如果是连续出队呢？重复刚才的步骤就好了，其实就是将Queue2的元素导入Queue1，然后将3出队。那么如果是现在有元素要入队呢？如果直接插入到Queue1很明显，元素的次序就乱了，所以还是只能把元素插入到Queue2.
综上所述，做个总结，也是算法的核心：
- 插入操作，如果两队列都为空，则默认插入Queue1，否则插入非空的队列。
- 出队操作，将非空的那个队列的元素依次插入到另外一个为空的队列当中，直至
最后一个元素，然后返回。
二、队列实现栈代码-java
import java.util.LinkedList;
import java.util.Queue;
public class QueueStack<E> {
/**
* 使用两个队列来模拟栈的行为
*/
Queue<E> queue1;
Queue<E> queue2;
public QueueStack(){
queue1 = new LinkedList<E>();
queue2 = new LinkedList<E>();
}
public void QueuePush(E elem){
if (queue1.isEmpty() && queue2.isEmpty()){
// 当两个队列都是空时，就默认往queue1增加数据
queue1.add(elem);
}else if (!queue1.isEmpty() && queue2.isEmpty()){
queue1.add(elem);
}else if (queue1.isEmpty() && !queue2.isEmpty()){
queue2.add(elem);
}
}
public E QueuePop(){
if (!queue1.isEmpty()){
// queue1不为空
E tmpElem;
while (queue1.size() != 0){
tmpElem = queue1.remove();
if (queue1.isEmpty()){
return tmpElem;
}else{
queue2.add(tmpElem);
}
}
}else {
// queue2不为空
E tmpElem;
while (queue2.size() != 0){
tmpElem = queue2.remove();
if (queue2.isEmpty()){
return tmpElem;
}else{
queue1.add(tmpElem);
}
}
}
return null;
}
public void toStr(){
System.out.println(queue1.toString());
System.out.println(queue2.toString());
}
public static void main(String[] args) {
}
}
三、图例解释算法运行过程
1:假设Queue1有1,2,3,4四个元素，现在要出队，如图：
image.png
2：然后现在要进队元素5，如图：
image.png
3：然后要出队元素5，如图：
image.png
