應用題 用Stack實作Queue_Leetcode #232 Implement Queue using Stacks

這題的題目在這裡

題目敘述

題目會給我們一組定義好的Queue 佇列的介面，要求底層用兩個stack來實現。

也就是說，要求我們用兩個LIFO的stacks去實作出一個FIFO的Queue

測試範例

Example 1:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

約束條件

Constraints:

• 1 <= x <= 9
• At most 100 calls will be made to push, pop, peek, and empty.
• All the calls to pop and peek are valid.

Follow-up: Can you implement the queue such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.

演算法

關鍵點在於用LIFO的特質，去組合、實作出FIFO的功能。

其實可以這樣想，既然是LIFO，代表可以用第一個stack作為輸入的buffer，用第二個stack作為輸出的buffer。

這樣一來，每個元素等於依照順序進出了stack兩次，LIFO 再 LIFO，等價於 FIFO。

例如 輸入順序是 [1, 2, 3]，再逐一pop出來，再推入另一個stack，
此時變成[3, 2, 1]

這時候再依序pop出來，就會得到1, 2, 3，剛好就是我們原本想要的FIFO輸出順序。

程式碼

class MyQueue:

def __init__(self):
　"""
　Initialize your data structure here.
　"""
　self.inbox = []
　self.outbox = []
　
　

def push(self, x: int) -> None:
　"""
　Push element x to the back of queue.
　"""
　self.inbox.append( x )
　

def pop(self) -> int:
　"""
　Removes the element from in front of queue and returns that element.
　"""

　self.peek()
　return self.outbox.pop()
　
　
def peek(self) -> int:
　"""
　Get the front element.
　"""
　
　if len( self.outbox ) != 0:
　　return self.outbox[-1]
　
　else:
　　
　　while len(self.inbox) != 0:
　　　
　　　top_of_inbox = self.inbox.pop()
　　　self.outbox.append( top_of_inbox )
　
　　return self.outbox[-1]
　

def empty(self) -> bool:
　"""
　Returns whether the queue is empty.
　"""
　
　if len(self.inbox) + len(self.outbox) == 0:
　　return True
　else:
　　return False

複雜度分析

時間複雜度: amortized O(1)

init(), push(), empty() 函數的時間複雜度為O(1) 。

peek() , pop() 在每次呼叫中，會把原本的順序再翻轉一次，從LIFO轉為FIFO，平均攤銷時間複雜度為O (1)

空間複雜度: O(n)

stack所耗用最大長度就是元素總數。

關鍵知識點

關鍵點在於用LIFO的特質，去組合、實作出FIFO的功能。

每個元素依照順序進出了stack兩次，LIFO 再 LIFO，等價於 FIFO。

Reference:

[1] Python/JS/Java/C++ sol by two stacks [w/ Comment] - Implement Queue using Stacks - LeetCode