本ユニットでは、データをコンピュータ上でどう並べ・つなげて扱うかを表す「データ構造」の基本を学びます。要素を順に並べるリストや、スタック・キューといった線形構造と、木構造・2分木の階層型構造を取り上げます。アルゴリズムの土台となる考え方で、特にスタックの後入れ先出しは出題されやすい要点です。
データを一列に順序付けて並べた基本的な線形データ構造。
リストは、複数のデータを一列に並べ、前後の順序を持たせて管理するデータ構造です。各要素は「次はどれか」という順序情報を持ち、先頭から順にたどることができます。 配列と似ていますが、リストは要素のつなぎ方を変えることで、途中への挿入や削除を比較的しやすいのが特長です。スタックやキューは、このリストに「どこから出し入れするか」という制約を加えた応用形と考えると理解しやすくなります。 試験では、データを順序付けて並べる最も基本的な構造であり、線形構造の土台であることを押さえておけば十分です。
たとえ数珠つなぎになった電車の車両のようなもの。先頭から順に車両がつながっており、間に車両を増やしたり外したりして並びを変えられます。
記憶フックリストといえばデータを一列に順序付けて並べた構造
後入れ先出し(LIFO)でデータを出し入れする線形データ構造。
スタックは、最後に入れたデータを最初に取り出す「後入れ先出し(LIFO:Last In First Out)」の規律を持つデータ構造です。データを積む操作をプッシュ、取り出す操作をポップと呼びます。 積み重ねた皿のように、上にどんどん積み、取るときは一番上(=最後に積んだもの)から取ります。Webブラウザの「戻る」機能や、関数呼び出しの管理などに使われます。 試験では、キューとの違いが頻出です。スタックは後入れ先出し、キューは先入れ先出しと、出し入れの順序の違いを必ず区別できるようにしておきましょう。
たとえ積み重ねた皿のようなもの。新しい皿は一番上に積み、使うときも一番上の皿(最後に積んだもの)から取るので、後から入れたものが先に出ます。
記憶フックスタックといえば後入れ先出し(LIFO)
先入れ先出し(FIFO)でデータを出し入れする線形データ構造。
キューは、最初に入れたデータを最初に取り出す「先入れ先出し(FIFO:First In First Out)」の規律を持つデータ構造です。データを入れる操作をエンキュー、取り出す操作をデキューと呼びます。 列に並んで順番を待つ様子と同じで、先に並んだ人から順にサービスを受けます。印刷の順番待ちや、処理要求を到着順にさばく場面などで使われます。 試験では、スタックとの対比で問われます。キューは先入れ先出し、スタックは後入れ先出しという、出し入れする順序の違いをしっかり押さえておきましょう。
たとえレジに並ぶ行列のようなもの。先に並んだ人から順に会計を済ませて出ていくので、最初に入った人が最初に出ます。
記憶フックキューといえば先入れ先出し(FIFO)
データを階層的に枝分かれさせて表す非線形データ構造。
木構造は、データを親子の階層関係で枝分かれさせて表すデータ構造です。最上位の節点を根(ルート)と呼び、そこから枝分かれして子の節点が広がり、末端の節点を葉(リーフ)と呼びます。 一列に並ぶリストなどの線形構造と違い、1つの要素が複数の要素につながる非線形構造である点が特徴です。フォルダの階層や組織図のように、上下関係・包含関係を表すのに適しています。 試験では、根・節点・葉といった階層型構造の基本用語と、線形構造との違いを押さえておくとよいでしょう。
たとえ会社の組織図のようなもの。社長(根)の下に部長、その下に課員と枝分かれし、上下の所属関係が階層的に枝で表されます。
記憶フック木構造といえば階層的に枝分かれする構造
各節点が持つ子の数が最大2つに限られた木構造。
2分木(にぶんぎ)は、木構造の中でも各節点が持つ子の数を最大2つまでに限定した特殊な形です。それぞれの子を左の子・右の子として区別します。 子が必ず2つ以下と決まっているため構造が単純になり、データの探索や並べ替えを効率よく行えるという利点があります。一般の木構造の特殊形であり、木構造の考え方を前提とした応用と捉えると分かりやすいです。 試験では、木構造との関係(各節点の子が最大2つに制限された木構造であること)を押さえておけば十分な水準です。
たとえ分かれ道が必ず二股までと決まっている迷路のようなもの。どの地点でも進める方向は左か右の2方向までに限られています。
記憶フック2分木といえば子が最大2つの木構造
関連の過去問演習は今後のアップデートで追加予定です。