データ構造の基礎——スタック・キュー・木・グラフ

データ構造とは何か

アルゴリズムが「手順」なら、データ構造は「道具箱の整理方法」です。同じデータを持っていても、どのように整理するかによって、処理の速さや書きやすさが大きく変わります。

実用的なプログラムでは、問題に合ったデータ構造を選ぶことが、パフォーマンスと保守性の両方に直結します。

スタック（Stack）

スタックは**後入れ先出し（LIFO: Last In, First Out）**のデータ構造です。積み上げた皿のイメージで、最後に載せた皿を最初に取ります。

stack = []
stack.append("A")  # push
stack.append("B")
stack.append("C")
print(stack.pop())  # → "C"（最後に追加したものが出る）

主な操作の計算量

操作	計算量
push（追加）	O(1)
pop（取り出し）	O(1)
peek（先頭確認）	O(1)

実際の使われ方

ブラウザの「戻る」ボタン——訪問履歴をスタックで管理
関数の呼び出し——コールスタック（再帰処理の仕組み）
テキストエディタの「Undo」機能

キュー（Queue）

キューは**先入れ先出し（FIFO: First In, First Out）**のデータ構造です。コンビニのレジ待ちのように、先に並んだ人が先に処理されます。

from collections import deque
queue = deque()
queue.append("A")   # enqueue
queue.append("B")
queue.append("C")
print(queue.popleft())  # → "A"（最初に追加したものが出る）

主な操作の計算量

操作	計算量
enqueue（追加）	O(1)
dequeue（取り出し）	O(1)

実際の使われ方

タスクキュー——メッセージブローカー（RabbitMQ, SQS 等）の基本概念
BFS（幅優先探索）の実装
プリンターの印刷待ち管理

木（Tree）

木は階層構造を表すデータ構造です。頂点（ルートノード）から枝分かれして葉（リーフノード）に至ります。

二分探索木（BST）

各ノードが「左の子 < 自分 < 右の子」という順序を保つ木です。

主な操作の計算量（バランスが取れている場合）

操作	計算量
検索	O(log n)
挿入	O(log n)
削除	O(log n)

木が偏った形（線形に連なる状態）になると O(n) まで劣化します。これを防ぐのが AVL 木や赤黒木などの自己平衡木です。

木の実際の使われ方

ファイルシステムのディレクトリ構造
HTML/XML の DOM ツリー
データベースの B-Tree インデックス——大量データを高速に検索するために使用

グラフ（Graph）

グラフはノード（頂点）とエッジ（辺）で構成されるデータ構造です。木はグラフの特殊ケース（ループなし・方向あり）と見なすこともできます。

  A --- B
  |   / |
  |  /  |
  C --- D

グラフには有向グラフ（矢印の向きがある）と無向グラフがあります。

代表的なグラフの表現方法

方法	メリット	向いている場面
隣接行列	エッジ確認 O(1)	辺が多い密なグラフ
隣接リスト	メモリ効率が良い	辺が少ない疎なグラフ

グラフ探索アルゴリズム

DFS（深さ優先探索）：スタックを使って深く潜っていく。迷路の解法、トポロジカルソートなど
BFS（幅優先探索）：キューを使って近い順に探索。最短経路の探索など

実際の使われ方

SNSの友人関係グラフ——「友達の友達」を検索
Googleマップの経路探索——ダイクストラ法など
タスク依存関係の管理——DAG（有向非巡回グラフ）

データ構造の選び方

やりたいこと	向いているデータ構造
最後に追加したものを先に処理	スタック
追加順に公平に処理	キュー
大量データを高速に検索・挿入	二分探索木 / B-Tree
ネットワーク・関係性の表現	グラフ
順序を保ちながら重複なく管理	順序付き集合（Ordered Set）

まとめ

データ構造を選ぶ基準は3つです。

操作の種類——追加・削除・検索のどれが多いか
データ量——小規模なら単純な配列、大規模なら専用構造
アクセスパターン——先頭から取り出すか、任意の位置にアクセスするか

「なんとなく配列を使う」から「操作に最適な構造を選ぶ」への意識の変化が、コードの品質とパフォーマンスを引き上げます。

アルゴリズムの性能評価の基礎は、ビッグO記法と計算量で学べます。あわせてご覧ください。