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

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, 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…

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

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.