Bài 4.1. Giới thiệu về hàng đợi

Nội dung bài học

1. Định nghĩa và đặc điểm
2. Ứng dụng của queue
3. Các hành động đặc trưng

Định nghĩa và đặc điểm

• Queue là một cấu trúc dữ liệu thường triển khai theo quy tắc FIFO-first in first out: vào trước ra trước.
• Queue luôn mở ở hai đầu, trong đó một đầu luôn dùng để chèn dữ liệu vào và một đầu còn lại luôn dùng để lấy dữ liệu ra.
• Quy tắc quản lý dữ liệu trong queue là phần tử nào được đưa vào trước sẽ được lấy ra trước.
• Queue có thể được triển khai bằng cách sử dụng mảng, ArrayList, danh sách liên kết,…
• Ví dụ về queue: dòng phương tiện nối đuôi nhau trên đường 1 làn xe; dòng người nối đuôi nhau làm thủ tục checkin ở sân bay…

Ứng dụng

• Queue được sử dụng trong các ứng dụng cần quản lý một nhóm các đối tượng mà phần tử nào tới trước sẽ được xử lý trước.
• Sử dụng để phục vụ yêu cầu đối với các tài nguyên dùng chung: máy in, CPU, bộ nhớ.
• Sử dụng khi dữ liệu được truyền một cách đồng bộ giữa hai tiến trình.
• Trung tâm hỗ trợ khách hàng, tổng đài sử dụng queue để giữ các cuộc gọi đến theo thứ tự cho tới khi cuộc gọi đó được phục vụ.
• Trong các hệ thống xử lý ngắt thời gian thực, các ngắt được xử lý theo cùng thứ tự mà nó xuất hiện.
• Sử dụng trong hàng đợi mail, chuyển mạch router, switches.

Các hành động

• enqueue(data) – thêm phần tử mới vào cuối queue.
• dequeue() – xóa phần tử ở đầu queue.
• peek() – lấy phần tử đầu queue nhưng không xóa.
• isFull() – kiểm tra xem queue đã đầy chưa. Áp dụng với queue triển khai bằng mảng.
• isEmpty() – kiểm tra xem queue có rỗng không.
• size() – trả về số phần tử hiện có của queue.

Trong các bài học kế tiếp ta sẽ lần lượt tìm hiểu các triển khai hàng đợi sử dụng ArrayList, danh sách liên kết, hàng đợi ưu tiên, hàng đợi vòng.