配列を「輪」に見立てるリングバッファ。Queue の先頭削除からシフトを消す

プログラムで「先に入れたものから順に取り出す」キュー（Queue）を作りたい場面は、よくあります。ログのバッファ、イベントの待ち行列、センサー値の直近 N 件——どれも Queue です。

JavaScript なら、配列ひとつで素直に書けます。push で末尾に足し、shift で先頭を取り出す。

class NaiveQueue {
  constructor(cap){ this.cap = cap; this.data = []; }
  enqueue(x){ if(this.data.length >= this.cap) return false; this.data.push(x); return true; }
  dequeue(){ return this.data.length ? this.data.shift() : undefined; }
}

短くて分かりやすい。でもこのやり方には、要素数が増えると効いてくる弱点があります。

弱点：先頭を取り出すたびに、全部が前へずれる

配列の先頭（index 0）を取り出すと、残りの要素はすべて1つ前へ詰め直されます。2番目が先頭へ、3番目が2番目へ……と、全員が席を1つずつ移動する。これが shift の正体です。

要素が4個なら4個ぶん、1万個なら1万個ぶん動かす。つまり dequeue 1回のコストが、入っている要素数に比例して重くなります（$O(n)$）。enqueue は末尾に足すだけなので軽いのに、取り出す側が足を引っ張るわけです。

中身は1バイトも変わらないのに、「席をずらす」ためだけに大量のコピーが走る。動かしたいのは「どこが先頭か」という目印だけのはずです。

リングバッファ：配列を「輪」に見立てる

そこで、固定長の配列を用意して、それを輪のように使います。これがリングバッファです。

考え方はシンプルで、配列を伸び縮みさせる代わりに、2つの数だけを動かします。

• head … いま先頭がある位置（次に取り出す場所）
• count … いま入っている要素数

enqueue は、空いている次の位置 (head + count) % cap に書いて count を1増やすだけ。dequeue は、head の中身を読んで head を1つ先に進め、count を1減らすだけ。要素は1つも動きません。

右端まで埋まったら、% cap（剰余）のおかげで自動的に 0 番へ戻ります。輪をぐるぐる回りながら、書く位置と読む位置の目印だけがずれていく。配列そのものは最初から最後まで同じ大きさのままです。

class RingQueue {
  constructor(cap){
    this.cap = cap;
    this.data = new Array(cap);
    this.head = 0;
    this.count = 0;
  }
  enqueue(x){
    if(this.count >= this.cap) return false;   // 満杯
    this.data[(this.head + this.count) % this.cap] = x;
    this.count++;
    return true;
  }
  dequeue(){
    if(this.count === 0) return undefined;      // 空
    const x = this.data[this.head];
    this.data[this.head] = undefined;           // 取り出した参照を残さない（GCのため）
    this.head = (this.head + 1) % this.cap;     // 先頭の目印を進めるだけ
    this.count--;
    return x;
  }
}

shift のような全体の詰め直しがどこにもありません。dequeue がやるのは足し算と剰余だけなので、入っている要素数に関係なく一定の手数（$O(1)$）で終わります。

触ってみる

文章だと「シフトが消える」感じが掴みにくいので、実際に動かせるようにしました。下のビジュアライザを触ってみてください。

• enqueue ＋ / dequeue − を押して、配列がどう変わるか見てください。
• 上の方式を「リングバッファ／素朴方式」で切り替えると、同じ操作での動きの差がそのまま見えます。素朴方式は dequeue のたびに残り全部がスッと前へスライドしますが、リングバッファは head の目印が1つ進むだけです。
• 「累計シフト移動量」のカウンタに注目。リングはずっと 0 のまま、素朴方式はみるみる増えていきます。これが速度差の正体です。
• 「自動デモ」で、満杯近くを保ちながら enqueue/dequeue を繰り返す様子を流せます。

うまく表示されないときは、ビジュアライザを別タブで開く 。

どれだけ速いのか：実測してみる

両方式で、容量（cap）を変えながら「満杯近くを保って dequeue＋enqueue を 10 万回」回し、JavaScript（Node.js）で実測しました。次の数値は手元のマシンで測った一例で、環境や実行ごとに前後しますが、傾向は変わりません。

いちばん左の「自前シフト」は、dequeue を「残り全要素を自分で1つ前へ詰める」素朴な実装で測ったものです。容量が10倍になるたびに時間も約10倍——きれいに $O(n)$ で悪化しています。一方リングバッファは、容量をどれだけ大きくしても 0.4 ミリ秒前後で一定。要素を動かさないので当然です。

Array.shift が中間にいる理由：JavaScript エンジン（V8）は Array.shift を内部で最適化していて、純粋な $O(n)$ ほどは悪化しません。それでも容量とともにじわじわ遅くなりますし、最適化の有無はエンジン任せです。リングバッファは、エンジンの最適化に頼らず自分のコードで $O(1)$ を保証できるのが強みです。

要素数が少ないうちはどの方式でも誤差ですが、Queue が大きくなるほど素朴方式は不利になり、リングバッファは涼しい顔のまま、という結果になりました。

function benchManual(cap, T){           // 自前シフト：残り全要素を前へ詰める
  const a = new Array(cap); for(let i=0;i<cap;i++) a[i]=i;
  let count=cap, acc=0; const t0=process.hrtime.bigint();
  for(let i=0;i<T;i++){
    acc += a[0];
    for(let j=0;j<count-1;j++) a[j]=a[j+1];   // ← O(n) のシフト
    count--; a[count]=i; count++;
  }
  return Number(process.hrtime.bigint()-t0)/1e6;
}
function benchShift(cap, T){            // Array.shift（V8 が内部最適化）
  const q=[]; for(let i=0;i<cap;i++) q.push(i);
  let acc=0; const t0=process.hrtime.bigint();
  for(let i=0;i<T;i++){ acc+=q.shift(); q.push(i); }
  return Number(process.hrtime.bigint()-t0)/1e6;
}
function benchRing(cap, T){             // リングバッファ：インデックス演算のみ
  const d=new Array(cap).fill(0); for(let i=0;i<cap;i++) d[i]=i;
  let head=0, count=cap, acc=0; const t0=process.hrtime.bigint();
  for(let i=0;i<T;i++){
    acc+=d[head]; head=(head+1)%cap; count--;
    d[(head+count)%cap]=i; count++;
  }
  return Number(process.hrtime.bigint()-t0)/1e6;
}

const T=100000;
for(const cap of [10,100,1000,10000]){
  benchManual(cap,5000); benchShift(cap,5000); benchRing(cap,5000); // ウォームアップ
  console.log(cap, benchManual(cap,T).toFixed(1), benchShift(cap,T).toFixed(1), benchRing(cap,T).toFixed(2));
}

玉突き・配列回転とのつながり

「配列を伸び縮みさせず、剰余で輪をぐるぐる回す」という発想は、このブログの他の記事とも地続きです。

• 配列をその場で回す（リバーサル法／ジャグリング法） では、(i + k) % n で要素を $k$ 個ずらす「回転」を、別配列なしで実現しました。リングバッファの (head + count) % cap と、同じ剰余の使い方です。リングバッファは「回転する読み書き位置」を持った配列、とも言えます。
• 画像をリネームだけで並び替える玉突き方式 では、実体を動かさず目印（穴やインデックス）だけを動かすことで手数を最小にしました。リングバッファの「要素は動かさず head だけ動かす」も、まったく同じ精神です。

「データそのものではなく、データを指す目印を動かす」。地味ですが、効くアイデアです。

まとめ

• 配列をそのまま Queue にすると、dequeue（先頭の取り出し）で残り全部を前へ詰めるシフトが起き、$O(n)$ になる。
• リングバッファは固定長の配列を輪に見立て、head と count だけで管理する。enqueue は (head+count)%cap に書き、dequeue は head を進めるだけ。要素を1つも動かさないので $O(1)$。
• 実測でも、容量が大きいほど素朴方式は遅くなり、リングバッファは一定だった。
• 本質は「実体ではなく目印を動かす」こと。配列回転や玉突き方式と同じ発想の仲間です。

上のビジュアライザで、素朴方式の「全部スライド」とリングバッファの「目印だけ移動」を、ぜひ見比べてみてください。