二つのスタックでキュー(FIFO)を実現する

解説

この問題は、二つのスタックでキュー（FIFO）を実現する典型的なデータ構造の問題である。 【アルゴリズムの考え方】 要素の追加は inStack に push する。取り出し時に outStack が空であれば、inStack の全要素を outStack に移し替える。スタックは後入れ先出し（LIFO）なので、移し替えると順序が反転し、最初に追加した要素が outStack の先頭に来る。outStack に要素が残っていれば移し替えは不要である。 【トレース】 (1) q.追加(10): inStack=[10], outStack=[] (2) q.追加(20): inStack=[10,20], outStack=[] (3) q.取出し(): outStack が空である → true → if に入る while(inStack が空でない): pop 20 → outStack に push: inStack=[10], outStack=[20] pop 10 → outStack に push: inStack=[], outStack=[20,10] outStack から pop → 10 を返す。outStack=[20] ✓ (4) q.追加(30): inStack=[30], outStack=[20] (5) q.取出し(): outStack が空である → false → if をスキップ outStack から pop → 20 を返す。outStack=[] ✓ (6) q.取出し(): outStack が空である → true → if に入る while(inStack が空でない): pop 30 → outStack に push: inStack=[], outStack=[30] outStack から pop → 30 を返す。outStack=[] ✓ 以上により、取出しの結果は 10、20、30 の順となり、FIFO として正しく動作する。よって正解はアである。

選択肢ごとの解説

ア

正解。outStack が空のときだけ inStack の全要素を移し替えることで、FIFO の順序が正しく保たれる。

イ

誤り。if 条件で outStack が空であることを確認した直後に while で outStack が空でないかを判定するため、ループ本体は一度も実行されない。結果として要素が移されず、空の outStack から pop しようとしてエラーとなる。

ウ

誤り。outStack にまだ要素が残っている場合でも inStack から移し替えてしまう。追加(30) の後の2回目の取出しで、outStack に残っていた 20 の上に 30 が積まれ、30 が先に返されて FIFO 順が崩れる。

エ

誤り。ループ条件が outStack が空である間だけ回るので、1要素を移した時点で outStack が空でなくなりループが終了する。inStack の全要素が移されないため、最初の取出しで 20（後から追加した値）が返され FIFO 順にならない。

オ

誤り。if の条件が逆になっている。outStack が空でないとき（既に取り出せる要素があるとき）に移し替えを行い、outStack が空のとき（移し替えが必要なとき）にはスキップしてしまうため、空の outStack から pop してエラーとなる。

カ

誤り。while の条件が逆になっている。inStack が空であるときにループを回そうとするが、if に入った時点で outStack は空であり、inStack には要素がある。inStack が空でないためループ本体は実行されず、空の outStack から pop してエラーとなる。

登録すると解いた結果が残り、間違えた問題は日をおいて復習に出ます。