การใช้บัฟเฟอร์วงแหวนคิวแบบวงกลมใน JavaScript

คิวแบบวงกลม

คิวแบบวงกลมเป็นโครงสร้างข้อมูลเชิงเส้นซึ่งดำเนินการตามหลักการ FIFO (เข้าก่อนออกก่อน) และตำแหน่งสุดท้ายเชื่อมต่อกลับไปยังตำแหน่งแรกเพื่อสร้างวงกลม เรียกอีกอย่างว่า "Ring Buffer"

ข้อดีอย่างหนึ่งของคิวแบบวงกลมคือเราสามารถใช้ประโยชน์จากช่องว่างหน้าคิวได้ ในคิวปกติ เมื่อคิวเต็มแล้ว เราไม่สามารถแทรกองค์ประกอบถัดไปได้ แม้ว่าจะมีช่องว่างด้านหน้าคิวก็ตาม แต่เมื่อใช้คิวแบบวงกลม เราสามารถใช้ช่องว่างเพื่อเก็บค่าใหม่ได้

ปัญหา

เราจำเป็นต้องออกแบบการใช้งานคิวแบบวงกลมใน JavaScript ที่สามารถรองรับการทำงานต่อไปนี้ -

• MyCircularQueue(k) − Constructor กำหนดขนาดของคิวเป็น k

• Front() - รับรายการด้านหน้าจากคิว หากคิวว่าง ให้คืนค่า -1

• Rear() - รับรายการสุดท้ายจากคิว หากคิวว่าง ให้คืนค่า -1

• enQueue(value) - แทรกองค์ประกอบลงในคิวแบบวงกลม คืนค่า จริง หากการดำเนินการสำเร็จ

• deQueue() - ลบองค์ประกอบออกจากคิวแบบวงกลม คืนค่า จริง หากการดำเนินการสำเร็จ

• 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