IT 技書の森

スタック

後入れ先出し (LIFO) でデータを管理する基本データ構造

データ構造基礎

スタックとは

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

計算量

操作 計算量
push (追加) O(1)
pop (取り出し) O(1)
peek (先頭を参照) O(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 が O(1) のため、そのままスタックとして使える。

実務での活用

コールスタック

関数の呼び出しはスタックで管理される。関数 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

スタックオーバーフローは、再帰が深すぎてスタックの容量を超えた場合に発生する。

Undo/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;
  }
}

括弧の対応チェック

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

DFS (深さ優先探索)

再帰の代わりに明示的なスタックで DFS を実装できる。

キューとの比較

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

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

関連用語