การนำคิววงกลม (Ring Buffer) ไปใช้ใน JavaScript

คิววงกลม (Circular Queue)

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

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

ปัญหา

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

• MyCircularQueue(k) - Constructor, กำหนดขนาดคิวเป็น 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