Stack

最後に入れたものから先に取り出す入れ物（LIFO）。配列の push / pop がそのままスタックになる。

効くのは入れ子を扱うとき。「いちばん内側から片付く」は「最後に積んだものから降ろす」と同じ形。括弧の対応、HTML タグの開閉、関数呼び出し（コールスタック）——全部これ。

15. Valid Parentheses

https://neetcode.io/problems/validate-parentheses/question?list=blind75

(){}[] だけからなる文字列が、正しく対応して閉じているかを判定する。"([{}])" は true、"[(])" は false。

"([{" まで読んだ時点で、次に来てよい閉じ括弧は } だけ。その次は ]、その次が )。つまり開いた順の逆から閉じる。覚えておくべきは「まだ閉じていない開き括弧の列」で、これは入力しだいでいくらでも伸びる。変数では持てないのでスタックが要る。

// 閉じ括弧 -> 対応する開き括弧
const CLOSE_TO_OPEN: Record<string, string> = {
    ')': '(',
    ']': '[',
    '}': '{',
};

class Solution {
    // 例: s = "([{}])"  ->  true
    isValid(s: string): boolean {
        // まだ閉じられていない開き括弧を、出てきた順に積む
        const stack: string[] = [];

        for (const c of s) {
            const open = CLOSE_TO_OPEN[c];

            // 対応表に無い = 開き括弧。まだ相方が来ていないので積んでおく
            if (!open) {
                stack.push(c);
                continue;
            }

            // 閉じ括弧。相方はいちばん最後に積んだもの以外にありえない
            if (stack.pop() !== open) return false;
        }

        // 積んだものが全部払い出されていれば正しい（"(((" は残るので false）
        return stack.length === 0;
    }
}

時間 O(n)、空間 O(n)。

"[(])"
c='['  積む                      stack = ['[']
c='('  積む                      stack = ['[', '(']
c=']'  期待は '['、pop() は '('  -> 不一致で false

応用: 覚えておくものが1個で足りるなら変数、何個になるか分からないならスタック。12（Best Time to Buy and Sell Stock）で覚えたのは「これまでの最安値」1個だけだったので minBuy という変数で済んだ。今回は「まだ閉じていない開き括弧」が入力しだいで何個にでもなるので、積める入れ物が要る。