題目敘述
題目會給我們一組定義好的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
100calls will be made topush,pop,peek, andempty. - All the calls to
popandpeekare 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
