Cấu trúc dữ liệu Queue: Hàng đợi và Ứng dụng trong Java

Chào mừng bạn đến với bài viết thứ 6 trong series về cấu trúc dữ liệu và giải thuật. Chúng ta sẽ khám phá cấu trúc dữ liệu Queue (hàng đợi). Ngôn ngữ lập trình Java sẽ được sử dụng để minh họa.

Queue là gì?

Queue (hàng đợi) là một cấu trúc dữ liệu tuyến tính. Nó tuân theo nguyên tắc FIFO (First-In, First-Out). Phần tử nào được thêm vào trước sẽ được lấy ra trước. Hãy tưởng tượng bạn đang xếp hàng mua vé xem phim. Người đến trước sẽ được phục vụ trước.

Nguyên lý FIFO (First-In, First-Out)

FIFO là trái tim của Queue. Nó đảm bảo tính công bằng trong việc xử lý các phần tử. Các phần tử được xử lý theo đúng thứ tự mà chúng được thêm vào. Điều này rất quan trọng trong nhiều ứng dụng thực tế.

Các thao tác cơ bản của Queue

Queue có ba thao tác cơ bản:

• Enqueue: Thêm một phần tử vào cuối hàng đợi.
• Dequeue: Loại bỏ phần tử ở đầu hàng đợi.
• Peek: Xem phần tử ở đầu hàng đợi mà không loại bỏ nó.

Enqueue

Thao tác enqueue thêm một phần tử mới vào cuối queue. Nó giống như việc một người mới đến và xếp vào cuối hàng.

Dequeue

Thao tác dequeue loại bỏ phần tử ở đầu queue. Nó giống như người đầu hàng được phục vụ và rời đi.

Peek

Thao tác peek cho phép bạn xem phần tử đầu tiên trong queue. Nó giống như nhìn vào người đầu hàng để biết ai sẽ được phục vụ tiếp theo. Thao tác này không làm thay đổi queue.

Ứng dụng thực tế của Queue

Queue được sử dụng rộng rãi trong nhiều lĩnh vực khác nhau:

• Hàng đợi in: Các tài liệu in được xếp hàng đợi và in theo thứ tự.
• Xử lý tác vụ bất đồng bộ: Các tác vụ được xếp hàng đợi và xử lý lần lượt.
• Điều phối tài nguyên: Các yêu cầu tài nguyên được xếp hàng đợi và cấp phát theo thứ tự.
• Tìm kiếm theo chiều rộng (BFS): Trong các thuật toán đồ thị.

Hàng đợi in

Khi bạn in nhiều tài liệu cùng một lúc, chúng sẽ được đưa vào một hàng đợi in. Máy in sẽ lấy từng tài liệu từ hàng đợi và in chúng theo thứ tự.

Xử lý tác vụ bất đồng bộ

Trong các ứng dụng web, các tác vụ nặng có thể được xử lý bất đồng bộ. Các tác vụ được đưa vào một hàng đợi và xử lý bởi một worker process. Điều này giúp cải thiện hiệu suất của ứng dụng.

Triển khai Queue bằng Java

Java cung cấp interface `Queue` và các lớp triển khai như `LinkedList` và `ArrayDeque`. Chúng ta có thể sử dụng chúng để tạo một Queue.

Sử dụng LinkedList

`LinkedList` là một triển khai phổ biến của Queue. Nó sử dụng một danh sách liên kết để lưu trữ các phần tử.

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();

        // Enqueue
        queue.offer("A");
        queue.offer("B");
        queue.offer("C");

        System.out.println("Queue: " + queue); // Output: Queue: [A, B, C]

        // Peek
        String first = queue.peek();
        System.out.println("First element: " + first); // Output: First element: A

        // Dequeue
        String removed = queue.poll();
        System.out.println("Removed element: " + removed); // Output: Removed element: A

        System.out.println("Queue after dequeue: " + queue); // Output: Queue after dequeue: [B, C]
    }
}

Trong ví dụ trên, chúng ta sử dụng `offer()` để thêm phần tử vào queue (enqueue). `peek()` để xem phần tử đầu tiên. `poll()` để loại bỏ phần tử đầu tiên (dequeue).

Sử dụng ArrayDeque

`ArrayDeque` là một triển khai khác của Queue. Nó sử dụng một mảng động để lưu trữ các phần tử. `ArrayDeque` thường nhanh hơn `LinkedList` trong một số trường hợp.

import java.util.ArrayDeque;
import java.util.Queue;

public class ArrayDequeExample {
    public static void main(String[] args) {
        Queue<String> queue = new ArrayDeque<>();

        // Enqueue
        queue.offer("A");
        queue.offer("B");
        queue.offer("C");

        System.out.println("Queue: " + queue); // Output: Queue: [A, B, C]

        // Peek
        String first = queue.peek();
        System.out.println("First element: " + first); // Output: First element: A

        // Dequeue
        String removed = queue.poll();
        System.out.println("Removed element: " + removed); // Output: Removed element: A

        System.out.println("Queue after dequeue: " + queue); // Output: Queue after dequeue: [B, C]
    }
}

So sánh LinkedList và ArrayDeque

Cả `LinkedList` và `ArrayDeque` đều là các triển khai tốt của Queue. `LinkedList` tốt hơn khi bạn cần thêm hoặc xóa các phần tử ở giữa danh sách. `ArrayDeque` thường nhanh hơn cho các thao tác enqueue và dequeue.

Các lưu ý khi sử dụng Queue

Khi sử dụng Queue, hãy chú ý đến các trường hợp sau:

• Queue rỗng: Cố gắng dequeue hoặc peek một queue rỗng sẽ gây ra lỗi.
• Kích thước Queue: Nếu bạn sử dụng một Queue có kích thước giới hạn, hãy đảm bảo rằng bạn không thêm quá nhiều phần tử.

Kết luận

Queue là một cấu trúc dữ liệu mạnh mẽ và hữu ích. Nó được sử dụng rộng rãi trong nhiều ứng dụng thực tế. Việc hiểu rõ nguyên lý hoạt động và các thao tác cơ bản của Queue sẽ giúp bạn giải quyết nhiều vấn đề trong lập trình. Hãy thử triển khai Queue bằng Java và khám phá thêm các ứng dụng khác của nó. Chúc bạn thành công!