STL stack 概述

棧（stack）是一種遵循**后進先出（LIFO）**原則的線性數據結構，僅允許在棧頂進行插入和刪除操作。STL（Standard Template Library）中的 stack 是一個容器適配器，基于其他容器（如 deque 或 list）實現，默認使用 deque 作為底層容器。

---

棧的基本操作

初始化棧

STL stack 的初始化需要包含頭文件 <stack>，并指定元素類型。

#include <stack>
using namespace std;stack<int> s; // 初始化一個存儲整數的棧

入棧操作（push）

將元素添加到棧頂。

s.push(10); // 棧內元素: [10]
s.push(20); // 棧內元素: [10, 20]
s.push(30); // 棧內元素: [10, 20, 30]

出棧操作（pop）

移除棧頂元素，但不返回其值。

s.pop(); // 移除30，棧內元素: [10, 20]

訪問棧頂元素（top）

返回棧頂元素的值，但不移除它。

int top_element = s.top(); // top_element = 20

檢查棧是否為空（empty）

返回布爾值，判斷棧是否為空。

bool is_empty = s.empty(); // 棧不為空，is_empty = false

獲取棧的大小（size）

返回棧中元素的個數。

int stack_size = s.size(); // stack_size = 2

---

棧的典型應用場景

1. 括號匹配問題
   檢查表達式中的括號是否匹配，例如 {[()]} 是合法的，而 {[(])} 是非法的。

2. 表達式求值
   實現中綴表達式轉后綴表達式（逆波蘭表達式），并計算其值。

3. 深度優先搜索（DFS）
   用棧模擬遞歸過程，避免遞歸調用帶來的額外開銷。

---

藍橋杯真題示例：括號匹配問題

問題描述

給定一個只包含 (、)、[、]、{、} 的字符串，判斷其括號是否匹配。

解決思路

1. 遍歷字符串，遇到左括號（(, [, {）時入棧。
2. 遇到右括號時，檢查棧頂是否是對應的左括號：
   • 如果是，彈出棧頂。
   • 如果不是，直接返回不匹配。
3. 遍歷結束后，棧為空則匹配，否則不匹配。

完整代碼

#include <iostream>
#include <stack>
#include <string>
using namespace std;bool is_valid(string s) {stack<char> st;for (char c : s) {if (c == '(' || c == '[' || c == '{') {st.push(c);} else {if (st.empty()) return false;char top = st.top();if ((c == ')' && top == '(') || (c == ']' && top == '[') || (c == '}' && top == '{')) {st.pop();} else {return false;}}}return st.empty();
}int main() {string s = "{[()]}";cout << (is_valid(s) ? "Valid" : "Invalid") << endl;return 0;
}

---

藍橋杯解題通用思路

1. 理解題意
   明確題目要求，例如輸入輸出格式、邊界條件（如空棧、非法輸入等）。

2. 選擇數據結構
   根據問題特性選擇棧或其他數據結構。棧適合處理對稱性或遞歸性質的問題。

3. 設計算法
   將問題分解為棧的基本操作（如入棧、出棧、匹配等）。

4. 編寫代碼
   實現算法，注意邊界條件和異常處理。

5. 測試驗證
   通過樣例測試和邊界測試（如空輸入、極端數據）驗證代碼正確性。

---

總結

STL stack 是解決一類特定問題（如括號匹配、表達式求值、DFS）的高效工具。在藍橋杯競賽中，熟練掌握棧的操作和應用場景能夠幫助快速解決相關問題。通過實際代碼示例和解題思路的訓練，可以提升對棧的理解和運用能力。