スタック（データ構造）とは：LIFOの定義・プッシュ・ポップの仕組みと例・実装

スタック（データ構造）の基本からLIFO原理、プッシュ／ポップ動作、具体例と実装例を図解でわかりやすく解説。初心者〜実践者向け。

スタックは、コンピュータサイエンスにおいて最も重要なデータ構造の一つです。スタックの動作をイメージするには、裏向きのトランプの山札を想像してください。私たちは常に「一番上にあるカード」にしか直接アクセスできません。上のカードを確認するだけでスタックに残す操作（peek/トップ参照）と、上のカードを取り出してスタックから取り除く操作（pop/ポップ）があります。新しいカードを一番上に置く操作はプッシュ（push）と呼ばれます。

基本的な定義と特性

スタック（stack）は、LIFO（Last-In, First-Out）の原則に従うコレクションです。つまり、最後に追加した要素が最初に取り出されます。典型的な操作は次の通りです：

• push(x) — 要素xをスタックの頂上に追加する。
• pop() — 頂上の要素を取り出してスタックから削除し、その要素を返す（要素がない場合は例外またはエラー）。
• peek() または top() — 頂上の要素を取り出さずに参照する。
• isEmpty() — スタックが空かどうかを判定する。
• size() — 現在の要素数を返す（実装による）。

簡単な例（トランプでの操作）

例：スタックにカードA, B, Cを順にプッシュすると、上から見ると「C（頂上）→ B → A（底）」になります。ここでpopを一回行うとCが取り出され、次にpeekするとBが見える、という動作になります。

時間計算量と空間

• push、pop、peek、isEmpty は典型的に O(1)（定数時間）で実行されます。
• 空間使用量は格納している要素数に比例します。固定長の配列で実装する場合は容量制限が発生し得ます。

実装の方法（概要）

代表的な実装は主に2つです。

• 配列ベース（固定長または動的配列）：インデックスで頂上を管理します。実装が簡単でキャッシュ効率が良いですが、固定配列だと容量超過に注意が必要です。動的配列（例：リサイズ可能配列）なら自動拡張できます。
• 連結リストベース：先頭（または末尾）にノードを追加／削除することで実現します。サイズに制限がなく、push/popが簡潔に実装できますが、ノードごとのメモリオーバーヘッドがあります。

簡単な擬似コード

// 配列ベース（固定容量） class Stack {   int[] data;   int top = -1;   Stack(int capacity) { data = new int[capacity]; }   void push(int x) {     if (top + 1 == data.length) throw "Overflow";     data[++top] = x;   }   int pop() {     if (top == -1) throw "Underflow";     return data[top--];   }   int peek() {     if (top == -1) throw "Empty";     return data[top];   }   boolean isEmpty() { return top == -1; } } 

よくある利用例・応用

• 再帰呼び出しの内部的な管理（コールスタック）：関数呼び出しごとに戻り先や局所変数を積む。
• 式の評価と逆ポーランド記法（RPN）：算術式の評価、演算子の優先順位処理など。
• ブラウザの「戻る」履歴、エディタの取り消し（undo）/やり直し（redo）機能。
• 深さ優先探索（DFS）を反復的に実装する際の補助データ構造。
• 括弧の整合性チェック（例：ソースコードの構文解析で括弧が対応しているか確認）。

注意点とエラー

• スタックオーバーフロー：固定サイズのスタックに対してpushを繰り返すと容量を超える。プログラムのクラッシュや例外の原因になる。
• 空のスタックからのpop：要素がないときにpopを呼ぶとアンダーフローになる。呼び出す前に必ずisEmptyをチェックするか例外処理を行う。
• スレッドセーフ性：マルチスレッド環境で共有する場合は同期（ロック）やスレッドセーフな実装が必要。

スタックとコールスタックの違い

「スタック」という用語はデータ構造一般を指しますが、プログラム実行時に関数呼び出しを管理する低レベルの仕組みは特にコールスタック（call stack）と呼ばれます。コールスタックはスタックの概念を用いて戻りアドレスや局所変数を管理しますが、実装や使用目的が固定されている点が異なります。

まとめ

スタックはシンプルで強力なデータ構造であり、LIFOの性質を活かして多くのアルゴリズムやシステム機能で使われます。基本操作は少なく、概念的にも実装的にも理解しやすい一方、容量管理や並行性には注意が必要です。

文字で検索