JavaScriptで循環キュー（リングバッファ）を実装する方法

循環キュー（Circular Queue）とは

循環キューは、FIFO（First In First Out：先入れ先出し）の原則に基づいて操作が行われる線形データ構造の一つです。末尾の位置が先頭の位置につながり、全体が輪のように見えることから「リングバッファ（Ring Buffer）」とも呼ばれます。

循環キューの大きなメリットは、キューの先頭側に生じた空きスペースを再利用できる点にあります。通常のキューでは、いったん満杯になると先頭側に空きがあっても新しい要素を挿入できません。しかし循環キューであれば、その空きスペースを活用して引き続き値を格納することが可能です。

実装要件

ここでは、JavaScriptで次の操作をサポートする循環キューを実装していきます。

• MyCircularQueue(k) − コンストラクタ。キューのサイズを k に設定します。

• Front() − キューの先頭にある要素を取得します。キューが空の場合は -1 を返します。

• Rear() − キューの末尾にある要素を取得します。キューが空の場合は -1 を返します。

• enQueue(value) − 循環キューに要素を挿入します。挿入に成功した場合は true を返します。

• deQueue() − 循環キューから要素を削除します。削除に成功した場合は true を返します。

• isEmpty() − 循環キューが空かどうかを判定します。

• isFull() − 循環キューが満杯かどうかを判定します。

サンプルコード

以下が実際の実装コードです。

const CircularQueue = function(k) {
    this.size = k
    this.queue = []
    this.start1 = 0
    this.end1 = 0
    this.start2 = 0
    this.end2 = 0
}
CircularQueue.prototype.enQueue = function(value) {
    if(this.isFull()) {
       return false
    }
    if(this.end2 <= this.size - 1) {
       this.queue[this.end2++] = value
    } else {
       this.queue[this.end1++] = value
    }
    return true
}
CircularQueue.prototype.deQueue = function() {
    if(this.isEmpty()) {
       return false
    }
    if(this.queue[this.start2] !== undefined) {
       this.queue[this.start2++] = undefined
    } else {
       this.queue[this.start1++] = undefined
    }
    return true
}
CircularQueue.prototype.Front = function() {
    if(this.isEmpty()) {
       return -1
    }
    return this.queue[this.start2] === undefined ? this.queue[this.start1] :     this.queue[this.start2]
}
CircularQueue.prototype.Rear = function() {
    if(this.isEmpty()) {
       return -1
    }
    return this.queue[this.end1 - 1] === undefined ? this.queue[this.end2 - 1] :     this.queue[this.end1 - 1]
}
CircularQueue.prototype.isEmpty = function() {
    if(this.end2 - this.start2 + this.end1 - this.start1 <= 0) {
       return true
    }
    return false
}
CircularQueue.prototype.isFull = function() {
    if(this.end2 - this.start2 + this.end1 - this.start1 >= this.size) {
       return true
    }
    return false
}
const queue = new CircularQueue(2);
console.log(queue.enQueue(1));
console.log(queue.enQueue(2));
console.log(queue.enQueue(3));
console.log(queue.Rear());
console.log(queue.isFull());
console.log(queue.deQueue());
console.log(queue.enQueue(3));
console.log(queue.Rear());

実装のポイント

この実装では、内部の配列を2組のインデックスで管理しています。start2 / end2 は最初の一周目の読み書き位置を追跡し、start1 / end1 は折り返した後の位置を追跡します。

enQueue の実行時には、まだ未使用の領域（end2 側）があればそこへ書き込み、使い切った後は先頭側へ折り返して（end1 側へ）書き込みます。これにより、deQueue で削除されて undefined になったスロットを再利用でき、配列全体を効率的に使い回せるのです。

また、isEmpty と isFull は「end2 − start2 + end1 − start1」という式で現在の要素数を算出し、それが 0 以下か、サイズ k 以上かを比較することで判定しています。

実行結果

true
true
false
2
true
true
true
3

このサンプルでは、サイズ2の循環キューを生成して一連の操作を行っています。3つ目の enQueue(3) はキューが満杯のため false を返しますが、その後 deQueue() で先頭の要素を取り除くと、同じ enQueue(3) が true を返して成功します。これは、先頭側に空いたスロットへ折り返して書き込めたことを示しており、循環キューの特徴的な動作が確認できます。