データ構造のスタックとキューを図で解説【基本情報技術者試験対策】

基本情報技術者試験対策として、スタックとキューを図解でわかりやすく解説します。

LIFO・FIFOの違いやPUSH・POP・ENQUEUE・DEQUEUEの操作、利用例を説明しています。

データ構造について

データ構造とは、データを効率よく格納し、検索・追加・削除などの操作を行いやすくするための仕組みです。

基本情報技術者試験では、配列、リスト、スタック、キュー、木構造がありますが、本書はスタック、キューについて説明します。

配列とリストの説明はこちらを参照してください。

スタックとキューは、データを一時的に保存し、決められた順番で取り出すためのデータ構造です。

スタックとキューは、どちらもデータの追加と取り出しを行いますが、取り出す順番が異なります。

例えば、スタックは本を積み重ねる場合は最後に置いた本から取り出す考え方です。
キューは、レジ待ちの列では最初に並んだ人から順番に案内される考え方です。

詳しくは次の章で説明します。

スタックは、最後に追加したデータを最初に取り出すデータ構造です。

つまり、先入れ後出し（LIFO：Last In, First Out）という考え方です。

スタックは下の絵のように、容器にデータを追加していき、取り出すときは上から取り出されます。

なお、この仕組みを活用して、データの順番を逆にしたい場合に適しています。

■スタックの特徴
データの追加と取り出しは、常にスタックのトップで行う

PUSH（プッシュ）とは、新しいデータを追加する操作です。
追加データはスタックの一番上（トップ）に配置されます。

例えば、スタックに「1」「2」「3」を順番にPUSHすると、3が一番上になります。

POP（ポップ）とは、スタックの一番上（トップ）にあるデータを取り出し、スタックから削除する操作です。

例えば、上のスタックでPOPを繰り返すと、「3 → 2 → 1」の順番で取り出されます。

スタックは、最後に行った処理を最初に取り消したい場面でよく利用されます。

キューとは、最初に追加したデータを最初に取り出す（FIFO：First In, First Out）データ構造です。

データは後ろ（リア）から追加し、前（フロント）から取り出します。

キューの特徴やイメージは次の通りです。

■キューの特徴
データは後ろ（リア）から追加し、前（フロント）から取り出します。

ENQUEUE（エンキュー）とはキューにデータを追加する操作です。
追加データはキューの後ろ（リア）に配置されます。

DEQUEUE（デキュー）とは、キューの前（フロント）にあるデータを取り出す操作です。

キューは、先に受け付けたデータから順番に処理したい場合に利用されるデータ構造です。

腕試し（理解テスト）に挑戦する場合はこちらをクリック。