循環佇列是一種線性資料結構,它的操作是基於FIFO(先進先出)原則進行的,並且最後一個位置連接回第一個位置,形成一個循環。它也被稱為“環形緩衝區”。
循環隊列的一個好處是我們可以利用隊列前面的空間。在普通隊列中,一旦隊列變滿,即使隊列前面有空間,我們也無法插入下一個元素。但是使用循環隊列,我們可以使用空間來儲存新的值。
我們需要在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中文網其他相關文章!