题目：
Implement the following operations of a queue using stacks.
- push(x) — Push element x to the back of queue.
- pop() — Removes the element from in front of queue.
- peek() — Get the front element.
- empty() — Return whether the queue is empty.
分析：
使用栈来实现队列的数据结构。
2个栈，stack1用来入队，stack2用来出队。
出队时，如果stack2不为空，则stack2直接弹出一个元素；如果为空，则stack1弹出所有元素，stack1每弹出一个元素就压入stack2，最后stack2再弹出一个元素。
代码：
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
import java.util.Stack; class MyQueue { private Stack<Integer> stack1; private Stack<Integer> stack2; public MyQueue(){ stack1 = new Stack<Integer>(); stack2 = new Stack<Integer>(); } // Push element x to the back of queue. public void push(int x) { stack1.push(x); } // Removes the element from in front of queue. public void pop() { if(stack2.isEmpty()){ while(!stack1.isEmpty()){ stack2.push(stack1.pop()); } } stack2.pop(); } // Get the front element. public int peek() { if(stack2.isEmpty()){ while(!stack1.isEmpty()){ stack2.push(stack1.pop()); } } return stack2.peek(); } // Return whether the queue is empty. public boolean empty() { return stack1.isEmpty() && stack2.isEmpty(); } } |