DSA 練功筆記 (22)：Implement Stack using Queues
理解題目
最多只用 2 個 queue 實作一個 last-in-first-out (LIFO) stack，這個 stack 必須支援所有 stack 常用的 function，舉例：push, top, pop, empty。
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題目限制
根據語言，可以使用 list or dequeue 來實作，只要是用 queue 的標準操作
思路與解法
題目已經給你基本 class 跟對應的方法，只要實作題目提到的 queue 的標準操作方法模擬 LIFO stack 就行。
從最簡單的開始，empty 方法就是判斷 queue 裡面是不是空的，只要判斷長度就解決了。push 方法因為我們是用 Go slice 來模擬 queue，只要 append 就可以模擬 push 行為。
不過 pop 跟 top 操作就讓人疑惑了，stack 的 pop 是 LIFO，直接對目前 queue 的最後一個 element 做 pop 或者 top 都是 LIFO 不滿足 queue FIFO 的特性，也就是要想方法讓操作 queue 的 pop 跟 top 的同時，滿足 queue FIFO 跟 stack LIFO 的特性。
於是我就想到每次 top 時先用反轉字串的 swap 方式把 elements 反過來，這樣 pop 時就能把第一個 element 彈出來，後來出現一個問題是如果執行 top 跟 pop 的順序不同就會影響到結果，swap 反序的做法也會讓中間的結果錯誤，然後每次 pop 前都要依賴 top 操作這個方式也覺得稍微複雜不直覺。
最後找到每次 push 操作都把 element 放到最前面 (front of queue)的寫法更好理解，而且所有 queue 操作都可以滿足 queue 的 FIFO 跟 stack 的 LIFO。
type MyStack struct {
queue []int
}
func Constructor() MyStack {
return MyStack{
queue: make([]int, 0),
}
}
func (ms *MyStack) Push(x int) {
ms.queue = append(ms.queue, x)
// Bring the last element to the front of queue to simulate the LIFO stack.
for i := 0; i < len(ms.queue)-1; i++ {
ms.queue = append(ms.queue, ms.queue[0])
ms.queue = ms.queue[1:]
}
}
func (ms *MyStack) Pop() int {
popValue := ms.queue[0]
ms.queue = ms.queue[1:]
return popValue
}
func (ms *MyStack) Top() int {
return ms.queue[0]
}
func (ms *MyStack) Empty() bool {
return len(ms.queue) == 0
}
/* Execution:
*
* stack := Constructor()
* stack.push(1)
* stack.push(2)
* stack.push(3)
* stack.top()
* stack.pop()
* stack.empty()
*/Big O notation
- Time Complexity: O(n), because push function brings the last element to the front of queue with the loop that the number of execution depends on the number of elements.
- Space Complexity: O(1), even a loop is used to bring the last element to the front in each push function, the space complexity of push operation is still considered O(1) because the amount of additional space used is constant, not proportional to the size of the input.
Note
雖然實作結構的題目看起來比較直覺，貼近真實的應用情境，對數據結構的底層操作還是跟直接做應用有點不同，需要夠深入的了解數據結構的特性。
