The queue data structure

Trong bài viết này, chúng ta sẽ tìm hiểu về queue data structure (cấu trúc dữ liệu hàng đợi) và triển khai queue trong JavaScript.

Giới thiệu queue data structure

Queue là một kiểu cấu trúc dữ liệu tuyến tính, tuân theo quy luật FIFO (First In First Out). Hay “first-come, first-served”, nghĩa là: “ai đến trước thì được phục vụ trước”. Không giống như stack dựa trên nguyên tắc LIFO (Last In First Out).

Tưởng tượng Queue giống như việc xếp hàng chờ mua trà sữa, người vào trước được ưu tiên phục vụ trước, ai đến sau phải chịu khó xếp hàng chờ đến lượt mình.

Ứng dụng Queue trong lập trình

• Sử dụng trong thuật toán tìm kiếm theo chiều rộng BFS.
• Event Queue trong JavaScript.
• Hệ thống xử lý các lệnh trong máy tính (ứng dụng trong hệ điều hành, trình biên dịch), hàng đợi các tiến trình chờ được xử lý.
• Bộ nhớ đệm khi xử lý đa luồng, đa tiến trình (download, xử lý audio, xử lý video,…)

Một Queue có hai thao tác chính:

• enqueue() : Chèn một phần tử vào cuối Queue
• dequeue() : Loại bỏ một phần tử ở đầu Queue.

Hình dưới đây minh họa một Queue:

Triển khai Queue trong JavaScript bằng Array

Một số phương thức triển khai trong class Queue:

• enqueue() : Thêm một phần tử vào cuối của Queue khi nó chưa đầy.
• dequeue() : Lấy ra một phần tử ở đầu của Queue khi nó không rỗng.
• peek()        : Trả về giá trị của phần tử ở đầu của Queue khi nó không rỗng.
• isEmpty() : Kiểm tra xem Queue có rỗng hay không.
• isFull()   : Kiểm tra xem Queue đã đầy hay chưa.

Code:

class Queue {
  constructor(capacity) {
    this.queue = []
    this.capacity = capacity;
  }
  
  enqueue(element) {
    if (this.isFull()) return false;
    this.queue.push(element)
  }
  
  dequeue() {
    if (this.isEmpty()) return true; //Queue is empty
    return this.queue.shift()
  }
  
  peek() {
    if (this.isEmpty()) return true; //Queue is empty
    return this.queue[0]
  }
  
  isEmpty() {
    return !this.queue.length
  }

  isFull() {
    return this.size === this.capacity;
  }
}

Phương thức Enqueue để thêm mới phần tử vào Queue:

• Bước 1: kiểm tra xem queue đã đầy chưa.
• Bước 2: nếu đầy, trả về false và thoát
• Bước 3: ngược lại, thêm phần tử mới vào cuối Queue

Khởi tạo một Queue mới với danh sách 5 phần tử.

var q = new Queue(5);

for (var i = 1; i <= 5; i++) {
    q.enqueue(i);
}
// [1 ,2 ,3 ,4 ,5]

Lấy phần tử đầu Queue bằng peek().

// get the current item at the front of the queue
console.log(q.peek()); // 1

Lấy kích thước hiện tại của Queue.

// get the current length of queue
console.log(q.capacity); //5

Phương thức Dequeue để loại bỏ một phần tử của Queue:

• Bước 1: kiểm tra xem queue có rỗng hay không.
• Bước 2: nếu rỗng, trả về true và thoát.
• Bước 3: ngược lại, loại bỏ phần tử ở đầu Queue.

// dequeue a element
    console.log(q.dequeue());
}
 
// [2 ,3 ,4 ,5]

Tham khảo:

https://completejavascript.com/trien-khai-queue-trong-javascript/
https://www.javascripttutorial.net/javascript-queue/
https://medium.com/javascript-in-plain-english/javascript-what-are-stack-and-queue-79df7af5a566