232. Implement Queue using Stacks - Easy

前往題目

這題做過，照搬一下

想法

• 這題一開始題目條件沒看清楚所以想破頭腦也想不出一個stack怎麼實作queue
• 看了解法覺得調用的方法就是個死循環，放到vscode一步一步看馬上就知道原因了
• 是因為有些方法是直接調用stack的，所以其實很簡單
• 的確是Easy的題目，但沒想通就永遠都是hard

思路

• 這裡使用兩個stack，一個input負責儲存資料，一個output負責還原成queue然後做相應動作

Push

• 直接push到input stack就好

Pop

• 使用自己寫的peek拿到output的top，就是queue的head
• 然後再用stack內建的pop把output的top去掉

Peek

• 確保output沒東西，有的話直接peek top是甚麼就完成peek了
• 沒東西的話就從input把所有東西push到output，這樣output就是一個queue了，因為input的順序會被反轉

Empty

• 直接調用stack內建的empty，兩個stack都是空的就是空

Code

class MyQueue {
    
    Stack<Integer> input, output;

    public MyQueue() {
        input = new Stack<>();
        output = new Stack<>();
    }
    
    public void push(int x) {
        input.push(x);
    }
    
    public int pop() {
        int head = peek();
        output.pop();
        return head;
    }
    
    public int peek() {
        if(output.empty()){
            while(!input.empty()){
                output.push(input.pop());
            }
        }
        return output.peek();
    }
    
    public boolean empty() {
        return input.empty() && output.empty();
    }
}

2023/12/17

• 大致上沒寫出來🤣但至少記得要用兩個stack，只是忘了一個當input一個當output

2024/08/05

• 寫出來了，剩一點小bug