Hàng đợi chặn (Blocking Queue)

1. Khái niệm hàng đợi

Hàng đợi là cấu trúc dữ liệu tuyến tính có đặc điểm duy nhất: phần tử được thêm vào đầu (rear) và lấy ra từ cuối (front), tuân theo nguyên tắc FIFO (First In First Out). Ví dụ điển hình là hàng người mua vé tàu: người mới tham gia luôn đứng cuối hàng, và người được phục vụ đầu tiên luôn là người đứng đầu hàng.

2. Định nghĩa hàng đợi chặn

Hàng đợi chặn là dạng đặc biệt của hàng đợi, trong đó các thao tác thêm/xóa phần tử sẽ bị chặn khi điều kiện không đủ. Cụ thể:

• Thêm phần tử: Nếu hàng đầy, luồng thực hiện sẽ bị chặn cho đến khi có vị trí trống.
• Lấy phần tử: Nếu hàng rỗng, luồng thực hiện sẽ bị chặn cho đến khi có dữ liệu.

3. Giao diện hàng đợi trong Java

Java chia tập hợp thành 2 nhóm chính: Collection và Map. Hàng đợi (Queue) thuộc nhóm Collection.

3.1 Giao diện Queue

• offer(E e): Thêm phần tử, trả về true nếu thành công.
• peek(): Trả về phần tử đầu hàng (không xóa) hoặc null nếu hàng rỗng.
• poll(): Trả về và xóa phần tử đầu hàng, hoặc null nếu hàng rỗng.
• remove(): Trả về và xóa phần tử đầu hàng, ném ngoại lệ nếu hàng rỗng.

3.2 Giao diện BlockingQueue

Là giao diện mở rộng Queue, hỗ trợ các phương thức chặn:

• Ném ngoại lệ: add()/remove()
• Trả về boolean: offer()/poll()
• Chặn vô hạn: put()/take()
• Chặn có thời gian: offer(timeout)/poll(timeout)

4. Các triển khai hàng đợi chặn trong Java

4.1 ArrayBlockingQueue

Hàng đợi chặn dựa trên mảng, có kích thước cố định. Cấu trúc chính:

final Object[] storage;
int dequeueIndex;
int enqueueIndex;
int size;
ReentrantLock queueLock;
Condition emptyCondition;
Condition fullCondition;

Nguyên lý hoạt động:

• Sử dụng ReentrantLock + Condition để đồng bộ hóa.
• Mảng được sử dụng như vòng tròn để tránh dịch chuyển phần tử.
• Khi thêm phần tử thất bại, luồng sẽ chờ ở fullCondition.
• Khi lấy phần tử thất bại, luồng sẽ chờ ở emptyCondition.

4.2 LinkedBlockingQueue

Hàng đợi chặn dựa trên danh sách liên kết, có thể là vô hạn (mặc định là Integer.MAX_VALUE). Đặc điểm:

int capacity;
AtomicInteger elementCount;
Node<E> front;
Node<E> rear;
ReentrantLock takeLock;
Condition notEmpty;
ReentrantLock putLock;
Condition notFull;

Ưu điểm:

• Sử dụng 2 khóa riêng biệt cho thêm/xóa để giảm cạnh tranh.
• Mỗi thao tác thêm/xóa không ảnh hưởng đến nhau.

4.3 DelayQueue

Hàng đợi chặn với cơ chế trì hoãn. Nguyên lý:

• Sử dụng PriorityQueue để sắp xếp theo thời gian trì hoãn.
• Luồng sẽ chờ đến khi phần tử đạt thời gian trì hoãn.
• Phù hợp cho các ứng dụng: định thời, quản lý cache.

4.4 PriorityBlockingQueue

Hàng đợi chặn có ưu tiên, sử dụng cấu trúc heap:

• Dữ liệu được lưu trong mảng theo cấu trúc cây nhị phân.
• Luôn lấy phần tử có độ ưu tiên thấp nhất (heap nhỏ).
• Sử dụng ReentrantLock + CAS để đảm bảo an toàn luồng.

4.5 SynchronousQueue

Hàng đợi chặn đặc biệt với kích thước 0:

• Mỗi thao tác thêm phải chờ đến khi có thao tác lấy.
• Tương tự như kênh truyền dữ liệu hai chiều, không cho phép tích trữ dữ liệu.