Stack如圖所示是後進先出(Last In First Out)的資料結構，主要操作有push()、pop()

優點

1. 操作push()、pop()時間複雜度O(1)。
2. 適合模擬順序反轉過程

限制

1. 只能操作頂端元素，不能直接存取中間資料

let mut stack = Vec::new();

stack.push(5);
stack.push(10);
stack.push(-5);

println!("{:?}", stack.pop()); // Some(-5)
println!("{:?}", stack.last()); // Some(10)

stack常見的用途

1. 括號匹配
2. 模擬特定字元處理
3. 復原動作
4. 函式呼叫
5. 非遞迴的深度優先搜尋(Depth First Search)

括號匹配題

Leetcode 20. Valid Parentheses

題目：給一個字串s只有'(', ')', '{', '}', '[' 和']'字元，判斷是否符合下列條件。

1. 左括號必須由同種類的右括號關閉。

2. 左括號必須以正確的順序關閉。

3. 每個右括號都有一個相同類型的對應左括號。

限制

• 1 <= s.length <= 10^4

• s consists of parentheses only '()[]{}'.

做法：

1. 宣告一個stack

2. 依序掃過一遍字串，如果是左括號就先存在stack，遇到右括號再判斷目前最上層是否是同類的左括號，是的話移除stack中的左括號，不是就回傳false

3. 最後檢查是否還有沒配到的'(',, '{', '[' 。

impl Solution {
    pub fn is_valid(s: String) -> bool {
        //new a stack
        let mut stack=Vec::new();
        //loop s if '('、'{'、'[' push to stack else check top element whether same type or not

        for c in s.chars(){
            if (matches!(c,'('|'['|'{')){
                stack.push(c);
            } else if (
                matches!(c,')') && matches!(stack.last(),Some('(')) ||
                matches!(c,']') && matches!(stack.last(),Some('[')) ||
                matches!(c,'}') && matches!(stack.last(),Some('{'))
                ){
                stack.pop();
            } else {
                return false
            }
        }
        stack.is_empty()
    }
}

Leetcode 20. Valid Parentheses

題目：給一個字串s只有'(', ')', '{', '}', '[' 和']'字元，判斷是否符合下列條件。

1. 左括號必須由同種類的右括號關閉。

2. 左括號必須以正確的順序關閉。

3. 每個右括號都有一個相同類型的對應左括號。

限制

• 1 <= s.length <= 104

• s consists of parentheses only '()[]{}'.

做法：

1. 宣告一個stack

2. 依序掃過一遍字串，如果是左括號就先存在stack，遇到右括號再判斷目前最上層是否是同類的左括號，是的話移除stack中的左括號，不是就回傳false

3. 最後檢查是否還有沒配到的'(',, '{', '[' 。

impl Solution {
    pub fn is_valid(s: String) -> bool {
        //new a stack
        let mut stack=Vec::new();
        //loop s if '('、'{'、'[' push to stack else check top element whether same type or not

        for c in s.chars(){
            if (matches!(c,'('|'['|'{')){
                stack.push(c);
            } else if (
                matches!(c,')') && matches!(stack.last(),Some('(')) ||
                matches!(c,']') && matches!(stack.last(),Some('[')) ||
                matches!(c,'}') && matches!(stack.last(),Some('{'))
                ){
                stack.pop();
            } else {
                return false
            }
        }
        stack.is_empty()
    }
}

Day8 總結

1. stack Last In First Out 特性
2. 透過操作頂端元素來解題
3. push()、pop()時間複雜度O(1)