题目
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
- void push(int x) 将元素 x 推到队列的末尾
- int pop() 从队列的开头移除并返回元素
- int peek() 返回队列开头的元素
- boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
- 你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
- 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
进阶：
- 你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。
解题
一个队列是 FIFO 的，但一个栈是 LIFO 的。这就意味着最新压入的元素必须得放在栈底。为了实现这个目的，我们首先需要把 s1 中所有的元素移到 s2 中，接着把新元素压入 s2。最后把 s2 中所有的元素弹出，再把弹出的元素压入 s1。
python解法
虽然py中的列表既能当作队列又能当作堆栈，但是这道题目的意思就是只能使用append()和pop()
class MyQueue: def __init__(self): """ Initialize your data structure here. """ self.stack1 = [] self.stack2 = [] def push(self, x: int) -> None: """ Push element x to the back of queue. """ while self.stack1: self.stack2.append(self.stack1.pop()) self.stack1.append(x) while self.stack2: self.stack1.append(self.stack2.pop()) def pop(self) -> int: """ Removes the element from in front of queue and returns that element. """ return self.stack1.pop() def peek(self) -> int: """ Get the front element. """ return self.stack1[-1] def empty(self) -> bool: """ Returns whether the queue is empty. """ return len(self.stack1)==0 # Your MyQueue object will be instantiated and called as such: # obj = MyQueue() # obj.push(x) # param_2 = obj.pop() # param_3 = obj.peek() # param_4 = obj.empty()
c++解法
由于c++中的stack ,pop并没有返回值，只能通过top来获得栈顶的元素,所以要比python实现多一点步骤.
class MyQueue { private: stack<int> stack1,stack2; public: /** Initialize your data structure here. */ MyQueue() { } /** Push element x to the back of queue. */ void push(int x) { while(!stack1.empty()){ stack2.push(stack1.top()); stack1.pop(); } stack1.push(x); while(!stack2.empty()){ stack1.push(stack2.top()); stack2.pop(); } } /** Removes the element from in front of queue and returns that element. */ int pop() { int top=stack1.top(); stack1.pop(); return top; } /** Get the front element. */ int peek() { return stack1.top(); } /** Returns whether the queue is empty. */ bool empty() { return stack1.empty(); } }; /** * 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(); * bool param_4 = obj->empty(); */
java解法
class MyQueue { Stack<Integer> st1; Stack<Integer> st2; public MyQueue() { st1=new Stack<>(); st2=new Stack<>(); } public void push(int x) { while(!st1.isEmpty()){ st2.push(st1.pop()); } st1.push(x); while(!st2.isEmpty()){ st1.push(st2.pop()); } } public int pop() { return st1.pop(); } public int peek() { return st1.peek(); } public boolean empty() { return st1.isEmpty(); } }
