問８
Ａ、Ｃ、Ｋ、Ｓ、Ｔの順に文字が入力される。スタックを利用して、Ｓ、Ｔ、Ａ、Ｃ、Ｋという順に文字を出力するために、最小限必要となるスタックは何個か。ここで、どのスタックにおいてもポップ操作が実行されたときには必ず文字を出力する。また、スタック間の文字の移動は行わない。
ア １ イ ２ ウ ３ エ ４
正解
ウ
解説
スタックは、後入れ先出し方式 (LIFO) により、処理中のデータを一時的に保管するための記憶領域のことである。
スタックに入れる操作をPUSH、
スタックから出す操作をPOP、
スタック１つ分を ( ) に入れ、
スタックは下から上に積まれるイメージだが、便宜上左から順に表記すると、
■スタックが１つの場合
PUSH:A (A)
PUSH:C (A, C)
PUSH:K (A, C, K)
PUSH:S (A, C, K, S)
POP:S (A, C, K) ・・・S
次に、Aをスタックから出せない。
■スタックが２つの場合
PUSH:A (A)
PUSH:C (A) と (C)
PUSH:K (A) と (C, K)
PUSH:S (A) と (C, K, S)
POP:S (A) と (C, K) ・・・S
PUSH:T (A) と (C, K, T) ・・・S
POP:T (A) と (C, K) ・・・ST
POP:A () と (C, K) ・・・STA
次に、Cをスタックから出せない。
※他にパターンがあるが、いずれも失敗する。
■スタックが３つの場合
PUSH:A (A)
PUSH:C (A) と (C)
PUSH:K (A) と (C) と (K)
PUSH:S (A) と (C) と (K, S)
POP:S (A) と (C) と (K) ・・・S
PUSH:T (A) と (C) と (K, T) ・・・S
POP:T (A) と (C) と (K)・・・ST
POP:A () と (C) と (K) ・・・STA
POP:C () と () と (K) ・・・STAC
POP:K () と () と () ・・・STACK
よってスタックが最小限3個あれば、STACKという文字を出力できる。
