36-02. データ構造（スタック/キュー）

（復習）データ構造とは？

コンピュータのプログラムはバラバラなデータを扱うことは難しいので、データ構造という形で整理整頓したデータ形式・仕組みを事前に用意しています。

ITパスポート試験で出題されるデータ構造は次表になります。

用語	説明
変数	1つのデータを格納するデータ構造
配列	複数のデータを連続的に格納するデータ構造
リスト	複数のデータを順序づけて格納するデータ構造
木構造	階層を持つデータ構造
2分木	全ての枝が2本の木構造
スタック	データ（要素）が入ってきた順に、積み上げていくデータ構造 ・プッシュ（挿入）、ポップ（取り出し） ・LIFO（後入れ先出法）
キュー	データ（要素）が入ってきた順に、並べていくデータ構造 ・エンキュー（挿入）、デキュー（取り出し） ・FIFO（先入れ先出法）

このページでは、『スタック』と『キュー』について解説します。スタックとキューはITパスポート試験で頻出なので、しっかりと理解しましょう。

スタック

スタックとは、データが入ってきた順に積み上げていくデータ構造です。
※stack:積み重ね

スタックへのデータの挿入をプッシュ（PUSH）、取り出しをポップ（POP）といいます。

具体的に、スタックへのデータの挿入と取り出しを順に確認していきましょう。

まず、スタックへ「１→２→３」の順にデータを挿入します。

スタックには、下から「１→２→３」の順番にデータが積み上がっていきます。

このデータを取り出したい場合、スタックは一番上にあるデータからしか取り出すことができません。

したがって、「３→２→１」の順でスタックから取り出されます。

データを挿入した順番は「１→２→３」ですが、取り出される順番は「３→２→１」となり、後に入れたデータが先に取り出されています。

このスタックの動作をLIFO（Last In First Out：後入れ先出し法）とよびます。

この動作原理は頻出ですのでしっかりと理解しておきましょう。

【例題】スタック

ITパスポート試験での『スタック』の出題例を確認しておきましょう。

下から上へ品物を積み上げて，上にある品物から順に取り出す装置がある。この装置に対する操作は，次の二つに限られる。

PUSH x：品物xを1個積み上げる。
POP：一番上の品物を1個取り出す。

最初は何も積まれていない状態から開始して，a，b，cの順で三つの品物が到着する。一つの装置だけを使った場合，POP操作で取り出される品物の順番としてあり得ないものはどれか。

ア）a，b，c
イ）b，a，c
ウ）c，a，b
エ）c，b，a

出典：令和元年秋期　問62

キュー

キューとは、データが入ってきた順番に並べていくデータ構造です。
※queue:列

キューへのデータの挿入をエンキュー、取り出しをデキューと呼びます。

具体的に、キューへのデータの挿入（エンキュー）と取り出し（デキュー）を順に確認しましょう。

例えば、キューへ「１→２→３」の順にデータを挿入します。

右（前）から「１→２→３」の順番にデータが並んでいきます。

このデータを取り出したい場合、キューは一番右（前）にあるデータからしか取り出すことができません。

したがって、「１→２→３」の順でキューから取り出されます。

キューにデータを挿入した順番と取り出される順番ともに「１→２→３」となります。つまり、先に入れたデータが先に取り出されています。この動作をFIFO（Fast In First Out：先入れ先出し法）と呼びます。

スタック同様、キューの動作原理も頻出ですのでしっかり押さえておきましょう。

【例題】キュー

あるキューに要素”33″，要素”27″及び要素”12″の三つがこの順序で格納されている。このキューに要素”45″を追加した後に要素を二つ取り出す。2番目に取り出される要素はどれか。
ア）12
イ）27
ウ）33
エ）45

出典：平成23年特別　問58

【まとめ】データ構造（スタック、キュー）

それでは最後におさらいをしておきましょう。

用語	説明
スタック	データ（要素）が入ってきた順に、積み上げていくデータ構造 後に入れたデータが先に出てくる（LIFO：後入れ先出法） ・プッシュ（挿入）、ポップ（取り出し）
キュー	データ（要素）が入ってきた順に、並べていくデータ構造 先に入れたデータが先に出てくる（FIFO：先入れ先出法） ・エンキュー（挿入）、デキュー（取り出し）