基本情報技術者試験

文字を出力するために最小限必要となるスタックは何個か | 基本情報過去問解説

PCでコーディング

こんにちは、フルスタックエンジニアのryuです。

今回の記事は、基本情報の過去問解説です。文字を出力するために,最小限必要となるスタックは何個かという問題について解説します。スタックとは、データ追加のときは最後にデータを追加し、データ取り出しのときはデータの最後から取り出す後入れ先出し(LIFO)のデータ構造です。スタックについても詳しく解説します。

文字を出力するために最小限必要となるスタックは何個か

今回の記事では、以下の問題について解説します。

A,C,K,S,Tの順に文字が入力される。スタックを利用して,S,T,A,C,Kという順に文字を出力するために,最小限必要となるスタックは何個か。ここで,どのスタックにおいてもポップ操作が実行されたときには必ず文字を出力する。また,スタック間の文字の移動は行わない。

ア:1

イ:2

ウ:3

エ:4

出典:令和元年秋期 問8

答えは、『ウ』の3回です。今回の記事では、スタックの後入れ先出し(LIFO)について詳しく解説します。

スタックとは?

ここからは、スタックについて解説します。

スタックとはデータ構造のこと

スタックとは、データ構造のことでデータを後入れ先出しする構造のことです。イメージは以下のような図になります。

スタックの構造
引用:スタック – Wikipedia

スタックを覚えるためには、箱をイメージしてください。その中にデータを積んでいきます。そしてデータを取り出すときは上に積んであるデータを取り出します。

ータを入れる命令をPUSH、データを取り出す命令をPOPと言います。覚えておきましょう!

また、スタックと似たようなものにキューがあります。キューも基本的なデータ構造の一つで、先に入れられたデータから順に取り出されます。

スタックの動きを解説

では、先ほどの問題について考えてみましょう。指定された文字列を出力する場合に最低限必要な個数を求めます。

まず、スタック1つの場合です。S,T,A,C,K」という文字を取り出すために、”S”までpushして取り出します。

スタックのデータの流れ1

次に、「S,T,A,C,K」の”T”を取り出します。”T”はそのままpushしてpopすれば取り出すことができます。

スタックのデータの流れ2

次は、「S,T,A,C,K」の”A”を取り出します。この場合、”A”は一番下にあるため、取り出すことはできません。このようにスタック1つの場合は、Aを取り出すことができないため、スタックを増やす必要があります。

スタックのデータの流れ3

今回の問題では、スタックを3つまで増やすことで希望の文字列を出力することができます。先ほどと同様の流れをスタックを一つずつ増やして検証する必要があります。

スタックを3つの場合で検証してみましょう。まず”S”を出力します。

スタックのデータの流れ4

次に”T”を出力します。

スタックのデータの流れ5

残りの”A,C,K”を順に出力すると、「S,T,A,C,K」という文字を取り出すことができます。

スタックのデータの流れ6

このような流れを理解するとデータの流れを理解することができます!

過去問解説まとめ

今回の記事では、以下の問題について解説しました。

A,C,K,S,Tの順に文字が入力される。スタックを利用して,S,T,A,C,Kという順に文字を出力するために,最小限必要となるスタックは何個か。ここで,どのスタックにおいてもポップ操作が実行されたときには必ず文字を出力する。また,スタック間の文字の移動は行わない。

ア:1

イ:2

ウ:3

エ:4

出典:令和元年秋期 問8

答えは、『ウ』の3回です。LIFOはアルゴリズムを考えるうえで基本的な内容になるので覚えておきましょう。

以上で解説を終わります。当ブログでは、このようなネットワークに関する内容や基本情報技術者試験の過去問解説をしているので興味のある方は引き続きご覧ください。

参考書を読む人
基本情報技術者試験過去問解説まとめ 午前問題過去問解説 基本情報技術者試験の過去問題を詳しく解説します。エンジニアの経験から実践を交えながら解説します! ...

About me
大手メーカのIT部門→上場ベンチャーでフルスタックエンジニアやってます。エンジニア歴は8年目。 サーバ、ネットワーク、セキュリティ、クラウドについて投稿します。 AI、ARも勉強中です! youtubeでも技術ネタを発信していきます。↓のアイコンよりご覧ください!

UdemyでIT講座をチェック!

  • セールだと1500円前後!
  • 無料サンプル講義動画・無料講義動画あり!
  • 気に入らなければ30日間返金保証!