Triển khai bộ đệm vòng hàng đợi tròn trong JavaScript

Hàng đợi Hình tròn

Hàng đợi hình tròn là một cấu trúc dữ liệu tuyến tính trong đó các phép toán được thực hiện dựa trên nguyên tắc FIFO (Nhập trước Xuất trước) và vị trí cuối cùng được kết nối trở lại vị trí đầu tiên để tạo thành một vòng tròn. Nó còn được gọi là "Ring Buffer".

Một trong những lợi ích của hàng đợi tròn là chúng ta có thể tận dụng các khoảng trống phía trước hàng đợi. Trong một hàng đợi bình thường, một khi hàng đợi đã đầy, chúng ta không thể chèn phần tử tiếp theo ngay cả khi có một khoảng trống phía trước hàng đợi. Nhưng bằng cách sử dụng hàng đợi tròn, chúng ta có thể sử dụng không gian để lưu trữ các giá trị mới.

Vấn đề

Chúng tôi được yêu cầu thiết kế triển khai hàng đợi vòng tròn trong JavaScript có thể hỗ trợ các hoạt động sau -

• MyCircularQueue (k) - Khối mã lệnh, đặt kích thước của hàng đợi là k.

• Front () - Lấy vật phẩm phía trước từ hàng đợi. Nếu hàng đợi trống, trả về -1.

• Rear () - Nhận mục cuối cùng từ hàng đợi. Nếu hàng đợi trống, trả về -1.

• enQueue (value) - Chèn một phần tử vào hàng đợi tròn. Trả về true nếu thao tác thành công.

• deQueue () - Xóa một phần tử khỏi hàng đợi tròn. Trả về true nếu thao tác thành công.

• isEmpty () - Kiểm tra xem hàng đợi tròn có trống hay không.

• isFull () - Kiểm tra xem hàng đợi tròn đã đầy hay chưa.

Ví dụ

Sau đây là mã -

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

Đầu ra

true
true
false
2
true
true
true
3