论述题 13.  请用两个队列实现栈的先进后出的操作,希望该栈的push/pop时间复杂度尽量小。请写出push/pop的代码。
【正确答案】假设使用队列q1与队列q2模拟栈s,q1为入队列,q2为出队列。
   实现思路如下:可以认为队列q1提供压栈的功能,队列q2提供弹栈的功能。
   当要压栈时,入队列q1即可,而当要弹栈时,出队列则需要分为以下两种情况考虑:
   1)如果队列q1中只有一个元素,那么让队列q1中的元素出队列并输出即可。
   2)如果队列q1中有多于一个元素,那么让队列q1中所有元素出队列,入队列q2,最后一个元素不入队列q2,输出该元素,然后将队列q2所有元素入队列q1。
   实现代码如下:
   import java.util.Queue;
   import java.util.concurrent.LinkedBlockingQueue;
   public class MyStack<T>
   {
   private Queue<T>q1=new LinkedBlockingQueue<T>();;
   private Queue<T>q2=new LinkedBlockingQueue<T>();
   public void push(T value)
   {
   q1.add(value);
   }
   public boolean empty()
   {
   if(q1.isEmpty())
   return true;
   else
   return false;
   }
   public T pop()
   {
   if(q1.size()=0)
   return null;
   else if(q1.size()=1)
   return q1.poll();
   else
   {
   while(q1.size()>1)
   q2.add(q1.poll());
   T result=-q1.poll();
   while(!q2.isEmpty())
   q1.add(q2.poll());
   return result;
   }
   }
   public static void main(String[]args)
   {
   MyStack<Integer>stack=new MyStack<Integer>();
   stack.push(1);
   stack.push(2);
   stack.push(3);
   System.out.println(stack.pop());
   stack.push(4);
   System.out.println(stack.pop());
   }
   }
   程序的运行结果为:
   3
   4
【答案解析】