两个队列实现一个栈

首先队列是先进先出，我们可以发现队列无论怎么倒，我们不能逆序一个队列。既然不能套用上题的解法，那么就得另谋出路，但是可以预知无非就是两个队列进行交替的入队出队操作，那么唯一要做的就是判断目前出队的值是否是按照放入元素顺序中最后放入的元素。 依旧画图举例

这里我们只看首次取出操作，那么需要注意一点， 如何判断哪一次取出操作后 QueueA 为空？

事实上作为 Queue 作为容器，我们可以通过事先定义好的方法 queue.size() 去判断一个队列中元素的个数，有人可能说这是犯规，其实不是的。题目中给出是让你用队列去实现，那么队列中公共 API 都是你可以用的。所以可以想象出下面的伪代码：

//如果 queueA 的大小不为 0 则循环取出元素
while(queueA.size() > 0){
    //被取出的元素
    int result = queueA.poll();
    // 这里注意我们取出元素后再去判断一次，队列是否为空，如果为空代表是最后一个元素
    if(queueA.size() != 0){
        queueB.add(result)
    }else{
        return result;
    }
}

上文我们只是说了一次取出操作，那么一次取出操作后，再次放入元素应该怎么放，我们似乎又遇到了困难。

我们应该先思考如果连续两次取出应该怎么操作，上面一次取出后 QueueA 空了，所以我们如果按照相同的思路将 B 中的元素倒入 A 中，那么将会得到 3 ，这看起来没什么问题。那么如果下一步进行的 push 操作，那么应该放入 QueueA 还是 QueueB 中才能保证元素先进后出的规则呢，很容易想到是放入 B 中。 那么总结一下操作要点：

• 任何时候两个队列总有一个是空的。
• 添加元素总是向非空队列中 add 元素。
• 取出元素的时候总是将元素除队尾最后一个元素外，导入另一空队列中，最后一个元素出队。

接上图我们开看第一次取出操作后可能的两种操作情况：

思路缕清楚了，那么时候写代码了：

public static class TwoQueueStack<E> {
   private Queue<E> queueA;
   private Queue<E> queueB;

   public TwoQueueStack() {
       queueA = new LinkedList<>();
       queueB = new LinkedList<>();
   }

   /**
    * 选一个非空的队列入队
    *
    * @param e
    * @return
    */
   public E push(E e) {
       if (queueA.size() != 0) {
           System.out.println("从 queueA 入队 " + e);
           queueA.add(e);
       } else if (queueB.size() != 0) {
           System.out.println("从 queueB 入队 " + e);
           queueB.add(e);
       } else {
           System.out.println("从 queueA 入队 " + e);
           queueA.add(e);
       }
       return e;
   }

   public E pop() {
       if (queueA.size() == 0 && queueB.size() == 0) {
           return null;
       }

       E result = null;
       if (queueA.size() != 0) {
           while (queueA.size() > 0) {
               result = queueA.poll();
               if (queueA.size() != 0) {
                   System.out.println("从 queueA 出队 并 queueB 入队 " + result);
                   queueB.add(result);
               }
           }
           System.out.println("从 queueA 出队 " + result);

       } else {
           while (queueB.size() > 0) {
               result = queueB.poll();
               if (queueB.size() != 0) {
                   System.out.println("从 queueB 出队 并 queueA 入队 " + result);
                   queueA.add(result);
               }
           }
           System.out.println("从 queueB 出队" + result);
       }
       return result;
   }
}