データ構造(全53問中6問目)
No.6解説へ
A，C，K，S，Tの順に文字が入力される。スタックを利用して，S，T，A，C，Kという順に文字を出力するために，最小限必要となるスタックは何個か。ここで，どのスタックにおいてもポップ操作が実行されたときには必ず文字を出力する。また，スタック間の文字の移動は行わない。
出典：令和元年秋期 問 8
- 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個必要です。
スタックでは、データを追加する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個必要です。
広告