題目出處

232. Implement Queue using Stacks

難度

easy

題目分類

Stack, Design, Queue

個人筆記

這篇比較偏程式架構設計，我專注在分析答案，就不特別解。

算法說明

「兩個 Stack 可以拼出一個 Queue」，
對於這個問題我們可以這樣想，
Stack 作為 FILO 的資料結構，先進入的資料會放在底層
而當有兩個 Stack，FILO，再一次 FILO (此時位於底層的資料，就會被拿上來到頂層)，
總合起來就會得到 FIFO 了！

研究別人的解法

這裡我研究的解法是：Share my python solution (32ms)

class MyQueue:
    def __init__(self):
        self.inStack = []
        self.outStack = []

    def push(self, x):
        while self.outStack:
            self.inStack.append(self.outStack.pop())
        self.outStack.append(x)
        while self.inStack:
            self.outStack.append(self.inStack.pop())

    def pop(self):
        return self.outStack.pop()

    def peek(self):
        return self.outStack[-1]

    def empty(self):
        return (not self.outStack and not self.inStack)


# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

初始化就是兩個 Stack，分成 in, out 兩組，
「記得我們的大概念就是要兩個 FILO + FILO = FIFO」

• init：初始化兩組 inStack, outStack
• push：放一個資料進入 inStack
• pop：從 outStack 拿出一筆資料，在這之前應該會需要經過把 inStack 的資料全部以 FILO 放入 outStack
• peek：與 pop 類似，但 pop 會需要回傳並刪除 Queue 中的內容，而 peek 只是我們想看看即將被 pop 的項目是什麼，而不做 pop 的動作。
• empty：我們需要同時檢查 inStack, outStack 是否為空

移動過程：作為移動 inStack 的資料內容至 outStack 的內容使用，這裡有個重點「outStack此時必須為空」，因為我們可以將每次的 move 視為一組，而當這組的 Queue 順序順利清空前，「不能」再放新資料進去，否則會造成順序錯誤。

圖例

下圖我們做的步驟是

• 先放入 123
• 準備拿出 123，但沒一次全拿
• 放入 456

Reference

• Share my python solution (32ms)