データ構造とは？キューとスタックでわかる整理のルール

ラボへ届いた修理の受付票は、先に受け付けたものから取り出したい。一方、画面で行った操作を一つ戻すなら、最後の操作から戻したい。同じように記録をためていても、次に必要なものは違います。

この違いに合わせて、データをどう整理し、どこへ追加し、どこから取り出すかを考えるのが、データ構造を学ぶ入口です。

データ構造とは、データを整理して扱うための仕組み

データ構造とは、データを目的に合う形に整理し、取り出したり、追加したりしやすくする仕組みです。 データ同士の順番や関係、許される操作などを扱います。

「情報を保存する箱」とだけ考えると、使い方が見えなくなります。たとえば100件の受付記録があっても、古い順に処理したいのか、受付番号から一件を探したいのかで、必要な操作は違います。

整理の目的は、見た目をきれいに並べることだけではありません。「次にどれを使うか」「どう探すか」を、プログラムで扱える形にすることです。

キューとスタックの違い：同じ3件でも取り出す順が変わる

A、B、Cという3件を、この順番で追加したとします。最初に取り出すものを決める二つの規則を見てみましょう。

キューは、先に入れたものを先に取り出す

キューは、末尾へ追加し、先頭から取り出す規則です。受付の列のように、A、B、Cと入れたらAから取り出します。この順序をFIFO（ファイフォ、First In, First Out）、日本語では「先入れ先出し」といいます。

追加をenqueue（エンキュー）、取り出しをdequeue（デキュー）と呼びます。まずは英語の名前より、「入る場所は後ろ、出る場所は前」という関係を押さえましょう。

これは通常のキューの説明です。優先度の高い仕事を先に取り出す「優先度付きキュー」など、別の規則を持つものもあります。現実の受付や印刷が、いつでも単純な到着順になるという意味ではありません。

スタックは、最後に入れたものを先に取り出す

スタックは、上へ積み、上から取り出す規則です。Aの上にB、さらにCを積むと、最初に取り出すのはCです。LIFO（ライフォ、Last In, First Out）、つまり「後入れ先出し」といいます。

上へ追加する操作はpush（プッシュ）、上から取り出す操作はpop（ポップ）です。直前の操作から順に戻したいときの考え方に合います。ただし、実際のアプリの「元に戻す」には、操作内容や変更前の状態を記録する仕組みも必要です。

ユイ

入れたものは同じなのに、最初に出るのがAとCで違うんですね

マコト

そこが大事なんだ。入れ物の名前より、次に何を取り出したいかから考えると選びやすいよ

キューとスタックは、操作の振る舞いを定める抽象データ型としても説明されます。「どんな操作ができるか」を決めることと、「メモリのどこへ、どう置いて実現するか」を分ける考え方です。同じ規則を実現する方法は一つではありません。

データ構造の種類：位置・階層・つながりも表せる

キューとスタックでは、列や積み重ねの端から取り出しました。途中の一件を位置で選びたいときや、駅と路線のようなつながりをたどりたいときは、別の関係にも注目します。「何番目か」「どの項目の下にあるか」「どことつながるか」を表す構造もあります。

配列で位置を指定する番号を、**添字（そえじ）**と呼びます。何番から数えるかや、途中へ追加したときの動きは、言語や実装によって違います。入門図の収納枠を見て、すべての言語がまったく同じメモリ配置を使うと思わないようにしてください。

木は、たとえば「道具→計測器→温度計」のような階層に向きます。一方、複数の駅を行き来し、回り道もできる関係はグラフで表せます。グラフには、必ず循環があるという意味ではありません。

これらを、名前だけの一覧として全部暗記する必要はありません。順番を守りたいのか、位置から取りたいのか、関係をたどりたいのかに注目すると、種類が分かれる理由が見えます。持ち方が決まると、そのデータから答えを探す手順にも影響します。

データ構造とアルゴリズムの違い

データ構造は、データをどう持ち、どんな操作で扱うか。アルゴリズムは、そのデータを使って問題をどう解くかという手順です。両者は、組み合わせて考えます。

たとえば、小さい順に並んだ数列から中央の値を取り出せるなら、中央と比べて探す範囲を絞る方法が使えます。一方、次の要素への参照を順にたどる構造では、中央へ到達する仕事も考える必要があります。

同じ「探す」という目的でも、データの持ち方によって、都合のよい手順は変わります。アルゴリズムとはでは、同じ8枚から数字を探す二つの手順を比べられます。

また、データ構造はメモリやストレージという装置の名前ではありません。保存場所の役割は、メモリとストレージの違いで別に整理できます。

データ構造は、よく行う操作から選ぶ

「一番速い構造」を先に探すより、どんな仕事を何度も行うかを言葉にしてみましょう。

• 到着した順に処理したいなら、キューの規則が合う。
• 直前の作業から戻したいなら、スタックの規則が手掛かりになる。
• 位置を指定して取り出したいなら、配列のような持ち方を考える。
• 分類の階層や道のつながりをたどりたいなら、木やグラフを考える。

追加や削除を頻繁に行うのか、探すことが多いのか、使えるメモリはどのくらいかでも選び方は変わります。実装を選ぶ段階では、使う言語の標準ライブラリが用意する構造と、その操作の条件を確認します。

よくある疑問と、小さな確認

Q1. キューやスタックを使うには、連結リストが必要ですか？

必須ではありません。配列を使う方法など、複数の実装があります。先入れ先出し・後入れ先出しという規則と、その規則を実現する方法を分けてください。

Q2. 空になっても、取り出す操作を続けられますか？

取り出せる要素がありません。エラーにする、空であることを返す、追加を待つなど、実装や利用する機能によって対応が異なります。取り出す前の状態と、空の場合の扱いも確認が必要です。

紙にA・B・Cを書き、キューとスタックそれぞれで一件取り出した後を描いてみましょう。キューにはB・Cが残り、次はB。スタックには下からA・Bが残り、次はBです。次の一件は同じでも、それまでの取り出し順が違うことまで説明できれば、規則を追えています。

紙のカードは、作業をやめても机に残せます。では、アプリの中にためた記録は、アプリを閉じた後も残るのでしょうか。取り出す規則とは別に、データをどこに置き、保存したかが関わります。メモリとストレージの違いで、作業中の置き場所と、次回まで残す保存先を見比べてみましょう。