題目敘述
題目會給我們一組定義好的Stack 堆疊的介面，要求底層用兩個或一個Queue來實現。也就是說，要求我們用一個或兩個FIFO的Queues去實作出一個LIFO的Stack
測試範例
Example 1:
Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]
Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False
約束條件
1 <= x <= 9- At most
100calls will be made topush,pop,top, andempty. - All the calls to
popandtopare valid.
Follow-up: Can you implement the stack using only one queue?
演算法
關鍵點在於用FIFO的特質，去組合、實作出LIFO的功能。
其實可以這樣想，既然是FIFO，代表要想盡辦法把剛剛推入最新的元素，把他挪到底層Queue的頭部，這樣下次pop時，才能取到剛剛那筆最新的元素值。
因此，每次插入的時候，除了推入元素之外，還要額外多付出O(n)調整元素位置的成本。
例如:
原本是Q[2, 1] 現在，推入3，變成Q[2,1,3]
我們要接著馬上把3調整到Queue的頭部，也就是說，取出2, 1，把他們重新放到3的後面，調整成Q[3,2,1]。
這樣，下次在pop的時候，才能從Queue的頭部取出對應最新的元素值 3
程式碼
from collections import deque
class MyStack:
def __init__(self):
""" Initialize your data structure here. """
# python natively support double-ended queue
self.queue = deque()
def push(self, x: int) -> None:
""" Push element x onto stack. """
# push new element into queue's tail
self.queue.append(x)
# make new element on the head position by rotation
for _ in range(len(self.queue)-1):
self.queue.append( self.queue.popleft() )
def pop(self) -> int:
""" Removes the element on top of the stack and returns that element. """
# pop head element of queue
return self.queue.popleft()
def top(self) -> int:
""" Get the top element. """
# return head element of queue
return self.queue[0]
def empty(self) -> bool:
""" Returns whether the stack is empty. """
return (not self.queue)
複雜度分析
時間複雜度:
init(), pop(), top(), empty() 函數的時間複雜度為O(1) 。
push() 在每次呼叫中，會把原本的順序再調整一次，把最新元素從queue的尾巴，調整到queue的頭部，所耗費成本為O(n)
空間複雜度: O(n)
底層queue所耗用最大長度就是元素總數。
關鍵知識點
關鍵點在於用FIFO的特質，去組合、實作出LIFO的功能。
每個元素依照順序推入queue，再從FIFO queue的尾巴，調整移動到FIFO queue的頭部，等價於 stack LIFO的順序。
Reference:
[1] Python sol by queue operation. [w/ Comment] - Implement Stack using Queues - LeetCode
