【基本情報技術者試験】データ構造のスタックとは？キューとの違いもわかりやすく解説！

コンピュータではたくさんのデータを扱っていますが、データの構造にはスタックやキュー、木構造など様々な種類の構造があります。

それぞれのデータ構造には得手不得手がありますが、その中でもスタックとキューは基本構造の1つです。

スタックとは、先入れ後出しのデータ構造で、キューは先入れ先出しのデータ構造です。

今回の記事では。「スタック」と「キュー」2つのデータ構造がどのような構造かを理解し、最後には基本情報技術者試験の過去問にも挑戦することで、理解を深めていきましょう。

その他の構造に関してはこちらの記事で解説しています。

スタックは後入れ先出しのデータ構造

スタックとは、後入れ先出しの構造になっていることをいいます。

例えば、一般的に箱の中に下から順番に本や新聞を重ねて入れていくと、

先に入れたものを取り出すのに苦労したりしますよね。

このように、先に入れたものが下になって後からしか取り出せない構造になっていることをスタックといいます。

キューとは先入れ先出しのデータ構造

キュー構造は先に入れたものから先に出すデータ構造のことです。

一般的にトンネルに入っていった車が追い越し禁止をしっかり守っていることを前提にすると先に入った車が先に出てくるようになっていますよね。

このように先に入れたデータから先に取り出せるような構造になっていることをキューと呼びます。

キューのことは、待ち行列とも呼び、ラーメン屋の行列は先に並んだ人から、お店に入れるのをイメージすると理解が深まります。

スタックとは反対の構造になっています。

LIFOとFIFOの違い

なんでもアルファベット4文字標記にすると覚えづらかったりします。

ただ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などのワードは問題文で出てきたときに問題を理解するために覚えておく必要があります。

これからも過去問を解説していくので一緒に理解していきましょう！