【筆記】常用C++ STL:stack

  • stack:堆疊或棧,資料有「先進後出」(first in last out, FILO) 的特性。
    • 像是自助餐廳的餐盤架,最新補充的乾淨餐盤堆疊在上方,客人取用餐盤時,從最上方的開始拿。
  • 宣告:
    • stack <int> stk;
  • 把元素 x 加進 stack:
    • stk.push(x);
  • 取值:
    • x = stk.top();
  • 移除已經讀取的值:
    • stk.pop();
  • 判斷是否為空的stack:
    • stk.empty() 回傳true
    • stk.size() 回傳零
  • 【範例】ZeroJudge b838: 104北二2.括號問題題解
    • 判斷輸入字串中,包含幾組合法的小括號。
#include <iostream>
#include <stack>
using namespace std;
 
int main() {
    int n;
    string s;
    cin >> n;
    while (n--) {
        int count = 0;
        stack <int> stk;
        cin >> s;
        for (int j = 0; j < s.length(); j ++){
            if (!stk.empty() && stk.top() == '(' && s[j] == ')'){
                stk.pop();
                count ++;
            }else{
                stk.push(s[j]);
            }
        }
        if (!stk.empty()){
            count = 0;
        }
        cout << count << endl;
    }
}

【更多練習】ZeroJudge c123: 00514 – Rails題解

分享本文 Share with friends