1. Queue là gì?
Queue (hàng đợi) là một cấu trúc dữ liệu trong lập trình, hoạt động theo nguyên tắc FIFO (First In, First Out), nghĩa là phần tử nào vào hàng đợi trước thì sẽ được xử lý trước. Điều này giống như một hàng người xếp hàng chờ đợi – người vào trước sẽ được phục vụ trước.
Queue là một trong những cấu trúc dữ liệu cơ bản, được ứng dụng trong nhiều thuật toán và hệ thống phần mềm. Cấu trúc này bao gồm hai đầu: đầu trước (front) và đầu sau (rear). Phần tử được thêm vào ở cuối hàng (rear) và được loại bỏ từ đầu hàng (front).
2. Các hoạt động cơ bản trong Queue
Queue có các hoạt động cơ bản sau:
Enqueue (thêm phần tử vào hàng đợi):
Thao tác này thêm một phần tử vào cuối hàng đợi. Nếu hàng đợi đầy, thao tác này sẽ không thể thực hiện được.
Dequeue (loại bỏ phần tử khỏi hàng đợi):
Thao tác này loại bỏ phần tử ở đầu hàng đợi và trả về phần tử đó. Nếu hàng đợi rỗng, thao tác này sẽ không thể thực hiện được.
Peek (xem phần tử ở đầu hàng đợi):
Trả về phần tử ở đầu hàng đợi mà không loại bỏ nó. Nếu hàng đợi rỗng, thao tác này cũng không thể thực hiện được.
IsEmpty (kiểm tra hàng đợi có rỗng không):
Kiểm tra xem hàng đợi có phần tử nào không. Nếu không, trả về “true”; ngược lại, trả về “false”.
IsFull (kiểm tra hàng đợi có đầy không):
Kiểm tra xem hàng đợi có đạt giới hạn số phần tử tối đa không (áp dụng cho các hàng đợi có kích thước cố định). Nếu đầy, trả về “true”; ngược lại, trả về “false”.
3. Ứng dụng của Queue
Queue được ứng dụng trong nhiều lĩnh vực và thuật toán nhờ tính chất FIFO:
- Quản lý hàng đợi trong hệ thống điều phối và xử lý yêu cầu: Ví dụ: Các hàng đợi trong hệ điều hành để quản lý tiến trình (process scheduling), giúp CPU xử lý lần lượt từng tiến trình.
- Lập lịch công việc: Trong các hệ thống máy in, các tài liệu được đưa vào hàng đợi in theo thứ tự người dùng gửi, và tài liệu nào vào trước sẽ được in trước.
- Xử lý luồng dữ liệu trong mạng máy tính: Các gói dữ liệu khi truyền qua mạng thường được lưu vào hàng đợi trước khi được gửi hoặc nhận. Điều này đảm bảo rằng các gói được xử lý lần lượt.
- Hệ thống hỗ trợ khách hàng (Customer Service): Queue hỗ trợ quản lý các yêu cầu từ khách hàng, giúp xếp thứ tự xử lý các yêu cầu theo nguyên tắc công bằng.
- Ứng dụng trong kiến trúc phần mềm xử lý luồng dữ liệu (stream processing): Queue được dùng để tạm lưu các dữ liệu đầu vào, chờ đến khi chúng được xử lý, như trong Apache Kafka.
- Hệ thống bán vé: chẳng hạn như bán vé sự kiện, Queue được sử dụng để quản lý các yêu cầu mua vé của khách hàng. Khi có nhiều người mua vé cùng một lúc, các yêu cầu sẽ được đưa vào hàng đợi, và khách hàng nào yêu cầu trước sẽ được xử lý trước. Điều này giúp tránh tình trạng quá tải và đảm bảo công bằng cho người mua, đặc biệt là khi số lượng vé có hạn. Queue còn giúp giảm thiểu rủi ro bị “double booking” (đặt vé trùng lặp) khi nhiều người cùng đặt một chỗ ngồi hoặc một loại vé cùng lúc.
Bài viết liên quan: Bất đồng bộ là gì ?


