ENGINEER_SPEC: データ構造
システム開発において「どのデータ構造を選ぶか」は、パフォーマンスに直結する重要な判断です。
1. キュー (Queue) & スタック (Stack)
これらは「データを出し入れする順序」を強制する仕組みです。
- キュー (FIFO)：最初に入れたものを最初に出す。Webサーバーのリクエスト処理や、プリンタの印刷ジョブなどで使われます。
- スタック (LIFO)：最後に入れたものを最初に出す。エディタの「戻る
(Undo)」機能や、プログラムの関数呼び出し履歴（コールスタック）の管理に使われます。
2. 優先度付きキュー (Priority Queue)
単なる「順番」ではなく、各データに割り当てられた「重要度（優先度）」に従ってデータを取り出します。裏側では「ヒープ木」などの構造が使われており、OSのタスクスケジューリングや、ダイクストラ法（最短経路探索）で重宝されます。
3. 連結リスト (単方向 vs 双方向)
配列（Array）がメモリ上に隙間なく連続してデータを置くのに対し、連結リストは「次のデータの場所（ポインタ）」を持つことで、メモリ上のバラバラな場所にデータを配置できます。
- 単方向リスト (Singly Linked List)：各ノードが「次
(Next)」のポインタのみを持ちます。メモリ消費は最小限ですが、一方向にしか進めず、後戻りができません。シンプルなキューの実装などに適しています。
- 双方向リスト (Doubly Linked List)：各ノードが「次 (Next)」と「前
(Prev)」の両方のポインタを持ちます。ポインタを保存するためのメモリ消費は増えますが、逆方向への走査や、特定のノードを削除する際のポインタの繋ぎ変えが圧倒的にスムーズになります。ブラウザの「戻る・進む」の履歴管理など、双方向の移動が頻繁なケースで活躍します。