一、今日學習目標

今天學習Stack（堆疊）的概念，並了解LIFO（Last In, First Out，後進先出）的特性，以及如何運用Stack處理具有階層或對稱關係的字串配對問題。

二、題目介紹

LeetCode 20： Valid Parentheses

給定一個僅包含字元 '(', ')', '{', '}', '[' 和 ']' 的字串 s，判斷該字串是否有效。

有效字串需滿足以下條件：

1. 左括號必須用相同類型的右括號閉合。
2. 左括號必須以正確的順序閉合。
3. 每個右括號都有一個對應的同類型左括號。

範例輸入：s = "()[]{}"

範例輸出：true

三、解題思路

由於括號必須按照「後開啟的括號要先閉合」的順序配對，這正好符合Stack LIFO（後進先出）的特性。

解題步驟如下：

1. 建立一個Stack用來儲存尚未配對的左括號。
2. 走訪字串中的每個字元：
   • 若為左括號 ('(', '{', '[')：將其壓入（Push）Stack中。
   • 若為右括號 (')', '}', ']')：
     • 先檢查Stack是否為空，若為空代表這個右括號沒有對應的左括號，回傳 false。
     • 從Stack頂端取出（Pop）最近一個左括號，檢查是否與當前右括號匹配。若不匹配，回傳 false。
3. 走訪完畢後，檢查 Stack 是否完全清空：
   • 若 Stack 為空，代表所有左括號都順利配對完成，回傳 true。
   • 若 Stack 不為空，代表有未閉合的左括號，回傳 false。

四、Java實作

五、Python實作

六、時間與空間複雜度
Java：

Time Complexity：O(n)

• 只需走訪一次長度為n的字串，每個括號最多進入Stack一次並移除一次，因此整體時間複雜度為O(n)。

Space Complexity：O(n)

• 最壞情況下，所有字元都是左括號，需要將全部元素儲存在Stack中，因此額外空間複雜度為O(n)。

Python：

Time Complexity：O(n)

• 只需走訪一次字串，每個括號最多進行一次加入或移除操作，因此整體時間複雜度為O(n)。

Space Complexity：O(n)

• 最壞情況下，所有字元都是左括號，需要將所有元素儲存在List中，因此額外空間複雜度為O(n)。

七、Java 與 Python 解法比較

1. Stack的實作方式：

• Java使用Deque<Character>搭配ArrayDeque實作Stack，透過push()與pop()操作資料。
• Python使用內建List實作Stack，透過append()加入元素，以及pop()移除最後一個元素。

2. 資料結構操作：

• Java的Deque提供push()、pop()、peek()等Stack常用操作。
• Python List可以透過append()和pop()簡單模擬Stack，因此程式碼較為簡潔。

3. 括號配對方式：

• Java透過條件判斷確認左、右括號是否正確配對。
• Python使用Dictionary儲存括號對應關係，使判斷邏輯更加簡潔。

4. 語法差異：

• Java需要明確宣告資料型別，例如Deque<Character>。
• Python不需要事先宣告List的元素型別，因此實作較為簡潔。

八、實作結果

LeetCode測試結果：Accepted

九、今日學習心得

今天學習到Stack（堆疊）的基本概念，以及LIFO（Last In, First Out）的特性。

透過Valid Parentheses這道題目，可以了解到Stack很適合處理具有「先進後出」特性的問題。遇到左括號時先存入Stack，遇到右括號時再取出最後一個加入的左括號進行配對。

這次實作也讓我了解到，雖然Java與Python都可以使用Stack解決相同問題，但兩種語言的資料結構操作方式不同。Java可以使用Deque搭配ArrayDeque，而Python則可以直接使用List搭配append()和pop()。

透過Java與Python的實際比較，我更加了解Stack的運作方式，也體會到選擇適合的資料結構可以讓程式的邏輯更加清楚。