Cấu trúc dữ liệu queue

Queue Data Structure (Cấu trúc dữ liệu hàng đợi)

Trong hướng dẫn này, bạn sẽ học hàng đợi là gì. Vì vậy, bạn sẽ tìm thấy việc triển khai hàng đợi trong Javascript.

Hàng đợi (Queue) là một cấu trúc dữ liệu có ích trong lập trình. Nó tương tự như việc xếp hàng mua vé bên ngoài sảnh rạp chiếu phim, nơi người đầu tiên vào hàng là người đầu tiên nhận được vé.

Hàng đợi tuân theo quy tắc First In First Out (FIFO) - mục nào vào trước thì sẽ xuất hiện trước.

Trong ảnh bên trên, vì 1 được giữ trong hàng đợi trước 2 nên nó cũng là phần tử đầu tiên bị xóa khỏi hàng đợi. Nó tuân theo quy tắc FIFO.

Trong thuật ngữ lập trình, việc đặt các mục trong hàng đợi là được gọi là enqueue và loại bỏ các mục từ hàng đợi được gọi là dequeue.

Chúng tôi có thể triển khai hàng đợi trong bất kỳ ngôn ngữ lập trình nào như: C, C#, JS, TS…, nhưng đặc điểm kỹ thuật là như nhau.

Hoạt động cơ bản của Hàng đợi

Hàng đợi là 1 đối tượng (object) (một cấu trúc dữ liệu trừu tượng - ADT) điều đó cho phép tuân theo hoạt động:

• Enqueue: Thêm một phần tử cuối cùng trong hàng đợi.
• Dequeue: Xóa một phần tử khỏi hàng đợi
• IsEmpty: Kiểm tra nếu hàng đợi trống
• IsFull: kiểm tra nếu hàng đợi đầy
• Peek: Nhận giá trị phía trước của hàng đợi mà không cần loại bỏ nó

Làm việc với Queue

Hàng đợi hoạt động như sau:

• Với 2 điểm: FRONT(đằng trước) và REAR(đằng sau)
• FRONT theo dõi phần tử đầu tiên của hàng đợi
• REAR theo dõi phần tử cuối cùng của hàng đợi
• Khởi tạo, thiết lập giá trị của FRONT và REAR là -1

Hoạt động của Enqueue

• Kiểm tra nếu hàng đợi là đầy
• Cho phần tử đầu tiên, thiết lập giá trị của FRONT là 0
• Tăng chỉ số REAR = 1 đơn vị
• Thêm phần tử mới vào vị trí được trỏ tới bởi REAR

Hoạt động của Dequeue

• Kiểm tra nếu hàng đợi trống
• Trả về giá trị của vị trí FRONT
• Tăng chỉ số FRONT lên 1 đơn vị
• Cho phần tử cuối cùng, thiết lập lại giá trị của FRONT và REAR thành -1

Triển khai Queue trong Javascript

Trong JavaScript, để triển khai Queue bạn có thể sử dụng một mảng và sử dụng hai phương thức của kiểu Mảng:

• Thêm một phần tử vào cuối mảng bằng phương thức push(). Phương thức này tương đương với hoạt động enqueue.
• Xóa một phần tử khỏi mảng trước bằng phương thức shift(). Nó cũng giống như hoạt động dequeue.

Hãy triển khai cấu trúc dữ liệu hàng đợi JavaScript bằng cách sử dụng một mảng.

// Hàm tạo Queue
function Queue() {
    this.elements = [];
}

// Thêm 1 phần tử ở cuối hàng đợi
Queue.prototype.enqueue = function (el) {
    this.elements.push(el);
}

// Xóa một phần tử ở đầu hàng đợi
Queue.prototype.dequeue = function () {
    this.elements.shift();
}

// Kiểm tra hàng đợi có trống không
Queue.prototype.isEmpty = function () {
    return this.elements.length === 0
}

// Lấy phần tử đầu tiên của hàng đợi mà ko làm thay đổi hàng đợi
Queue.prototype.peek = function () {
    return !this.isEmpty() ? this.elements[0] : undefined;
}

// Tính độ dài hàng đợi
Queue.prototype.length = function () {
    return this.elements.length;
}

// Khởi tạo hàng đợi mới
let queue = new Queue();

// Thêm phần tử vào hàng đợi
for (let i = 0; i < 6; i++) {
    queue.enqueue(i);
}

// Xem độ dài của hàng đợi
console.log('Độ dài: ', queue.length);

// Kiểm tra là trống không
console.log('Check is empty: ', queue.isEmpty());

// Xoá phần tử đầu tiên trong hàng đợi
queue.dequeue();

// Lấy phần tử đầu tiên trong hàng đợi
console.log('First element: ', queue.peek());

// Xóa lần lượt tất cả các phần tử trong hàng đợi
while (!queue.isEmpty()) {
    console.log('Current queue: ', queue.dequeue());
}

Điểm hạn chế của hàng đợi

Như bạn có thể thấy như ảnh dưới, sau 1 bit của enqueue và dequeue, kích thước của queue sẽ giảm xuống.

Và chúng tôi chỉ có thể thêm các chỉ số 0 và 1 khi queue tái thiết lập (khi tất cả các phần tử đều được xóa (dequeue))

Phía sau REAR đạt đến chỉ số cuối cùng, nếu chúng tôi có thể lưu trữ mở rộng các phần tử trong khoảng trống (0 và 1), thì chúng tôi có thể sử dụng các khoảng trống đó. Điều này được thể hiện bởi hàng đợi được chỉnh sửa được gọi là circular quere.

Phân tích độ phức tạp

Độ phức tạp của việc thêm và xóa hàng đợi trong 1 array là 0(1). Nếu bạn sử dụng hàm shift(n) trong Javascript code thì độ phức tạp có thể là 0(n) phụ thuộc vào vị trí của item được loại bỏ.

Ứng dụng của hàng đợi

• Lịch trình của CPU, Disk
• Khi dữ liệu được truyền không đồng bộ giữa hai quá trình, hàng đợi được sử dụng để đồng bộ hóa. ex: Bộ đêm IO, pipes, file IO…
• Xử lý ngắt trong hệ thống thời gian thực
• Hệ thống điện thoại của Call center sử dụng queue để giữ những người đang thực hiện cuộc gọi theo thứ tự trước sau.