/** * Initialize your data structure here. */var MyQueue = function () { this.pushstack = [] this.popstack = []};/** * Push element x to the back of queue. * @param {number} x * @return {void} */MyQueue.prototype.push = function (x) { this.pushstack.push(x)};/** * Removes the element from in front of queue and returns that element. * @return {number} */MyQueue.prototype.pop = function () { if (!this.popstack.length) { while (this.pushstack.length) { this.popstack.push(this.pushstack.pop()) } } return this.popstack.pop()};/** * Get the front element. * @return {number} */MyQueue.prototype.peek = function () { if (this.popstack.length) return this.popstack[this.popstack.length - 1] return this.pushstack[0]};/** * Returns whether the queue is empty. * @return {boolean} */MyQueue.prototype.empty = function () { return !this.pushstack.length && !this.popstack.length};
你只能使用标准的栈操作 — 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的、 （例如，一个空的队列不会调用 pop 或者 peek 操作）。
前置知识
栈
队列
思路
题目要求用栈的原生操作来实现队列，也就是说需要用到 pop 和 push
但是我们知道 pop 和 push 都是在栈顶的操作，而队列的 enque 和 deque 则是在队列的两端的操作，这么一看一个 stack 好像不太能完成。
/* * @lc app=leetcode id=232 lang=javascript * * [232] Implement Queue using Stacks *//** * Initialize your data structure here. */var MyQueue = function() { // tag: queue stack array this.stack = []; this.helperStack = [];};/** * Push element x to the back of queue. * @param {number} x * @return {void} */MyQueue.prototype.push = function(x) { let cur = null; while ((cur = this.stack.pop())) { this.helperStack.push(cur); } this.helperStack.push(x); while ((cur = this.helperStack.pop())) { this.stack.push(cur); }};/** * Removes the element from in front of queue and returns that element. * @return {number} */MyQueue.prototype.pop = function() { return this.stack.pop();};/** * Get the front element. * @return {number} */MyQueue.prototype.peek = function() { return this.stack[this.stack.length - 1];};/** * Returns whether the queue is empty. * @return {boolean} */MyQueue.prototype.empty = function() { return this.stack.length === 0;};/** * Your MyQueue object will be instantiated and called as such: * var obj = new MyQueue() * obj.push(x) * var param_2 = obj.pop() * var param_3 = obj.peek() * var param_4 = obj.empty() */
Python Code:
class MyQueue: def __init__(self): """ Initialize your data structure here. """ self.stack = [] self.help_stack = [] def push(self, x: int) -> None: """ Push element x to the back of queue. """ while self.stack: self.help_stack.append(self.stack.pop()) self.help_stack.append(x) while self.help_stack: self.stack.append(self.help_stack.pop()) def pop(self) -> int: """ Removes the element from in front of queue and returns that element. """ return self.stack.pop() def peek(self) -> int: """ Get the front element. """ return self.stack[-1] def empty(self) -> bool: """ Returns whether the queue is empty. """ return not bool(self.stack)# 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()
Java Code
class MyQueue { Stack<Integer> pushStack = new Stack<> (); Stack<Integer> popStack = new Stack<> (); /** Initialize your data structure here. */ public MyQueue() { } /** Push element x to the back of queue. */ public void push(int x) { while (!popStack.isEmpty()) { pushStack.push(popStack.pop()); } pushStack.push(x); } /** Removes the element from in front of queue and returns that element. */ public int pop() { while (!pushStack.isEmpty()) { popStack.push(pushStack.pop()); } return popStack.pop(); } /** Get the front element. */ public int peek() { while (!pushStack.isEmpty()) { popStack.push(pushStack.pop()); } return popStack.peek(); } /** Returns whether the queue is empty. */ public boolean empty() { return pushStack.isEmpty() && popStack.isEmpty(); }}/** * 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(); */
复杂度分析
时间复杂度：O(N)，其中 N 为 栈中元素个数，因为每次我们都要倒腾一次。
空间复杂度：O(N)，其中 N 为 栈中元素个数，多使用了一个辅助栈，这个辅助栈的大小和原栈的大小一样。
