スタック

スタックとは

スタック (Stack) は、最後に追加された要素が最初に取り出される LIFO (Last-In, First-Out) のデータ構造である。push (追加) と pop (取り出し) の 2 つの操作で構成される。皿を積み重ねるイメージで、一番上の皿だけを取り出せる。

触れる端が一番上の 1 箇所だけ、という制約がスタックの本体である。途中の要素を見に行けない代わりに、「最後に始めたものが最初に終わる」入れ子の構造をそのまま表現でき、追加も取り出しも位置を探さずに済む。関数呼び出し、括弧の対応、Undo の履歴が揃ってスタックで書けるのは、いずれもこの入れ子の性質を持つためである。

計算量

要素数がどれだけ増えても、3 つの操作はいずれも末尾 1 箇所を触るだけで完了する。

操作	計算量
push (追加)	償却 O(1)
pop (取り出し)	O(1)
peek (一番上を参照)	O(1)

push だけ「償却」が付くのは、可変長配列で持つ場合に容量を使い切った回の push が領域の確保と既存要素のコピーを伴うためである。その 1 回は O(n) になるが、確保する容量を倍々に増やす実装ではコピーの総量が要素数に比例する範囲に収まり、1 回あたりに均せば定数時間になる。連結リストで持てばこのコピーは起きない代わりに、要素ごとに次を指す参照の分だけメモリを使い、要素が連続領域に並ばないのでキャッシュの効きも落ちる (連結リスト)。上限が読めない大量の要素を積むとき以外は、配列実装で足りる。

TypeScript での実装

配列を内部に隠して、末尾以外を触れないようにしたものがスタックの最小実装になる。

class Stack<T> {
  private items: T[] = [];

  push(item: T): void { this.items.push(item); }
  pop(): T | undefined { return this.items.pop(); }
  peek(): T | undefined { return this.items[this.items.length - 1]; }
  isEmpty(): boolean { return this.items.length === 0; }
  get size(): number { return this.items.length; }
}

JavaScript の配列は push と pop がどちらも末尾への操作なので、要素の詰め直しが起きない。20 万件を積んで全て取り出す処理を Node.js v26 で測ると 6 ミリ秒程度で終わる。専用のクラスを作らず配列をそのまま使っても速度の面では問題にならないため、上のようにクラスで包む意味は、shift や添字アクセスを呼べなくして LIFO の制約を型で保証することにある。

実務での活用

コールスタック

関数の呼び出しはスタックで管理される。関数 A が関数 B を呼び、B が C を呼ぶと、スタックに A → B → C の順で積まれ、C → B → A の順で戻る。

call A → push A
  call B → push B
    call C → push C
    return → pop C
  return → pop B
return → pop A

積める段数の上限は言語仕様ではなく、実行環境が用意したスタック領域の大きさと 1 フレームの太さで決まる。引数もローカル変数もない最小の再帰なら Node.js v26 で 1 万段強まで積めるが、引数が増えれば 1 フレームが太るので届く段数は減る。上限を超えると RangeError: Maximum call stack size exceeded で停止する (再帰)。深さが入力の大きさに比例して伸びる処理は、この節の後半で扱う明示的なスタックへ書き換えるのが確実な対策になる。

Undo/Redo

操作の履歴を積む側と、取り消した分を積む側の 2 本のスタックで表せる。execute で redo 側を空にしているのは、取り消した後に新しい操作をした時点で、やり直せる未来が分岐して意味を失うためである。

class UndoManager<T> {
  private undoStack: T[] = [];
  private redoStack: T[] = [];

  execute(state: T) {
    this.undoStack.push(state);
    this.redoStack = [];
  }

  undo(): T | undefined {
    const state = this.undoStack.pop();
    if (state) this.redoStack.push(state);
    return this.undoStack[this.undoStack.length - 1];
  }

  redo(): T | undefined {
    const state = this.redoStack.pop();
    if (state) this.undoStack.push(state);
    return state;
  }
}

undo が返すのは取り消した状態ではなく、取り消した後の現在の状態である。そのため最初の状態を execute で積んでいないと、最後の 1 回の undo で undefined が返る。初期状態を履歴の底に入れておくか、undoStack.length が 1 以下なら undo を無効にする実装が必要になる。

括弧の対応チェック

function isBalanced(s: string): boolean {
  const stack: string[] = [];
  const pairs: Record<string, string> = { ')': '(', ']': '[', '}': '{' };

  for (const ch of s) {
    if ('([{'.includes(ch)) stack.push(ch);
    else if (')]}'.includes(ch)) {
      if (stack.pop() !== pairs[ch]) return false;
    }
  }
  return stack.length === 0;
}

isBalanced('({[]})');  // true
isBalanced('({[})');   // false
isBalanced('(');       // false (閉じられていない)
isBalanced(')(');      // false (開く前に閉じている)

開き括弧を積み、閉じ括弧が来たら一番上と種類が合うか確かめる。開く前に閉じた場合は stack.pop() が undefined を返して不一致になり、閉じ忘れた場合は最後にスタックが空にならないので、2 種類の誤りが同じ仕組みで検出できる。

DFS (深さ優先探索)

再帰による探索は、コールスタックが「戻ってから次に見る場所」を覚えている。この役目を自分の配列で引き受けると、再帰を使わない DFS になる。

function dfs(graph: Record<string, string[]>, start: string): string[] {
  const stack = [start];
  const seen = new Set<string>();
  const order: string[] = [];
  while (stack.length > 0) {
    const node = stack.pop()!;
    if (seen.has(node)) continue;  // 別の経路から先に訪問済み
    seen.add(node);
    order.push(node);
    for (const next of graph[node]) stack.push(next);
  }
  return order;
}

注意点が 2 つある。訪問済みの記録を取り出した直後に見ないと、閉路のあるグラフで同じ頂点を何度も処理してしまう。もう 1 つは訪問順で、隣接頂点を配列の順に push すると最後に積んだものから取り出されるため、再帰版と兄弟をたどる向きが逆になる。A → B, C / B → D のグラフでは、上の実装が A > C > B > D、再帰版が A > B > D > C を返す。順序に意味があるなら push する前に逆順にする。

キューとの比較

違いは取り出す端がどちらかという 1 点だけだが、実装の手間は対称にならない。

データ構造	順序	用途
スタック (LIFO)	後入れ先出し	コールスタック、Undo、DFS
キュー (FIFO)	先入れ先出し	メッセージキュー、BFS

スタックは追加も取り出しも配列の末尾で済むので、素朴な配列実装のままで速い。キューは追加が末尾、取り出しが先頭に分かれるため、配列の先頭を取り除くと残りを前へ詰め直すことになり、件数が増えるほど遅くなる。この差の実測と回避策は キュー 側で扱う。

理論と実装の両面から学ぶなら関連書籍が参考になる。