満杯を個数で判断するキュー

容量3、添字0〜2の循環キュー。h=t=count=0から始める。 put(x): if count=3: return false Q[t] ← x t ← (t+1) mod 3 count ← count+1 return true get(): if count=0: return EMPTY x ← Q[h] h ← (h+1) mod 3 count ← count−1 return x put(A),put(B),get(),put(C),put(D),put(E),get()を順に実行。失敗したputの値と2回目のgetの戻り値はどれか。

答え・解き方を読む

E、B

図で見る

末尾の次を先頭へ戻す循環キュー

図を拡大して見る ↗

この図は容量3・添字0〜2の問題だけに対応します。hとtが同じでも空と満杯があり得るため、個数countを持つ方式ではcountも一緒に追います。

図は問題の関係を整理する模式図です。記号には各問題の数値を当てはめます。寸法・面積・時間の縮尺や、実施工の全条件は表していません。

考える順序

1. 1Aを取り出した後にBだけが残る
2. 2C,Dを追加してB,C,Dの3個で満杯、Eは拒否
3. 3最後のgetは最も古いBを返す

選択肢ごとの理由

• 比較 · 失敗なし、B

  満杯のためEを追加できません。

• 正解 · E、B

  Aを取り出した後にBだけが残る。C,Dを追加してB,C,Dの3個で満杯、Eは拒否。最後のgetは最も古いBを返す。

• 比較 · D、B

  Aを取り出して空きがあるためDは入ります。

• 比較 · E、C

  Cより先にBが登録されています。