令和元年秋期試験午前問題 問8

午前試験免除制度対応!基本情報技術者試験のeラーニング【独習ゼミ】
A,C,K,S,Tの順に文字が入力される。スタックを利用して,S,T,A,C,Kという順に文字を出力するために,最小限必要となるスタックは何個か。ここで,どのスタックにおいてもポップ操作が実行されたときには必ず文字を出力する。また,スタック間の文字の移動は行わない。

  • 1
  • 2
  • 3
  • 4
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:データ構造
スタックは、データ追加のときは最後尾にデータを追加し、データ取り出しのときはデータの最後尾から取り出す後入れ先出し(LIFO:Last-in First-out)のデータ構造です。
スタックでは、データを追加するPUSH命令、データを取り出すPOP命令を使用してデータ操作を行います。

まず、スタック構造の動作を確認する意味を含めて1つの場合で試してみます。※[]の中を各スタックの内容として考えてください。一番右が最後尾のデータです。

push A:[A]
push C:[A,C]
push K:[A,C,K]
push S:[A,C,K,S]
pop  :[A,C,K] → Sを出力
push T:[A,C,K,T]
pop  :[A,C,K] → Tを出力
pop  :[A,C,K] → Kを出力 //×

STに続いてAが出力できないので無理です。

次にスタックを2つ用意した場合を考えてみます。

push A:[A] []
push C:[A] [C]
push K:[A,K] [C] または [A] [C,K] //×


AをCより先にpopするには、CをAとは別のスタックに積む必要があります。その後、Kを積むと、AとCKより先に出力することができなくなってしまうので、目的の順番で出力できません。

スタックを3つ用意すると、CKよりも先に出力したいAを退避させておくことができます。

push A:[A] [] []
push C:[A] [C] []
push K:[A] [C] [K]
push S:[A] [C] [K,S]
pop  :[A] [C] [K] → Sを出力
push T:[A] [C] [K,T]
pop  :[A] [C] [K] → Tを出力
pop  :[] [C] [K] → Aを出力
pop  :[] [] [K] → Cを出力
pop  :[] [] [] → Kを出力

したがって、S,T,A,C,Kという順に文字を出力するためには、最低限スタックが3個必要です。

Pagetop