ArrayQueue
add(x) … 末尾にxを追加する
remove() … 先頭の要素を返し、削除する
さっきのArrayStackあたりの技術を応用してキューを作りたい。けどそれだと先頭に追加するときに後ろ全てをずらさないといけない。非常に時間がかかる。 もし配列長が無限にあれば、
abcdefg_________…
_bcdefg_________…
__cdefg_________…
__cdefgh________…
__cdefghi________…
___defghi________…
みたいに先頭jをずらしながら処理することで、毎回のコピーが防げる。無限長…せや！配列をmodで管理すればいいんや！というデータ構造。
具体的には
_______abc_
_______abcd
e______abcd
ef_____abcd
ef______bcd
ef______bcd (a.length=10)でa[4]を呼ぶとfが返ってくる。具体的には、開始位置 j=7 で、4番目…なのでa[(j+i)%a.length]、つまりa[(7+4)%10]、計算するとa[1]が呼ばれることになって、fが返ってくる。
resizeするときは、配列aの j%a.length, (j+1)%a.length, (j+2)%a.length…番目を配列bの0,1,2…番目に対応させてコピーすれば良い。