Trong bài hướng dẫn này, bạn sẽ được tìm hiểu về cấu trúc dữ liệu Queue (hàng đợi) và cách triển khai Queue trong JavaScript bằng cách sử dụng các phương thức của Mảng.
Queue là gì?
Queue (hàng đợi) là một danh sách các phần tử có thứ tự, được xếp hàng.
Trong đó:
-
Một phần tử được chèn vào queue sẽ chèn vào cuối hàng đợi
-
Và được xóa khỏi queue sẽ xóa từ đầu hàng đợi.
Không giống như một Stack, hoạt động dựa trên nguyên tắc nhập sau, xuất trước (LIFO), một Queue hoạt động dựa trên nguyên tắc nhập trước, xuất trước (FIFO - First In, Firt Out).
Hàng đợi có hai hoạt động chính liên quan đến việc chèn một phần tử mới và loại bỏ một phần tử hiện có.
-
Thao tác chèn được gọi là enqueue
-
Và thao tác xóa được gọi là dequeue.
Thao tác euqueue sẽ chèn một phần tử vào cuối hàng đợi, trong khi thao tác dequeue loại bỏ một phần tử ở phía trước hàng đợi.
Hình sau minh họa một hàng đợi:
Một hoạt động quan trọng khác của Queue là lấy phần tử ở phía trước gọi là peek. Khác với hoạt động dequeue, hoạt động peek chỉ trả về phần tử ở phía trước mà không sửa đổi Queue.
Tên Queue xuất phát từ sự tương tự với cách xếp hàng (hàng đợi) của khách hàng. Khách hàng đến trước sẽ được phục vụ trước, khách đến sau xếp hàng cuối sẽ được phục vụ sau.
Triển khai Queue sử dụng mảng 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.
Sau đây là hàm tạo của Queue:
// Hàm tạo Queue
function Queue() {
this.elements = [];
}
Hàm tạo Queue() sử dụng một mảng để lưu trữ các phần tử của nó.
Tiếp đến, chúng ta tạo các phương thức (hành động) của queue bằng các phương thức mảng trong JS.
Đầu tiên, Phương thức enqueue() thêm một phần tử vào cuối hàng đợi.
Trong đó enqueue(), chúng ta sử dụng phương thức push() của đối tượng mảng để chèn phần tử mới vào cuối hàng đợi:
// Enqueue: Thêm phần tử vào cuối hàng đợi
Queue.prototype.enqueue = function(e) {
this.elements.push(e);
};
Thứ hai, Phương thức dequeue() loại bỏ một phần tử từ phía trước hàng đợi.
Trong phương thức dequeue(), chúng ta sử dụng phương thức shift() của mảng để loại bỏ một phần tử ở phía trước hàng đợi.
// Dequeue: Loại bỏ phần tử ở đầu hàng đợi
Queue.prototype.dequeue = function() {
return this.elements.shift();
};
Thứ ba, Phương thức isEmpty() kiểm tra xem hàng đợi có trống không bằng cách kiểm tra xem thuộc tính độ dài của mảng có bằng 0 hay không.
// Kiểm tra xem hàng đợi có đang trống
Queue.prototype.isEmpty = function() {
return this.elements.length == 0;
};
Thứ tư, Phương thức peek() truy cập phần tử ở phía trước hàng đợi mà không sửa đổi nó.
// Peek: Lấy phần tử đầu của hàng đợi
// mà không thay đổi hàng đợi
Queue.prototype.peek = function() {
// Nếu hàng đợi không trống => Trả về phần tử đầu tiên
// ngược lại, trả về undefined
return !this.isEmpty() ? this.elements[0] : undefined;
};
Thứ năm, Phương thức length() trả về độ dài của hàng đợi.
// Tính độ dài của queue
Queue.prototype.length = function() {
return this.elements.length;
}
Bây giờ, sau khi đã tạo được Queue và các phương thức của nó, chúng ta có thể tạo một hàng đợi mới từ hàm tạo Queue(), bạn sử dụng từ khóa new như sau:
// Tạo một hàng đợi mới
let q = new Queue();
Sử dụng vòng lặp for để sắp xếp các số từ 1 đến 7 vào hàng đợi:
for (let i = 1; i <= 7; i++) {
// Thêm phần tử vào hàng đợi
q.enqueue(i);
}
Để lấy phần tử đầu tiên (không thay đổi queue) chúng ta sử dụng phương thức peek() đã tạo ở trên.
// Lấy phần tử đầu tiên với peek
// không thay đổi queue
console.log(q.peek()); // 1
Để tính độ dài hiện tại của hàng đợi, bạn sử dụng phương thức length() như trong ví dụ sau.
// Tính độ dài của queue
console.log(q.length()); // 7
Để xóa phần tử ở phía trước hàng đợi, bạn sử dụng phương thức dequeue() như sau:
// Xóa lần lượt tất cả phần tử của queue
while (!q.isEmpty()) {
console.log(q.dequeue());
}
Kết quả:
1
2
3
4
5
6
7
Bây giờ, sau khi đã loại bỏ hết phần tử trong hàng đợi q, ta thử kiểm tra lại xem q đã trống hay chưa.
// Kiểm tra xem hàng đợi có trống hay không
console.log(q.isEmpty());
Kết quả ta được:
true
Tổng kết Queue trong JavaScript
Bây giờ, bạn đã hiểu rõ về cấu trúc dữ liệu Queue và biết cách sử dụng phương thức push() và shift() của mảng để triển khai Queue trong JavaScript.
Chúc bạn học tốt.
---
HỌC VIỆN ĐÀO TẠO CNTT NIIT - ICT HÀ NỘI
Học Lập trình chất lượng cao (Since 2002). Học thực tế + Tuyển dụng ngay!
Đc: Tầng 3, 25T2, N05, Nguyễn Thị Thập, Cầu Giấy, Hà Nội
SĐT: 02435574074 - 0968051561
Email: hello@niithanoi.edu.vn
Fanpage: https://facebook.com/NIIT.ICT/
#niit #niithanoi niiticthanoi #hoclaptrinh #khoahoclaptrinh #hoclaptrinhjava #hoclaptrinhphp #python #php #java