题目描述
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. Notes: You must use only standard operations of a stack – which means only push to top, peek/pop from top, size, and is empty operations are valid. Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack. You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).
题目大意就是让我们用栈操作实现一个队列，并且只能运用栈的标准操作，例如peek/pop push 等。思路是：用两个栈s1,s2来实现，其中s1用来压入栈，s2用来弹出栈。 例如 进栈元素先后顺序为 a,b,c,d , s1 从栈顶到栈底为 d,c,b,a ,按照队列取队头的操作，应该出a, 此时先将 s1 中的元素运用 pop操作依次出栈并压入 s2中，压入完毕后 s2 从栈顶到栈底 为 a,b,c,d 那么s2直接弹出 a就可以了。我们只要维护s2栈顶元素始终是队头元素就可以了。
注意：当需要取队头元素，只有当s2为空时，我们才需要 将s1的元素弹出压入s2中，否则直接取s2 栈顶元素作为队头元素即可。
Java 算法实现如下：
public class MyQueue { private Stack<Integer> s1; private Stack<Integer> s2; /** Initialize your data structure here. */ public MyQueue() { s1=new Stack<Integer>(); s2=new Stack<Integer>(); } /** Push element x to the back of queue. */ public void push(int x) { s1.push(x); } /** Removes the element from in front of queue and returns that element. */ public int pop() { if(s2.size()==0){ while(s1.size()>0) s2.push(s1.pop()); } return s2.pop(); } /** Get the front element. */ public int peek() { if(s2.size()==0){ while(s1.size()>0) s2.push(s1.pop()); } return s2.peek(); } /** Returns whether the queue is empty. */ public boolean empty() { return s1.size()==0 && s2.size()==0; } } /** * Your MyQueue object will be instantiated and called as such: * MyQueue obj = new MyQueue(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.peek(); * boolean param_4 = obj.empty(); */