如图所示,我们先往栈内压入一个元素a。由于两个队列现在都是空,我们可以选择把a插入两个队列中的任一个。我们不妨把a插入queue1。接下来继续网栈内压入b,c两个元素。我们把它们都插入queue1。这个时候 queue1包含3个元素a,b,c其中a位于队列的头部,c位于队列的尾部。
现在我们考虑从栈内弹出一个元素。根据栈的后入先出的原则,最后被压入栈的c应该最先被弹出。由于c位于queue1的尾部,而我们每次只能从队列的头部删除元素,因此我们可以从queueu中依次删除a/b/c并插入到queue2中,再从queue1中删除c。这就相当于从栈中弹出元素c了。我们可以用同样的方法从栈内弹出元素b。
接下来我们考虑从栈内压入一个元素d.此时queue1已经有了一个元素,我们就把d插入到queue1的尾部。如果我们再从栈内弹出一个元素,此时被弹出的应该是最后被压入的d.由于d位于queue1的尾部,我们只能先从头部删除 queue1的元素并插入到queue2,直到queue1中遇到d再直接把它删除。如果所示:
import java.util.LinkedList;public class StackByTwoQueue { private LinkedListqueue1 = new LinkedList (); private LinkedList queue2 = new LinkedList (); /* * 两个队列实现一个栈 * pop完成出栈操作,push完成入栈操作 */ public void push(String obj) { if(queue1.isEmpty()){ queue2.add(obj); } if(queue2.isEmpty()){ queue1.add(obj); } } public String pop() { //两个栈都为空时,没有元素可以弹出 if (queue1.isEmpty()&&queue2.isEmpty()) { try { throw new Exception("stack is empty"); } catch (Exception e) { } } if(queue1.isEmpty()){ while(queue2.size()>1){ queue1.add(queue2.poll()); } return queue2.poll(); } if(queue2.isEmpty()){ while(queue1.size()>1){ queue2.add(queue1.poll()); } return queue1.poll(); } return null; } public static void main(String[] args) { StackByTwoQueue stack = new StackByTwoQueue(); for(int i=0;i<10;i++){ stack.push(i+""); } for(int i=0;i<20;i++){ System.out.println(stack.pop()); } } }