A、C、K、S、Tの順に文字が入力される。スタックを利用して、S、T、A、C、Kという順に文字を出力するために、最小限必要となるスタックは何個か。ここで、どのスタックにおいてもポップ操作が実行されたときには必ず文字を出力する。また、スタック間の文字の移動は行わない。
ア 1 イ 2 ウ 3 エ 4
ウ
スタックは、後入れ先出し方式 (LIFO) により、処理中のデータを一時的に保管するための記憶領域のことである。
スタックに入れる操作をPUSH、
スタックから出す操作をPOP、
スタック1つ分を ( ) に入れ、
スタックは下から上に積まれるイメージだが、便宜上左から順に表記すると、
■スタックが1つの場合
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をスタックから出せない。
■スタックが2つの場合
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をスタックから出せない。
※他にパターンがあるが、いずれも失敗する。
■スタックが3つの場合
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という文字を出力できる。
| 問７ | 目次 | 問９ |