こんにちは、フルスタックエンジニアのryuです。
今回は基本情報技術者試験の過去問解説です。「文字を出力するために，最小限必要となるスタックは何個か」という問題を、図解を使って一つずつ丁寧に解説していきます。
この問題で問われているのは、スタックというデータ構造の理解です。
スタックとは、データを追加するときは一番上に積み、取り出すときも一番上から取り出す後入れ先出し（LIFO：Last In First Out）のデータ構造のこと。記事の後半でスタックについても詳しく解説するので、はじめての方も安心してください。
ちなみに、スタックやキューといったデータ構造は、科目Bのアルゴリズム問題でも擬似言語の形でよく登場します。
擬似言語の読み方からしっかり対策したい方は、科目Bの擬似言語に特化した学習サイトGijiAcademyもあわせてご覧ください。
文字を出力するために最小限必要となるスタックは何個か¶
今回の記事では、以下の問題について解説します。
A，C，K，S，Tの順に文字が入力される。スタックを利用して，S，T，A，C，Kという順に文字を出力するために，最小限必要となるスタックは何個か。ここで，どのスタックにおいてもポップ操作が実行されたときには必ず文字を出力する。また，スタック間の文字の移動は行わない。
ア:1 イ:2 ウ:3 エ:4
出典：令和元年秋期 問8
答えは、『ウ』の3個です。なぜ3個必要になるのか、スタックの後入れ先出し（LIFO）のしくみと合わせて詳しく解説していきます。
スタックとは？¶
ここからは、スタックについて解説します。
スタックとはデータ構造のこと¶
スタックとは、データ構造の一つで、データを後入れ先出しする構造のことです。イメージは以下のような図になります。
スタックを覚えるためには、箱をイメージしてください。その箱の中にデータを上へ上へと積んでいきます。そしてデータを取り出すときは、一番上に積んであるデータから取り出します。
データを入れる命令をPUSH、データを取り出す命令をPOPと言います。この2つはセットで覚えておきましょう！
また、スタックと似たようなものにキューがあります。キューも基本的なデータ構造の一つですが、こちらは先に入れられたデータから順に取り出される先入れ先出し（FIFO）という点がスタックと逆になります。「スタックは後入れ先出し、キューは先入れ先出し」とセットで押さえておくと、試験でも迷いません。
スタックの動きを図解で確認¶
では、先ほどの問題を実際に解いてみましょう。ポイントは「S，T，A，C，K の順に出力するには、スタックが最低いくつ必要か」です。
まず、スタックが1つの場合を考えます。最初に出力したいのは"S"です。そこで、先に入力されてくるA，C，Kをいったんスタックに積んでおき、"S"が来たところで"S"をPUSHしてすぐにPOPします。これで"S"が出力できます。
次に、「S，T，A，C，K」の"T"を取り出します。"T"はそのままPUSHしてPOPすれば取り出すことができます。
問題はここからです。次に取り出したいのは「S，T，A，C，K」の"A"ですが、"A"はスタックの一番下に積まれているため、上に乗っているK，Cが邪魔で取り出すことができません。スタック1つでは、後から積んだ順（K→C→A）でしか取り出せないので、A，C，Kの順に出力することができないのです。このように、スタックを増やす必要があります。
そこで、スタックを増やして考えます。カギになるのは、A，C，Kを入力された順（A→C→K）のまま出力しなければならない点です。スタックが1つだと順番が逆になってしまうので、A・C・Kをそれぞれ別々のスタックに分けて積むのがポイントになります。
つまり、A，C，Kを3つのスタックに1文字ずつ振り分ければ、それぞれのスタックの一番上から A→C→K の順に取り出せます。SとTはこの3つのスタックを使い回せるので、最小限必要となるスタックは3個というわけです。
それでは、スタック3つの場合で検証してみましょう。まず"S"を出力します。
次に"T"を出力します。
残りの"A，C，K"を順に出力すると、「S，T，A，C，K」という文字を取り出すことができます。
図の流れを追っていくと、データがどう動くのかがイメージしやすくなりますよ！
過去問解説まとめ¶
今回の記事では、以下の問題について解説しました。
A，C，K，S，Tの順に文字が入力される。スタックを利用して，S，T，A，C，Kという順に文字を出力するために，最小限必要となるスタックは何個か。ここで，どのスタックにおいてもポップ操作が実行されたときには必ず文字を出力する。また，スタック間の文字の移動は行わない。
ア:1 イ:2 ウ:3 エ:4
出典：令和元年秋期 問8
答えは、『ウ』の3個です。LIFOはアルゴリズムを考えるうえで基本的な内容になるので、しっかり覚えておきましょう。
そして、こうしたアルゴリズムは科目Bで擬似言語として出題されます。擬似言語のトレースに苦手意識がある方は、GijiAcademyの科目B・擬似言語対策で手を動かしながら練習するのがおすすめです。
また、当ブログを運営しているInfraAcademyでは、LinuxやネットワークをシミュレーターでハンズオンしながらインフラエンジニアやLPICの学習ができます。
基本情報の勉強と並行して、実際に手を動かしてインフラの知識も身につけたい方はぜひご利用ください。
以上で解説を終わります。当ブログでは、このようなネットワークに関する内容や基本情報技術者試験の過去問解説をしているので、興味のある方は引き続きご覧ください。
あわせて読みたい - 基本情報技術者試験にオススメ参考書5選紹介！【午前・午後問題をしっかり対策できる参考書】 - 基本情報技術者試験を合格するために必要な勉強時間は？【最短の勉強時間で合格する方法】 - 基本情報技術者試験を高校生で取得するには？難易度は？勉強方法は？【現役エンジニアが解説】 - 基本情報技術者試験の午後問題の対策方法とは？【長文を理解するの能力を身に付ける！】
