こんにちは、フルスタックエンジニアのryuです。
今回の記事は、基本情報の過去問解説です。文字を出力するために，最小限必要となるスタックは何個かという問題について解説します。スタックとは、データ追加のときは最後にデータを追加し、データ取り出しのときはデータの最後から取り出す後入れ先出し(LIFO)のデータ構造です。スタックについても詳しく解説します。
※本ページには、プロモーション・アフィリエイトリンクが含まれています
文字を出力するために最小限必要となるスタックは何個か
今回の記事では、以下の問題について解説します。
A，C，K，S，Tの順に文字が入力される。スタックを利用して，S，T，A，C，Kという順に文字を出力するために，最小限必要となるスタックは何個か。ここで，どのスタックにおいてもポップ操作が実行されたときには必ず文字を出力する。また，スタック間の文字の移動は行わない。
ア:1
イ:2
ウ:3
エ:4
出典：令和元年秋期 問8
答えは、『ウ』の3回です。今回の記事では、スタックの後入れ先出し(LIFO)について詳しく解説します。
スタックとは？
ここからは、スタックについて解説します。
スタックとはデータ構造のこと
スタックとは、データ構造のことでデータを後入れ先出しする構造のことです。イメージは以下のような図になります。
スタックを覚えるためには、箱をイメージしてください。その中にデータを積んでいきます。そしてデータを取り出すときは上に積んであるデータを取り出します。
データを入れる命令をPUSH、データを取り出す命令をPOPと言います。覚えておきましょう！
また、スタックと似たようなものにキューがあります。キューも基本的なデータ構造の一つで、先に入れられたデータから順に取り出されます。
スタックの動きを解説
では、先ほどの問題について考えてみましょう。指定された文字列を出力する場合に最低限必要な個数を求めます。
まず、スタック1つの場合です。「S，T，A，C，K」という文字を取り出すために、”S”までpushして取り出します。
次に、「S，T，A，C，K」の”T”を取り出します。”T”はそのままpushしてpopすれば取り出すことができます。
次は、「S，T，A，C，K」の”A”を取り出します。この場合、”A”は一番下にあるため、取り出すことはできません。このようにスタック1つの場合は、Aを取り出すことができないため、スタックを増やす必要があります。
今回の問題では、スタックを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はアルゴリズムを考えるうえで基本的な内容になるので覚えておきましょう。
以上で解説を終わります。当ブログでは、このようなネットワークに関する内容や基本情報技術者試験の過去問解説をしているので興味のある方は引き続きご覧ください。
