應用題 用Queue實作Stack_Leetcode #225 Implement Stack using Queues

Holly Stratton on Unsplash

這題的題目在這裡

題目敘述

也就是說，要求我們用一個或兩個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 100 calls will be made to push, pop, top, and empty.
• All the calls to pop and top are 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