プログラミングの基礎(擬似言語のトレース)
要素数4の文字列型の配列 q を環状に使うキューがある。head と tail の初期値は1で、enq(v) は q[tail] ← v の後に tail ← tail mod 4 + 1 を行い、deq() は q[head] の値を返した後に head ← head mod 4 + 1 を行う。次のプログラムを実行したとき、「E」が格納される q の要素はどれか。
enq("A")
enq("B")
enq("C")
deq()
deq()
enq("D")
enq("E")- Aq[1]
- Bq[3]
- Cq[5]
答えと解説を見る
正解：A. q[1]
mod は + より先に計算するので、tail ← tail mod 4 + 1 は tail を 1 → 2 → 3 → 4 → 1 と循環させます。A、B、C は q[1]〜q[3] に入り、tail = 4 です。2回の deq() で A と B が取り出され、head = 3 になります。D は q[4] に入って tail が 4 mod 4 + 1 = 1 に戻り、E は空いた q[1] に入ります。要素を前へ詰めずに、取り出して空いた場所を再利用するのが環状のキュー(リングバッファ)です。
- A. 正しい。tail は4の次に1へ戻り、E は取り出し済みで空いた q[1] に入ります。
- B. 取り出すたびに残りの要素を前へ詰めると考えた場合の位置です。この方式では詰めません。
- C. tail を4の次に5へ進めた場合の位置で、配列の範囲を超えます。tail mod 4 + 1 で1に戻ります。