Triển khai hàng đợi vòng (circular queue/ring buffer) trong JavaScript

Hàng đợi vòng

Hàng đợi vòng là cấu trúc dữ liệu tuyến tính nơi các thao tác dựa trên nguyên tắc FIFO (First In First Out) và vị trí cuối được nối kembali vị trí đầu để tạo thành vòng tròn. Còn gọi là "Ring Buffer".

Lợi ích: có thể sử dụng khoảng trống phía trước hàng đợi. Trong hàng đợi bình thường, khi đầy không thể chèn thêm dù có chỗ trống phía trước. Với hàng đợi vòng, có thể dùng chỗ trống đó.

Vấn đề

Chúng ta cần thiết kế triển khai hàng đợi vòng trong JavaScript hỗ trợ các thao tác:

• MyCircularQueue(k) - Constructor, đặt kích thước hàng đợi là k.
• Front() - Lấy phần tử đầu. Nếu rỗng trả về -1.
• Rear() - Lấy phần tử cuối. Nếu rỗng trả về -1.
• enQueue(value) - Chèn phần tử. Trả về true nếu thành công.
• deQueue() - Xóa phần tử. Trả về true nếu thành công.
• isEmpty() - Kiểm tra hàng đợi rỗng.
• isFull() - Kiểm tra hàng đợi đầy.

Ví dụ

Dưới đây là mã thực hiện:

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());

Kết quả

true true false 2 true true true 3