# Bài 4: Queue Interface và các Implementations

#### Định nghĩa và Mục đích của Queue

**Queue** là một giao diện trong Collections Framework, đại diện cho một tập hợp các phần tử được lưu trữ theo thứ tự FIFO (First-In-First-Out). Queue thường được sử dụng trong các trường hợp cần quản lý thứ tự xử lý của các phần tử, như trong các hàng đợi công việc, tác vụ hoặc yêu cầu.

**Mục đích**:

* Quản lý thứ tự xử lý các phần tử theo thứ tự thêm vào (FIFO).
    
* Hỗ trợ các thao tác như thêm, lấy, và xem phần tử ở đầu hàng đợi.
    

#### Ví dụ Minh họa về Các Tình huống Sử dụng Queue

**Ví dụ 1**: Quản lý hàng đợi khách hàng trong một cửa hàng.

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

public class CustomerService {
    public static void main(String[] args) {
        Queue<String> customers = new LinkedList<>();
        customers.add("John");
        customers.add("Jane");
        customers.add("Jack");

        System.out.println("Khách hàng đầu tiên: " + customers.poll()); // Lấy và xóa phần tử đầu tiên
        System.out.println("Khách hàng tiếp theo: " + customers.peek()); // Xem nhưng không xóa phần tử đầu tiên
    }
}
```

**Ví dụ 2**: Quản lý hàng đợi tác vụ trong một hệ thống xử lý song song.

```java
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.Queue;

public class TaskManagement {
    public static void main(String[] args) {
        Queue<String> tasks = new ConcurrentLinkedQueue<>();
        tasks.add("Task1");
        tasks.add("Task2");
        tasks.add("Task3");

        while (!tasks.isEmpty()) {
            System.out.println("Xử lý: " + tasks.poll());
        }
    }
}
```

#### Các Implementations của Queue

1. **LinkedList**:
    
    * **Mô tả**: Triển khai hàng đợi sử dụng danh sách liên kết đôi.
        
    * **Đặc điểm**: Hỗ trợ tất cả các thao tác của Queue và Deque, cho phép thêm/xóa ở cả đầu và cuối danh sách.
        
    * **Tình huống sử dụng**: Thích hợp cho các ứng dụng cần hàng đợi linh hoạt, cho phép truy cập và thay đổi ở cả đầu và cuối.
        
2. **PriorityQueue**:
    
    * **Mô tả**: Triển khai hàng đợi ưu tiên, các phần tử được sắp xếp theo thứ tự tự nhiên hoặc theo Comparator.
        
    * **Đặc điểm**: Không cho phép phần tử null, không duy trì thứ tự FIFO mà dựa trên ưu tiên.
        
    * **Tình huống sử dụng**: Thích hợp cho các ứng dụng cần xử lý các phần tử dựa trên mức độ ưu tiên.
        
3. **ArrayDeque**:
    
    * **Mô tả**: Triển khai hàng đợi hai đầu sử dụng mảng động.
        
    * **Đặc điểm**: Hỗ trợ các thao tác thêm/xóa ở cả hai đầu hàng đợi, không có giới hạn về kích thước.
        
    * **Tình huống sử dụng**: Thích hợp cho các ứng dụng cần hàng đợi hiệu suất cao và linh hoạt.
        
4. **ConcurrentLinkedQueue**:
    
    * **Mô tả**: Triển khai hàng đợi không đồng bộ (non-blocking) sử dụng danh sách liên kết.
        
    * **Đặc điểm**: Được thiết kế cho các ứng dụng đa luồng, đảm bảo an toàn trong môi trường đa luồng mà không cần đồng bộ hóa.
        
    * **Tình huống sử dụng**: Thích hợp cho các ứng dụng cần hàng đợi không đồng bộ trong môi trường đa luồng.
        

#### So sánh Hiệu năng và Đặc điểm Nổi bật của Từng Implementation

| **Đặc điểm** | **LinkedList** | **PriorityQueue** | **ArrayDeque** | **ConcurrentLinkedQueue** |
| --- | --- | --- | --- | --- |
| Thêm phần tử | O(1) | O(log n) | O(1) | O(1) |
| Lấy phần tử | O(1) | O(log n) | O(1) | O(1) |
| Truy cập ngẫu nhiên | O(n) | O(n) | O(n) | O(n) |
| Đồng bộ hóa | Không | Không | Không | Có |
| Ứng dụng | Hàng đợi linh hoạt | Hàng đợi ưu tiên | Hàng đợi hiệu suất cao | Hàng đợi không đồng bộ |

#### Ví dụ và Bài tập Thực hành với Queue

**Ví dụ 1**: Quản lý hàng đợi khách hàng

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

public class CustomerService {
    public static void main(String[] args) {
        Queue<String> customers = new LinkedList<>();
        customers.add("John");
        customers.add("Jane");
        customers.add("Jack");

        System.out.println("Khách hàng đầu tiên: " + customers.poll()); // Lấy và xóa phần tử đầu tiên
        System.out.println("Khách hàng tiếp theo: " + customers.peek()); // Xem nhưng không xóa phần tử đầu tiên
    }
}
```

**Ví dụ 2**: Quản lý hàng đợi tác vụ

```java
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.Queue;

public class TaskManagement {
    public static void main(String[] args) {
        Queue<String> tasks = new ConcurrentLinkedQueue<>();
        tasks.add("Task1");
        tasks.add("Task2");
        tasks.add("Task3");

        while (!tasks.isEmpty()) {
            System.out.println("Xử lý: " + tasks.poll());
        }
    }
}
```

**Bài tập Thực hành**:

1. **Bài tập 1**: Tạo một hàng đợi chứa các số nguyên từ 1 đến 10. In ra các phần tử của hàng đợi.
    
    * **Gợi ý**:
        
        ```java
        Queue<Integer> numbers = new LinkedList<>();
        for (int i = 1; i <= 10; i++) {
            numbers.add(i);
        }
        
        while (!numbers.isEmpty()) {
            System.out.println(numbers.poll());
        }
        ```
        
2. **Bài tập 2**: Sử dụng `PriorityQueue` để quản lý các công việc dựa trên mức độ ưu tiên (ưu tiên cao hơn được xử lý trước).
    
    * **Gợi ý**:
        
        ```java
        import java.util.PriorityQueue;
        import java.util.Queue;
        
        public class PriorityTaskManagement {
            static class Task implements Comparable<Task> {
                private String name;
                private int priority;
        
                public Task(String name, int priority) {
                    this.name = name;
                    this.priority = priority;
                }
        
                @Override
                public int compareTo(Task other) {
                    return Integer.compare(this.priority, other.priority);
                }
        
                @Override
                public String toString() {
                    return name + " (Priority: " + priority + ")";
                }
            }
        
            public static void main(String[] args) {
                Queue<Task> tasks = new PriorityQueue<>();
                tasks.add(new Task("Task1", 3));
                tasks.add(new Task("Task2", 1));
                tasks.add(new Task("Task3", 2));
        
                while (!tasks.isEmpty()) {
                    System.out.println("Xử lý: " + tasks.poll());
                }
            }
        }
        ```
        
3. **Bài tập 3**: Sử dụng `ArrayDeque` để triển khai một hàng đợi hai đầu, cho phép thêm và xóa phần tử ở cả hai đầu.
    
    * **Gợi ý**:
        
        ```java
        import java.util.ArrayDeque;
        import java.util.Deque;
        
        public class DequeExample {
            public static void main(String[] args) {
                Deque<String> deque = new ArrayDeque<>();
                deque.addFirst("Front1");
                deque.addLast("End1");
                deque.addFirst("Front2");
                deque.addLast("End2");
        
                System.out.println("Phần tử đầu tiên: " + deque.pollFirst()); // Front2
                System.out.println("Phần tử cuối cùng: " + deque.pollLast()); // End2
            }
        }
        ```
        

**Bài tập Nâng cao**:

1. Tạo một hàng đợi chứa các đối tượng `Customer` với các thuộc tính `id`, `name`, `serviceTime`. Viết phương thức để tìm khách hàng có thời gian phục vụ lâu nhất.
    
    * **Gợi ý**:
        
        ```java
        import java.util.LinkedList;
        import java.util.Queue;
        
        class Customer {
            private String id;
            private String name;
            private int serviceTime;
        
            public Customer(String id, String name, int serviceTime) {
                this.id = id;
                this.name = name;
                this.serviceTime = serviceTime;
            }
        
            public String getId() {
                return id;
            }
        
            public String getName() {
                return name;
            }
        
            public int getServiceTime() {
                return serviceTime;
            }
        }
        
        public class CustomerManagement {
            public static void main(String[] args) {
                Queue<Customer> customers = new LinkedList<>();
                customers.add(new Customer("C001", "John", 10));
                customers.add(new Customer("C002", "Jane", 15));
                customers.add(new Customer("C003", "Jack", 5));
        
                Customer maxServiceTimeCustomer = customers.stream().max((c1, c2) -> Integer.compare(c1.getServiceTime(), c2.getServiceTime())).orElse(null);
                if (maxServiceTimeCustomer != null) {
                    System.out.println("Khách hàng có thời gian phục vụ lâu nhất: " + maxServiceTimeCustomer.getName() + " (" + maxServiceTimeCustomer.getServiceTime() + " phút)");
                } else {
                    System.out.println("Không có khách hàng nào.");
                }
            }
        }
        ```
        

2. Tạo một hàng đợi chứa các đối tượng `Document` với các thuộc tính `id`, `name`, `pages`. Viết phương thức để sắp xếp các tài liệu dựa trên số trang và in ra thứ tự xử lý.
    
    * **Gợi ý**:
        
        ```java
        import java.util.PriorityQueue;
        import java.util.Queue;
        
        class Document implements Comparable<Document> {
            private String id;
            private String name;
            private int pages;
        
            public Document(String id, String name, int pages) {
                this.id = id;
                this.name = name;
                this.pages = pages;
            }
        
            @Override
            public int compareTo(Document other) {
                return Integer.compare(this.pages, other.pages);
            }
        
            @Override
            public String toString() {
                return name + " (Pages: " + pages + ")";
            }
        }
        
        public class DocumentManagement {
            public static void main(String[] args) {
                Queue<Document> documents = new PriorityQueue<>();
                documents.add(new Document("D001", "Document1", 10));
                documents.add(new Document("D002", "Document2", 5));
                documents.add(new Document("D003", "Document3", 15));
        
                System.out.println("Thứ tự xử lý tài liệu:");
                while (!documents.isEmpty()) {
                    System.out.println(documents.poll());
                }
            }
        }
        ```
        

### Tổng kết

Giao diện `Queue` trong Java Collections Framework cung cấp một cách hiệu quả để lưu trữ và thao tác với các phần tử theo thứ tự FIFO. Hiểu và sử dụng đúng các triển khai của `Queue` như `LinkedList`, `PriorityQueue`, `ArrayDeque`, và `ConcurrentLinkedQueue` sẽ giúp lập trình viên tối ưu hóa hiệu suất và quản lý các hàng đợi phần tử một cách linh hoạt và hiệu quả. Việc lựa chọn đúng loại `Queue` dựa trên yêu cầu cụ thể của ứng dụng là một kỹ năng quan trọng mà mọi lập trình viên Java cần có.