在JavaScript中實作循環佇列環形緩衝區

循環佇列

循環佇列是一種線性資料結構，它的操作是基於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中文網其他相關文章！