このページでは、配列と連結リストの違い、先頭・末尾での追加と削除、LIFOのスタックとFIFOのキュー、グラフ探索や逆ポーランド表記での使われ方がわかります。
リスト
- 一言で言うと：
- データを「順番に並べて持つ」2つの方法（配列と連結リスト）と、連結リストでの追加・削除の手間、リストで2分木を表す方法の話。
並べ方を選ぶ（配列か連結リストか）→ 出し入れする（先頭・末尾での追加と削除）→ 木も表せる（リストによる2分木）
覚え方の軸
- 配列は「場所が決まっている」、連結リストは「ポインタでつながっている」：
- 配列は好きな場所をすぐ読めるが、途中の出し入れが遅い。連結リストはその逆
- 連結リストの種類は「ポインタの向き」で3つ：
- 次だけ（単方向）、前と次（双方向）、最後が先頭に戻る（循環）
- HeadとTailをもつリストの処理量は「追加は先頭も末尾も同じ、削除だけ末尾が重い」：
- 末尾を消すには、1つ手前の要素を探してHeadから順にたどる必要がある
- だからこのリストは「末尾に足して先頭から取る」キュー向き
- 2分木のノードは「自分のデータ＋親・左の子・右の子への3本のポインタ」
リストの実現方法：配列か、連結リストか
- リスト：
- 順序づけられたデータの並び
- 一般に「リスト」といったら連結リストを指すことが多い
- リストを表現する主なデータ構造は、配列と連結リスト
- 配列：
- 個々の要素の位置を固定して、要素の番地（アドレス）を簡単に計算できるようにしたデータ構造
- 同じ型のデータを、決まった個数だけ並べた形。記憶装置の連続した番地に順に格納するので、要素番号（添字）で直接アクセス（ダイレクトアクセス）できる
- 長所：
- 任意の要素を参照できる
- 短所：
- 挿入・削除のときは、その位置より後ろの要素を1つずつ後ろ（または前）にずらすので、処理効率が悪い
- あらかじめ最大データ数分の領域を確保しておく必要があり、実際のデータが少ないと無駄が出る
- 連結リスト：
- 各要素をポインタでつないだデータ構造
- 長所：
- 要素の追加・削除は、少しのポインタの付け替えだけでできる（例：単方向リスト「東京→大阪→福岡」から「大阪」を消すなら、「東京」のポインタ部に「大阪」のポインタ部の値（福岡のアドレス）を入れるだけ）
- 使うデータの個数だけ動的に領域を確保できるので、無駄な領域が出ない（動的確保には、通常ヒープ領域を使う）
- 短所：
- 要素の位置が固定されていないので、要素番号を使った任意の要素の参照はできない
- 要素ごとにポインタ部が別に要るので、データ1個あたりの記憶域は配列の方が小さい
- 連結リストの種類
| 種類 | 別名 | ポインタのもち方 |
|---|---|---|
| 単方向リスト | 片方向リンク、線形リスト | 各要素が次の要素へのポインタをもつ。最後の要素は「次がない」 |
| 双方向リスト | 双方向リンク | 各要素が前と後ろの要素へのポインタをもつ |
| 循環リスト | − | 各要素が次の要素へのポインタをもち、末尾の要素は先頭要素へのポインタをもつ |
- 各要素は、データ部とポインタ部でできている
連結リストにおける要素の追加と削除：先頭と末尾で手間が違う
- 試験では、先頭要素へのポインタ（Head）と末尾要素へのポインタ（Tail）をもつ連結リストが出る
- ★試験では、リストの先頭と末尾での、要素の追加と削除の処理量が問われる
- 例のリスト：
- Head → A → B → C → D（TailはDを指す）
- 要素の追加：
- 先頭でも末尾でも処理量は同じ
- 先頭にZを追加する手順：
- ① Zのポインタ部に、HeadがもつAのアドレスを入れる → ② HeadにZのアドレスを入れる
- 末尾にEを追加する手順：
- ① TailからたどったDのポインタ部に、Eのアドレスを入れる → ② TailにEのアドレスを入れる
- 要素の削除（読み出したあとで削除）：
- 先頭より末尾の方が処理量が多い
- 先頭要素Aを削除する手順：
- ① HeadからたどったAのポインタ部の値（Bのアドレス）をHeadに入れる（1手で終わる）
- 末尾要素Dを削除する手順：
- ① Headから順にCまでたどる → ② Cのポインタ部をNULL（空値）にする → ③ TailにCのアドレスを入れる
- 末尾要素の削除にかかる時間は、要素数にほぼ比例する
- 理由：
- 単方向リストでは「1つ手前（C）」へ戻れないので、先頭から順にたどるしかない
- メモリリーク：
- 動的に作ったリストでは、削除したデータの記憶領域を解放する必要がある。解放しないで不要な領域が増えると、使えるメモリがだんだん減っていく
- HeadとTailをもつリストの用途：
- 「追加は末尾、取り出しは先頭」で行うキュー（FIFO）の実現に向いている
- 先頭で追加と削除をするスタックとしても使えるが、その場合Tailは不要
- リストでキューを作る場合、途中への要素の追加・削除は、単方向リストより双方向リストの方がやりやすい
| 操作 | 先頭 | 末尾 |
|---|---|---|
| 追加 | ポインタ2か所の変更 | ポインタ2か所の変更（同じ） |
| 削除 | Headを1か所変えるだけ（軽い） | 手前までたどる必要がある（重い。要素数に比例） |
リストによる2分木の表現：ポインタで親子をつなぐ
- リスト構造で2分木を表現できる
- ノードのデータ構造：
- data（ノードのデータ値）、Parent（親ノードへのポインタ）、Left（左の子へのポインタ）、Right（右の子へのポインタ）
- 配列で表した例（「－」は指す先がないこと）
| 番号 | data | P（Parent） | L（Left） | R（Right） |
|---|---|---|---|---|
| 1 | 40 | － | 2 | 3 |
| 2 | 30 | 1 | 4 | 5 |
| 3 | 50 | 1 | － | － |
| 4 | 20 | 2 | － | － |
| 5 | 35 | 2 | － | － |
- 木の形：
- 根が40、その左の子が30、右の子が50。30の左の子が20、右の子が35
- 親の子を指す書き方：
- ノードnの親がもつ左の子へのポインタは Left［Parent［n］］、右の子へのポインタは Right［Parent［n］］
- ノードを追加する例：
- データ値35のノードの右に、データ値37のノード（番号6）を追加するときは、次の2つを行う
- 番号5（35）のRightに、番号6を指すポインタを入れる
- 番号6（37）のParentに、番号5を指すポインタを入れる
- ポイント：
- 親から子へ、子から親への両方向を設定する
混同しやすいペア
- 配列（任意の要素をすぐ読める、挿入・削除は遅い、領域を最初に確保）／連結リスト（任意の要素は読めない、挿入・削除はポインタの付け替えだけ、動的に確保）
- 単方向リスト（次だけ）／双方向リスト（前と次）／循環リスト（末尾が先頭を指す）
- 先頭の削除（Headを付け替えるだけ）／末尾の削除（手前までたどる。要素数に比例）
- キューとして使う（Head・Tailとも必要）／スタックとして使う（Tailは不要）
- データ1個あたりの記憶域：
- 配列の方が小さい（連結リストはポインタ部の分だけ大きい）
スタックとキュー
- 一言で言うと：
- データの「取り出す順番」が決まった2つの入れ物の話。最後に入れたものから出すのがスタック、最初に入れたものから出すのがキュー。
2つの入れ物（スタックとキュー）→ 使い道（グラフの探索）→ 計算にも使う（逆ポーランド表記）
覚え方の軸
- スタックは「積み重ねた皿」、キューは「レジの行列」：
- スタック＝LIFO（後入れ先出し）、キュー＝FIFO（先入れ先出し）
- 操作の名前は組で覚える：
- スタックはPUSH／POP、キューはENQ／DEQ
- 探索との対応：
- 深さ優先探索はスタック、幅優先探索はキュー
- 関数の呼び出しはスタック：
- 戻り番地・引数・局所変数を積み、戻るときに取り出す（再帰もこれで動く）
- 逆ポーランド表記は「数字ならPUSH、演算子なら2つPOPして計算してPUSH」
スタックとキューの基本操作
- スタック：
- 最後に入れたデータから順に取り出すLIFO（Last In First Out：後入れ先出し）方式
- 挿入はPUSH（プッシュ）、取り出しはPOP（ポップ）。どちらも常に最上段（頂上）で行う
- 配列かリストで実現する。配列なら、トップの位置を表す変数top（初期値0）だけで操作する
- PUSH(x)：
- top ← top＋1、S［top］← x
- POP：
- top ← top−1、S［top＋1］を返す
- PUSH(x)：
- スタックと関数呼び出し：
- スタックは、関数呼び出し（再帰的処理を含む）の実現に欠かせない
- 関数を呼ぶときに戻り番地、引数、局所変数をスタックに積み、戻るときに取り出して、実行途中の状態を管理する
- 制御スタック：
- 関数呼び出しのときに使うスタック。コールスタックともいう
- スタックフレーム：
- 関数ごとに積まれるデータのまとまり
- スタックポインタ：
- スタックの最上段の位置を指す
- フレームポインタ：
- スタックフレーム内の特定の位置を指す
- 局所変数：
- 関数（手続）の中だけで使えるローカル変数
- グローバル変数：
- プログラム（コンパイル単位）内の、どの手続からでも参照できる変数
- キュー：
- 最初に入れたデータから順に取り出すFIFO（First In First Out：先入れ先出し）方式
- 追加はいつも一方の端、取り出しはもう一方の端で行うので、一番古いデータから処理できる
- 挿入はENQ（エンキュー）、取り出しはDEQ（デキュー）
- 配列で作る場合、格納位置を表すxと処理位置を表すyを使う。配列の最後まで格納したら、先頭に戻る
| スタック | キュー | |
|---|---|---|
| 取り出す順 | LIFO（後入れ先出し） | FIFO（先入れ先出し） |
| 入れる操作 | PUSH | ENQ |
| 出す操作 | POP | DEQ |
| 例え | 積み重ねた皿 | レジの行列 |
| 主な用途 | 関数呼び出し、再帰、深さ優先探索、逆ポーランド記法の計算 | 幅優先探索、到着順の処理 |
- 例題：
- 空の入れ物に「1を入れる → 2を入れる → 1つ出す → 3を入れる → 1つ出す → 1つ出す」を行う
- スタックなら出てくる順は 2 → 3 → 1
- キューなら出てくる順は 1 → 2 → 3
グラフの探索：深さはスタック、幅はキュー
- ある出発点から目的点までの経路を調べるときに、スタックやキューを使う
- 深さ優先探索：
- スタックを使う
- 一般に、保持する情報が少なく、記憶域の消費が少ない効率のよい探索ができる
- ただし局所的に探索していくので、最適な経路にならない場合がある
- 幅優先探索：
- キューを使う
- 深さ優先探索と幅優先探索は、後の「木構造」でも詳しく扱う
- 深さ優先探索：
スタックを使った演算（逆ポーランド表記）
- 逆ポーランド表記（後置表記）：
- 演算子を数値（オペランド）の後ろに書く書き方
- 例：
- 算術式（4＋6）＊3 → 逆ポーランド表記 4 6 ＋ 3 ＊
- スタックを使い、左端から右へ順に、次の規則で計算できる
- 規則1：
- 数値（オペランド）を読んだら、スタックにPUSHする
- 規則2：
- 演算子を読んだら、スタックから2つPOPし、「後から取り出した数値 演算子 先に取り出した数値」を計算して、結果をPUSHする
- 規則1：
- 上の例の手順：
- 4、6をPUSH → 「＋」で6、4をPOPして4＋6＝10をPUSH → 3をPUSH → 「＊」で3、10をPOPして10＊3＝30をPUSH（これが答え）
- 例題：
- 4 1 − 2 3 ＋ ＊ を計算する
- 4、1をPUSH → 「−」で4−1＝3 → 2、3をPUSH → 「＋」で2＋3＝5 → 「＊」で3＊5＝15
- 元の式は（4−1）＊（2＋3）
- 注意：
- 引き算・割り算は順番が大事。「4 1 −」は4−1（後から取り出した4から、先に取り出した1を引く）
混同しやすいペア
- スタック（LIFO、PUSH／POP）／キュー（FIFO、ENQ／DEQ）
- 深さ優先探索（スタック、記憶域が少ない、最適経路とは限らない）／幅優先探索（キュー）
- スタックポインタ（最上段を指す）／フレームポインタ（フレーム内の特定の位置を指す）
- 局所変数（関数の中だけ）／グローバル変数（どの手続からでも）
- 制御スタック（＝コールスタック。関数呼び出し用のスタック全体）／スタックフレーム（関数1回分のデータのまとまり）