ホームページ > 記事 > ウェブフロントエンド > JavaScript で循環キュー リング バッファを実装する
循環キューは線形データ構造であり、その動作は FIFO (先入れ先出し) の原則に基づいており、最後に位置は最初の位置に接続されてループを形成します。 「リングバッファ」とも呼ばれます。
循環キューの利点の 1 つは、キューの前のスペースを利用できることです。通常のキューでは、キューがいっぱいになると、キューの前に空きがあっても次の要素を挿入できません。しかし、循環キューを使用すると、スペースを使用して新しい値を保存できます。
次の操作をサポートするには、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());
true true false 2 true true true 3
以上がJavaScript で循環キュー リング バッファを実装するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。