スポンサーリンク

36-02. データ構造(スタック/キュー)

スポンサーリンク
ITパスポート
スポンサーリンク

(復習)データ構造とは?

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

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

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

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

スポンサーリンク

スタック

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

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

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

スタックの挿入(PUSH、プッシュ)


まず、スタックへ「1→2→3」の順にデータを挿入します。

スタックの挿入後(PUSH、プッシュ)

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

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

スタックの取り出し(POP、ポップ)

したがって、「3→2→1」の順でスタックから取り出されます

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

このスタックの動作を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
[解答・解説]
スタックは積み上げていくデータ構造なので、最後に格納(PUSH:プッシュ)をしたデータから、取り出し(POP:ポップ)ができます。

cを最初に取り出す場合、スタックには下から『a→b』と積みあがっているので、bよりも先にaを取り出すことはできません

したがって、『ウ)c,a,b』になります。
スポンサーリンク

キュー

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

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

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

キューの挿入(エンキュー)

例えば、キューへ「1→2→3」の順にデータ挿入します。

キューの挿入後(エンキュー)

右(前)から「1→2→3」の順番にデータが並んでいきます。

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

キューの取り出し(デキュー)

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

キューにデータを挿入した順番と取り出される順番ともに「1→2→3」となります。つまり、先に入れたデータが先に取り出されています。この動作をFIFO(Fast In First Out:先入れ先出し法)と呼びます。

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

【例題】キュー

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

出典:平成23年特別 問58
[解答・解説]
キューは順番に並べていくデータ構造なので、最初に格納(エンキュー)したデータから取り出し(デキュー)できます。

キューには、前から「33→27→12→45」で格納されているので、2番目に取り出されるのは、27です。

したがって、『イ)27』になります。

スポンサーリンク

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

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

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

コメント

タイトルとURLをコピーしました