As the title described, you should only use two stacks to implement a queue‘s actions.
The queue should support push(element), pop() and top() where pop is pop the first(a.k.a front) element in the queue.
Both pop and top methods should return the value of first element.
For push(1), pop(), push(2), push(3), top(), pop(), you should return 1, 2 and 2
implement it by two stacks, do not use any other data structure and push, pop and top should be O(1) by AVERAGE.
Solution:
1 public class Solution { 2 private Stack<Integer> stack1; 3 private Stack<Integer> stack2; 4 5 public Solution() { 6 stack1 = new Stack<Integer>(); 7 stack2 = new Stack<Integer>(); 8 } 9 10 public void push(int element) { 11 stack2.push(element); 12 } 13 14 private void shuffle(){ 15 while (!stack2.isEmpty()) 16 stack1.push(stack2.pop()); 17 } 18 19 public int pop() { 20 if (stack1.isEmpty()) shuffle(); 21 return stack1.pop(); 22 } 23 24 public int top() { 25 if (stack1.isEmpty()) shuffle(); 26 return stack1.peek(); 27 } 28 }
LintCode-Implement Queue by Stacks
原文：http://www.cnblogs.com/lishiblog/p/4196912.html