基本情報技術者 2012年 秋期 午前（科目A） 問05

四つのデータを逆順に並べ替えるときの deq_push 回数【午前2 解説】

要点まとめ

• 結論：deq_pushは最小で3回。先頭から3個をスタックに移し，残ったDを先頭にしてからスタックを順にキューへ戻せばD,C,B,Aになります。
• 根拠：スタックはLIFOなので，先にスタックへ入れた要素ほど後にキューに戻り，これを利用して順序を逆にできます。
• 差がつくポイント：全要素を一度にスタックに移す必要はないと認識し，最後の要素をキューに残す発想でdeq_push回数を減らせます。

正解の理由

よくある誤解

• 「全要素を一度スタックへ移さないと逆順にならない」：最後の要素をキューに残せば良く，すべて移す必要はありません。
• 「pop_enq の回数も同じだけ数えるべき」：問題は deq_push の最小回数を問うており，pop_enq は数える対象外ですが，実際には deq_push = 3 に対して pop_enq = 3 で済みます。
• 「キューの前後の向きを取り違える」：問題文の「この順に入っている」は先頭が A, 末尾が D と理解する点を誤ると解答を間違えます。

解法ステップ

1. 初期状態：キュー Q = [A, B, C, D]（先頭左），スタック S = []（上が左側表記）。
2. deq_push を3回実行：
   • deq_push(A) → S = [A], Q = [B, C, D]
   • deq_push(B) → S = [B, A], Q = [C, D]
   • deq_push(C) → S = [C, B, A], Q = [D]
3. pop_enq を3回実行（スタックの上から順にキューの末尾へ）：
   • pop_enq() → S = [B, A], Q = [D, C]
   • pop_enq() → S = [A], Q = [D, C, B]
   • pop_enq() → S = [], Q = [D, C, B, A]
4. 結果：Q = [D, C, B, A]。deq_push の実行回数は3回で最小。

選択肢別の誤答解説

• ア: 2
  2回では先頭から2個（A,B）をスタックへ移せますが，残りのCとDを逆順で並べ替えるためにはさらにdeq_pushが必要であり，最終的にDを先頭にして完全に逆順にできません。
• イ: 3（正解）
  先頭から3個をスタックへ移し，残ったDを先頭にしてからスタックを順に戻すことでD,C,B,Aを実現します。
• ウ: 4
  4回は可能な手順（すべてスタックへ移してから戻す）ですが，最小回数ではありません。問題は最小回数を問うため不正解。
• エ: 5
  5回は不要かつ無駄な操作回数です。最小値より大きいので誤りです。

補足コラム

• 一般化：要素数を $n$ とすると，キューの順序を完全に逆転させる最小の deq_push 回数は $n-1$ です。最後の要素をキューに残し，残り $n-1$ 個をスタックに移してから順に戻せば良いためです。
• 操作計画のコツ：逆順にしたい要素のうち「最後に来るべきもの」をキューに残す発想を持つと，スタックのLIFO性を最短で活かせます。

FAQ