過去問解きまくり研究所

平成23年度 秋期 午前 問5

データ構造

スタックに関する問題

スタック1，2があり，図の状態になっている。関数 f はスタック1からポップしたデータをそのままスタック2にプッシュする。関数 g はスタック2からポップしたデータを出力する。b，c，d，a の順番に出力するためには，関数をどの順で実行すればよいか。

〔図〕
  スタック1              スタック2
┌─────┐            ┌ ─ ─ ─ ┐
│ （空き）│            ┊ （空き）┊
├─────┤            ├ ─ ─ ─ ┤
│    a    │ ← 上端     ┊       ┊
├─────┤            ├ ─ ─ ─ ┤
│    b    │            ┊       ┊
├─────┤            ├ ─ ─ ─ ┤
│    c    │            ┊       ┊
├─────┤            └ ─ ─ ─ ┘
│    d    │
└─────┘            （スタック2は空・仕切りは点線）
答えと解説を見る

✓ これが正解イf, f, g, f, g, f, g, g

解説

先に二つ移し、あとは移すことと出すことを交互にします。

スタックは最後に入れたものが先に出る入れ物です。一方の関数は片方からポップした値をもう一方へプッシュし、他方の関数は積まれた側からポップして出力します。求められている出力の並びは、もとの並びの二番目から順に下へ進み、最後に先頭の値が来る形です。ですから先頭の値は早いうちに移してしまい、出力せずに底へ沈めておく必要があります。移す関数を続けて二回実行すると、先頭の値が下、二番目の値が上に積み上がります。ここで出す関数を一回実行すれば、二番目の値が出ます。あとは、次の値を一つ移してはすぐ出す、という組合せを繰り返せば、もとの並びの順に取り出せます。最後に底へ沈めておいた先頭の値だけが残るので、それを出して終わりです。判定の軸は、出す操作をはさむ間隔が、底へ沈めた値を途中で掘り出さない形になっているかどうかです。

ほかの選択肢はなぜ違うのか

出典：平成23年度 秋期 基本情報技術者試験 午前 問5（改変：原典の図表をテキストに書き起こした）

この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）