【基本情報】スタックとキューってなに？どこで使われている？

正解は”ウ”

実際に検証しながら最小限必要なスタックの数を確かめましょう。

●スタックが1個の場合
最初にSをポップする必要があるのでSがプッシュされるまでひたすらプッシュを繰り返します。
・Aをプッシュ：{A}
・Cをプッシュ：{A,C}
・Kをプッシュ：{A,C,K}
・Sをプッシュ：{A,C,K,S}
やっとSが来たので、Sをポップします。
・Sをポップ　：{A,C,K}<S>
次にTをポップする必要があるのでTが来るまでプッシュを繰り返します。
・Tをプッシュ：{A,C,K,T}<S>
Tが来たので、Tをポップします。
・Tをポップ　：{A,C,K}<S,T>
次にポップしたいのはAですが、待機しているのはKなのでNGです。
よって、スタックが1個では無理でした。

●スタックが2個の場合
最初にSをポップする必要があるのでSが来るまでプッシュを繰り返します。Sをプッシュする手前の形は以下の4通りが考えれます。
①{A,C,K}&{}
②{A,C}&{K}
③{A,K}&{C}
④{A}&{C,K}

しかし、ポップする順番はS→T→A→C→Kです。つまり、AはCやKよりも先に取り出す必要があります。よってAの後ろにCやKが入っている①②③はこの時点でNGとなります。また、CはKよりも先に取り出す必要がありますが、④だとK→Cの順番でしか取り出せません。よって④もNGとなり、スタックが2個でも無理だと分かります。

●スタックが3個の場合
同じようにSをプッシュする手前の形を考えます。
①{A,C,K}&{}&{}
②{A,C}&{K}&{}
③{A,K}&{C}&{}
④{A}&{C,K}&{}
⑤{A}&{C}&{K}

Aよりも先にCとKが入っている①②③はNG、Cよりも先にKが入っている④はNGです。なので⑤だけに焦点を当てて続きを考えます。

次にプッシュするのはSですが、すぐにプルするのでどのスタックに入れても同じです。
⑥{A,S}&{C}&{K}　→　{A}&{C}&{K}<S>
⑥{A}&{C,S}&{K}　→　{A}&{C}&{K}<S>
⑥{A}&{C}&{K,S}　→　{A}&{C}&{K}<S>

次にプッシュするTもすぐにプルするのでどこに入れても⑦の状態になりますね。
⑦{A}&{C}&{K}<S,T>

あとは、A→C→Kの順番でそれぞれのスタックから取り出せば良いだけです。
⑧{}&{C}&{K}<S,T,A>
⑨{}&{}&{K}<S,T,A,C>
⑨{}&{}&{}<S,T,A,C,K>

よって、最小限必要なスタックの個数は3個です。

正解は”ア”

●初期状態
A  B  C

●ƒ()を呼び出す（1回目）
この時点でAは空ではありません。なのでAからpopした値をCにpushします。スタックなのでAは最後にpushした3をpopします。
A  B  C

ここで再度ƒ()を呼び出します。再度呼び出したƒ()の処理が完了した後、「Cからpopした値をBにpushする」という処理が残っていることを忘れないで下さい。

●ƒ()を呼び出す（2回目）
1回目と同じようにAからpopした値をCにpushします。
A  B  C

ここで再度ƒ()を呼び出します。注意点は1回目と同じです。

●ƒ()を呼び出す（3回目）
1回目と同じようにAからpopした値をCにpushします。
A[1]  B  C

ここで再度ƒ()を呼び出します。注意点は1回目と同じです。

●ƒ()を呼び出す（4回目）
Aが空なので何もせずに終了します。
A[]  B  C

ここで3回目のƒ()の続きに戻ります。

●ƒ()を呼び出す（3回目続き）
Cからpopした値をBにpushします。
A[]  B  C

ここで2回目のƒ()の続きに戻ります。

●ƒ()を呼び出す（2回目続き）
Cからpopした値をBにpushします。
A[]  B  C

ここで2回目のƒ()の続きに戻ります。

●ƒ()を呼び出す（1回目続き）
Cからpopした値をBにpushします。
A[]  B  C

これで処理は終了です。

正解は”ウ”

待ち行列はいわゆるお店の行列のようにデータの挿入と取り出しを行います。なので先に挿入したデータを先に取り出すキュー構造となります。

それでは実際にデータの状態遷移を見てみましょう。

1. ENQ 1：
2. ENQ 2：
3. ENQ 3：
4. DEQ：[2,3]→1
5. ENQ 4：[2,3,4]
6. ENQ 5：[2,3,4,5]
7. DEQ：[3,4,5]→2
8. ENQ 6：[3,4,5,6]
9. DEQ：[4,5,6]→3
10. DEQ：[5,6]→4
11. DEQ：[6]→5

最後に取り出されるのは5になるので、答えはウになります。

正解は”ウ”

スタックの状態は下図のように遷移します。

よって答えはウです。

正解は”ウ”

【アの検証】→[A,D,B,C]は出力可能？
●最初にAを出力するので、スタックしたAはすぐにプッシュします。
1.スタック{A}　出力[]
2.スタック{}　出力[A]

●次にDを出力するので、Dをスタックするまでスタックし続けます。
3.スタック{B}　出力[A]
4.スタック{B,C}　出力[A]
5.スタック{B,C,D}　出力[A]

●全てのデータをスタックしたので、後はプッシュするだけです。
6.スタック{B,C}　出力[A,D]
7.スタック{B}　出力[A,D,C]　→この時点でアの形にはなりません。

【イの検証】→[B,D,A,C]は出力可能？
●最初にBを出力するので、Bをスタックするまでスタックし続けます。
1.スタック{A}　出力[]
2.スタック{A,B}　出力[]

●Bをスタックしたので、Bを出力します。
3.スタック{A}　出力[B]

●次にDを出力するので、Dをスタックするまでスタックし続けます。
4.スタック{A,C}　出力[B]
5.スタック{A,C,D}　出力[B]

●全てのデータをスタックしたので、後はプッシュするだけです。
6.スタック{A,C}　出力[B,D]
7.スタック{A}　出力[B,D,C]　→この時点でイの形にはなりません。

【ウの検証】→[C,B,D,A]は出力可能？
●最初にCを出力するので、Cをスタックするまでスタックし続けます。
1.スタック{A}　出力[]
2.スタック{A,B}　出力[]
3.スタック{A,B,C}　出力[]

●Cをスタックしたので、Cを出力します。
4.スタック{A,B}　出力[C]

●次に出力するのはBなので、Bをプッシュします。
5.スタック{A}　出力[C,B]

●次にDを出力するので、Dをスタックするまでスタックし続けます。
5.スタック{A,D}　出力[C,B]

●全てのデータをスタックしたので、後はプッシュするだけです。
6.スタック{A}　出力[C,B,D]
7.スタック{}　出力[C,B,D,A]　→ウの形になりました。

【エの検証】→[D,C,A,B]は出力可能？
●最初にDを出力するので、Dをスタックするまでスタックし続けます。
1.スタック{A}　出力[]
2.スタック{A,B}　出力[]
3.スタック{A,B,C}　出力[]
4.スタック{A,B,C,D}　出力[]

●全てのデータをスタックしたので、後はプッシュするだけです。
5.スタック{A,B,C}　出力[D]
6.スタック{A,B}　出力[D,C]
7.スタック{A}　出力[D,C,B]　→この時点でエの形にはなりません。

よって、答えはウになります。