0232. 用棧實現隊列 · ttttt

# 0232. 用棧實現隊列 ## 題目地址(232. 用棧實現隊列) <https://leetcode-cn.com/problems/implement-queue-using-stacks/> ## 題目描述 ``` <pre class="calibre18">``` 使用棧實現隊列的下列操作： push(x) -- 將一個元素放入隊列的尾部。 pop() -- 從隊列首部移除元素。 peek() -- 返回隊列首部的元素。 empty() -- 返回隊列是否為空。示例: MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // 返回 1 queue.pop(); // 返回 1 queue.empty(); // 返回 false 說明: 你只能使用標準的棧操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的語言也許不支持棧。你可以使用 list 或者 deque（雙端隊列）來模擬一個棧，只要是標準的棧操作即可。假設所有操作都是有效的（例如，一個空的隊列不會調用 pop 或者 peek 操作）。 ``` ``` ## 前置知識 - [棧](https://github.com/azl397985856/leetcode/blob/master/thinkings/basic-data-structure.md) ## 公司 - 阿里 - 騰訊 - 百度 - 字節 - bloomberg - microsoft ## 思路這道題目是讓我們用棧來模擬實現隊列。我們知道棧和隊列都是一種受限的數據結構。棧的特點是只能在一端進行所有操作，隊列的特點是只能在一端入隊，另一端出隊。在這里我們可以借助另外一個棧，也就是說用兩個棧來實現隊列的效果。這種做法的時間復雜度和空間復雜度都是O(n)。由于棧只能操作一端，因此我們peek或者pop的時候也只去操作頂部元素，要達到目的我們需要在push的時候將隊頭的元素放到棧頂即可。因此我們只需要在push的時候，用一下輔助棧即可。具體做法是先將棧清空并依次放到另一個輔助棧中，輔助棧中的元素再次放回棧中，最后將新的元素push進去即可。比如我們現在棧中已經是1，2，3，4了。我們現在要push一個5. push之前是這樣的： ![](https://img.kancloud.cn/1c/81/1c8161f262fca7ae9530a82591d9a823_434x223.jpg) 然后我們將棧中的元素轉移到輔助棧： ![](https://img.kancloud.cn/1d/96/1d9608bc6cc17ba6fed5fcf94ece4acb_313x264.jpg) 最后將新的元素添加到棧頂。 ![](https://img.kancloud.cn/bc/ed/bced05dbd68c75cbf7b23e1f42284611_353x252.jpg) 整個過程是這樣的： ![](https://img.kancloud.cn/3a/35/3a35b3010dc9e00945cd052e33d8284e_700x467.jpg) ## 關鍵點解析 - 在push的時候利用輔助棧(雙棧) ## 代碼 - 語言支持：JS, Python, Java Javascript Code: ``` <pre class="calibre18">``` /* * @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: ``` <pre class="calibre18">``` 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 ``` <pre class="calibre18">``` 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(1)O(1)O(1) - 空間復雜度：O(1)O(1)O(1) ## 擴展 - 類似的題目有用隊列實現棧，思路是完全一樣的，大家有興趣可以試一下。 - 棧混洗也是借助另外一個棧來完成的，從這點來看，兩者有相似之處。 ## 延伸閱讀實際上現實中也有使用兩個棧來實現隊列的情況，那么為什么我們要用兩個stack來實現一個queue？其實使用兩個棧來替代一個隊列的實現是為了在多進程中分開對同一個隊列對讀寫操作。一個棧是用來讀的，另一個是用來寫的。當且僅當讀棧滿時或者寫棧為空時，讀寫操作才會發生沖突。當只有一個線程對棧進行讀寫操作的時候，總有一個棧是空的。在多線程應用中，如果我們只有一個隊列，為了線程安全，我們在讀或者寫隊列的時候都需要鎖住整個隊列。而在兩個棧的實現中，只要寫入棧不為空，那么`push`操作的鎖就不會影響到`pop`。 - [reference](https://leetcode.com/problems/implement-queue-using-stacks/discuss/64284/Do-you-know-when-we-should-use-two-stacks-to-implement-a-queue) - [further reading](https://stackoverflow.com/questions/2050120/why-use-two-stacks-to-make-a-queue/2050402#2050402) 更多題解可以訪問我的LeetCode題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經37K star啦。關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)