問題プレビューID: 0a8461c3基本情報技術者試験 2019年(令和元年度)秋期 午前

問 8
基本情報技術者試験 2019年(令和元年度)秋期 午前

A, C, K, S, T の順に文字が入力される。スタックを利用して,S, T, A, C, K という順に文字を出力するために,最小限必要となるスタックは何個か。ここで,どのスタックにおいてもポップ操作が実行されたときには必ず文字を出力する。また,スタック間の文字の移動は行わない。

解説

正解は「ウ」です。

スタックは「後入れ先出し (LIFO: Last In, First Out)」のデータ構造です。 最初に入力される A, C, K は、出力される順番が A → C → K となります。つまり、先に入力されたものが先に出力される「先入れ先出し」の順番を保たなければなりません。 もし A の上に C を積むと、ポップ(出力)したときに C が A より先に出てしまいます。したがって、A, C, K はそれぞれ別のスタックに積む必要があります。

入力順と出力順の対応を追ってみます:

  1. A が入力される → スタック1 にプッシュ(積む)
  2. C が入力される → スタック1 に積むと A より先に出力されてしまうため、新しいスタック2 にプッシュ
  3. K が入力される → C の上に積むと K が先に出力され、A の上に積んでも K が先に出力されるため、新しいスタック3 にプッシュ
  4. S が入力される → そのまま出力(ポップ)すればよいため、どこにも積まずに出力するか、空いているスタックに積んで即座にポップ。
  5. T が入力される → そのまま即座に出力。
  6. この時点でスタックに残っている A, C, K を、スタック1、スタック2、スタック3 からそれぞれ順番にポップして出力する。

このように、出力順序を守るためには、少なくとも「A」「C」「K」を退避させるための 3つの独立したスタック が必要になります。したがって、最小限必要なスタックは 3 個(ウ)です。

関連問題

本文が同じ・似ている問題を表示しています