一、队列实现栈核心算法概述

之前已经描述过了用栈实现队列的功能，见栈系列之-实现队列，那么同样队列也可以用来实现栈，而且原理也不复杂，本文主要讲解这个。和栈实现队列的算法一样，队列实现栈需要两个队列。队列是一种先进先出的数据结构，但是栈是先进后出的数据结构，其实你仔细想就会发现，两个队列，不管怎么导入导出，也无法颠倒其进入队列的顺序。这正是队列的特性决定的。

队列实现栈，其实进队列操作和栈是一样的，关键就是出队列的时候，栈是从栈顶弹栈出去，而队列是从队头出去，要用队列实现这一点，既然队列的导入导出做不到，那么只能是找到要弹栈出去的元素，然后返回，其他元素在一次插入到另外一个队列当中。用图例解释一下这一段话。

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