コンピュータではたくさんのデータを扱っていますが、データの構造にはスタックやキュー、木構造など様々な種類の構造があります。
それぞれのデータ構造には得手不得手がありますが、その中でもスタックとキューは基本構造の1つです。
スタックとは、先入れ後出しのデータ構造で、キューは先入れ先出しのデータ構造です。
今回の記事では。「スタック」と「キュー」2つのデータ構造がどのような構造かを理解し、最後には基本情報技術者試験の過去問にも挑戦することで、理解を深めていきましょう。
その他の構造に関してはこちらの記事で解説しています。
基本情報技術者対策おすすめ講座
BizLearnで科目A試験(旧午前試験)免除！
- 累計受講者数7,429万人以上のネットラーニングが提供するオンライン講座
- 科目A試験を免除できる数少ない認定講座！
- 指導者があなたに一人専属でついてくれて質問し放題で挫折しない！
Udemyで本よりお得に試験対策！
- 複数の基本情報技術者試験講座の中から自分に合った講座が選べる
- SALE狙いで圧倒的コストパフォーマンス
- 買い切り型なのでSALEで買っておいて後で勉强もOK！
STUDYing でスキマ時間で試験合格を目指す！
- スマートフォン1つで動画も問題もテキストも模試も学習できる
- 通勤通学時間などのスキマ時間で学習できる
- 36,800と安価に受講が可能
スタックは後入れ先出しのデータ構造
スタックとは、後入れ先出しの構造です。
例えば、一般的に箱の中に下から順番に本や新聞を重ねて入れていくと、先に入れたものを取り出すのに苦労したりしますよね。
このように、先に入れたものが下になって後からしか取り出せない構造になっていることをスタック構造と呼びます。
キューとは先入れ先出しのデータ構造
キュー構造は先に入れたものから先に出すデータ構造です。
わかりやすい例でいうと、1車線のトンネルを考えてみてください。最初に入った車が最初に出てきますよね。このように先に入れたデータから先に取り出せるような構造になっていることをキューと呼びます。
キューのことは、待ち行列とも呼び、ラーメン屋の行列は先に並んだ人から、お店に入れるのをイメージすると理解が深まります。
スタックとは反対の構造になっています。
LIFOとFIFOの違い
スタックやキューのことをアルファベット4文字でLIFOやFIFOと表現することがあります。
- LIFOはLast In First Outの略：最後に入れて最初から出す！
- FIFOはFirst In First Outの略：最初に入れて最初から出す！
なんでもアルファベット4文字標記にするのがIT業界あるあるです。
ただLIFOは（Last In First Out）の略称でそのまま「最後に入れたものが最初に出る」意味です。
つまりスタック型の構造です。
逆にFIFOは（First In First Out）の略称で「最初に入れたものが最初に出る」意味です。
つまりキュー型の構造のことです。
それぞれ構造の性質のことを言っているのです。
Push操作とPop操作とは？
スタックにデータを入れることをPush操作、スタックからデータを取り出すことをPop操作と呼びます。
問題文に当たり前のように出てくるので、意味だけ覚えておきましょう。
- Push操作（プッシュ）・・・スタックへデータを格納する操作のこと
- Pop操作（ポップ）・・・スタックからデータを取り出す操作のこと
スタックに関する過去問を解いてみよう！
A，C，K，S，Tの順に文字が入力される。スタックを利用して，S，T，A，C，Kという順に文字を出力するために，最小限必要となるスタックは何個か。ここで，どのスタックにおいてもポップ操作が実行されたときには必ず文字を出力する。また，スタック間の文字の移動は行わない。
出典：令和元年秋期 問8
この問題を解くにあたって理解していないといけないこと。
- スタックとはなにか
- ポップ操作とは何か
- スタックを利用して文字を出力する方法
スタックは最小で何個必要かを調べるので、
スタック一つだと「S，T，A，C，Kという順に文字を出力」できるかどうかをまず確かめます。
スタック1 の箱にA→C→K→Sの順番で入れていきます(プッシュ操作)。
スタックは後入れ先出しの性質なので、最後に入れたSを出力します(ポップ操作)。
そしてもう一度プッシュ操作を行なってTをスタック1に入れます(プッシュ操作)。
最後に入れたTが出力できるので出力します(ポップ操作)。
その次に出力できるのがKとなっていてその下のCとAは取り出せません。
つまりスタック1個だと並び替えができません。
続いてスタックが2個の場合を考えていきます。
スタックが2個、つまり箱が2個あるのをイメージしてください。
後入れ先出しできる箱が二つあるのでそれを使って並び替えができるかを確かめます。
まずスタック1の箱にA→Cと入れていきます(プッシュ操作)。
同じようにスタック2の箱にもK→Sと入れていきます(プッシュ操作)。
これでSが出力でき、Tも出力できます。
しかし次に出力したいAがCの下にあるため、出力できません。
仮にスタック1にAだけ入れて
スタック2にC→K→Sを入れたとすると、
今度はAまで出力できますが、今度はKが邪魔でCを出力できません。
よってスタックは2個でも並び替えはできません。
続いてスタックが3個の場合を考えます。
スタック1にAを、スタック2にC、スタック3にK→S、そしてスタック2にTを入れます。(あくまでも一例で入れ方は複数あります)
後入れ先出しの性質より一番上のSとTとAは出力できます。
そして残りのCとKも取り出せる位置にあるので、
スタックが3つあると並び替え可能とわかりました。
よって答えは3個となります。
まとめ
今回はスタック操作についてまとめていきました。
プッシュ操作、ポップ操作や、LIFO、FIFOなどのワードは問題文で出てきたときに問題を理解するために覚えておく必要があります。
これからも過去問を解説していくので一緒に理解していきましょう！
BizLearnは本記事のまとめ
- スタック・・・後に入れたものを先に出す性質(LIFOとも呼ぶ)のある箱のこと！
- キュー・・・先に入れたものを先に出す性質(FIFO)のある箱のこと！
- Push操作・・・スタックやキューにデータを入れること！
- Pop操作・・・スタックやキューからデータを取り出すこと！
