Interface Queue<E>

Queue<E> là một collection được thiết kế để lưu trữ các phần tử trước khi chúng được xử lý. Ngoài các thao tác cơ bản của Collection, các hàng đợi (queues) còn cung cấp thêm các thao tác chèn, trích xuất, và kiểm tra các phần tử. Mỗi thao tác này tồn tại dưới hai dạng: một dạng ném ra ngoại lệ nếu thao tác thất bại, và dạng kia trả về một giá trị đặc biệt (thường là null hoặc false, tùy thuộc vào thao tác).

Tóm tắt các phương thức của Queue

Thứ tự của các phần tử

↳ Các hàng đợi thường sắp xếp các phần tử theo thứ tự FIFO (first-in-first-out), nhưng không phải luôn luôn. Một số ngoại lệ bao gồm hàng đợi ưu tiên (priority queues), nơi các phần tử được sắp xếp theo comparator cung cấp hoặc theo thứ tự tự nhiên của chúng, và hàng đợi LIFO (last-in-first-out), như các ngăn xếp (stacks).

Phương thức offer()

↳ Phương thức offer chèn một phần tử nếu có thể, nếu không sẽ trả về false. Điều này khác với phương thức add trong Collection, chỉ thất bại bằng cách ném ra ngoại lệ không kiểm tra được (unchecked exception). Offer được thiết kế cho các trường hợp mà thất bại là một sự kiện bình thường, chẳng hạn trong các hàng đợi có dung lượng cố định (hoặc "bounded").

Phương thức remove() và poll()

↳ Cả hai phương thức này đều xóa và trả về phần tử đầu của hàng đợi. Sự khác biệt chính là khi hàng đợi trống: remove() sẽ ném ra ngoại lệ, trong khi poll() sẽ trả về null.

Phương thức element() và peek()

↳ Hai phương thức này trả về nhưng không xóa phần tử đầu tiên của hàng đợi.

↳ Không định nghĩa các phương thức chặn: Queue không định nghĩa các phương thức chặn (blocking methods), thường được sử dụng trong lập trình đồng thời. Các phương thức này được định nghĩa trong interface BlockingQueue, mở rộng từ Queue.

Không cho phép phần tử null

↳ Hầu hết các triển khai của Queue không cho phép chèn phần tử null, mặc dù một số như LinkedList không cấm điều này. Tuy nhiên, null không nên được chèn vào một hàng đợi, vì null được sử dụng như một giá trị trả về đặc biệt bởi phương thức poll để chỉ ra rằng hàng đợi không có phần tử.

Không định nghĩa phương thức equals và hashCode dựa trên phần tử

↳ Các triển khai của Queue thường không định nghĩa các phiên bản của phương thức equals và hashCode dựa trên phần tử, mà thay vào đó thừa kế các phiên bản dựa trên định danh từ lớp Object. Điều này là do sự bình đẳng dựa trên phần tử không phải lúc nào cũng được định nghĩa rõ ràng cho các hàng đợi có cùng phần tử nhưng có các thuộc tính sắp xếp khác nhau.

Thành viên của Java Collections Framework

↳ Interface Queue là một thành phần của Java Collections Framework, giúp chuẩn hóa cách xử lý các hàng đợi trong Java.

Khai báo Interface Queue<E> trong Java

Để sử dụng Interface Queue<E>, bạn cần import gói java.util vào đầu file Java của mình. Gói này cung cấp các lớp và giao diện để làm việc với các collection, bao gồm cả hàng đợi (queue), trong Java.

Cú pháp câu lệnh import:

import java.util.Queue;

Cú pháp khai báo Interface Queue<E>:

public interface Queue<E>
extends Collection<E>

Dưới đây là giải thích chi tiết về cú pháp khai báo này:

↳ public: Cho biết interface Queue có thể được sử dụng ở mọi nơi trong chương trình.

↳ interface: Khai báo một giao diện (interface) – nơi định nghĩa các phương thức nhưng không cài đặt.

↳ Queue<E>: Tên interface là Queue, sử dụng generic với kiểu phần tử là E. Ví dụ: Queue<String> là hàng đợi các chuỗi.

↳ extends Collection<E>: Queue kế thừa interface Collection, nghĩa là nó là một kiểu tập hợp (collection) đặc biệt có các quy tắc xử lý phần tử theo nguyên tắc hàng đợi.

Tính năng và Quy tắc của Queue<E>

↳ Tuân theo Quy tắc FIFO: Queue (Hàng đợi) vận hành theo một nguyên tắc cốt lõi: FIFO (viết tắt của First-In-First-Out), có nghĩa là "Vào trước, Ra trước". Điều này được hiểu như sau: Phần tử được thêm vào Queue đầu tiên sẽ là phần tử được lấy ra khỏi Queue đầu tiên. Mọi phần tử mới đều được thêm vào cuối hàng đợi. Mọi phần tử được lấy ra đều xuất phát từ đầu hàng đợi. Nguyên tắc này đảm bảo rằng các phần tử được xử lý theo đúng trình tự thời gian mà chúng được thêm vào.

↳ Thao tác với phần tử: Queue cung cấp các phương thức để thêm phần tử vào hàng đợi (offer(E e), add(E e)), loại bỏ phần tử khỏi hàng đợi (poll(), remove()), và kiểm tra phần tử đầu tiên mà không loại bỏ (peek(), element()).

↳ Không cho phép phần tử null: Một số lớp triển khai của Queue có thể không cho phép phần tử null. Việc thêm phần tử null có thể dẫn đến ngoại lệ hoặc hành vi không mong muốn trong các lớp triển khai cụ thể.

Các phương thức của Interface Queue<E>

Interface Queue<E> cung cấp một số phương thức sử dụng để quản lý các phần tử trong hàng đợi (queue) theo cách mà bạn có thể thêm, lấy, và xóa các phần tử. Dưới đây là danh sách tất cả các phương thức của Interface Queue<E> trong Java:

↳ boolean add(E e): Thêm phần tử e vào hàng đợi. Nếu hàng đợi đã đầy, sẽ ném ra ngoại lệ IllegalStateException.

↳ boolean offer(E e): Thêm phần tử e vào hàng đợi nếu có thể thực hiện ngay lập tức. Trả về true nếu thành công, false nếu hàng đợi đầy.

↳ poll(): Lấy và xóa phần tử đầu của hàng đợi. Nếu hàng đợi rỗng, trả về null.

↳ peek(): phần tử đầu của hàng đợi mà không xóa nó. Nếu hàng đợi rỗng, trả về null.

↳ element(): Lấy phần tử đầu của hàng đợi. Nếu hàng đợi rỗng, ném ra ngoại lệ NoSuchElementException.

↳ remove(): Lấy và xóa phần tử đầu của hàng đợi. Nếu hàng đợi rỗng, ném ra ngoại lệ NoSuchElementException.

Một Queue điển hình

Một Queue điển hình bao gồm các thành phần chính sau:

↳ Front (Đầu hàng đợi): Vị trí đầu tiên của hàng đợi, nơi phần tử đầu tiên sẽ được lấy ra.

↳ Rear (Cuối hàng đợi): Vị trí cuối cùng của hàng đợi, nơi phần tử mới sẽ được thêm vào.

↳ Array (Mảng) hoặc LinkedList (Danh sách liên kết): Là nơi lưu trữ các phần tử trong hàng đợi.

Cách hoạt động của Queue

Queue (Hàng đợi) vận hành theo một nguyên tắc cốt lõi: FIFO (viết tắt của First-In-First-Out), có nghĩa là "Vào trước, Ra trước". Điều này được hiểu như sau: Phần tử được thêm vào Queue đầu tiên sẽ là phần tử được lấy ra khỏi Queue đầu tiên. Mọi phần tử mới đều được thêm vào cuối hàng đợi. Mọi phần tử được lấy ra đều xuất phát từ đầu hàng đợi.

↳ Enqueue (Thêm phần tử): Thêm một phần tử mới vào cuối hàng đợi. Rear sẽ di chuyển đến vị trí mới sau khi thêm phần tử.

↳ Dequeue (Lấy phần tử): Loại bỏ phần tử từ đầu hàng đợi và trả về phần tử đó. Front sẽ di chuyển đến vị trí tiếp theo sau khi loại bỏ phần tử.

↳ Peek/Front (Xem phần tử đầu): Trả về phần tử ở đầu hàng đợi mà không loại bỏ nó.

↳ isEmpty (Kiểm tra rỗng): Kiểm tra xem hàng đợi có rỗng hay không.

↳ isFull (Kiểm tra đầy): Kiểm tra xem hàng đợi có đầy không (đối với hàng đợi kích thước cố định).

Cách tự triển khai một thư viện chuẩn cho cấu trúc dữ liệu Queue bằng cách sử dụng mảng trong Java mà không sử dụng thư viện có sẵn:

// Tạo lớp MyQueue với kiểu dữ liệu tổng quát T
public class Queue<T> {
    private T[] queueArray; // Mảng để lưu trữ các phần tử của Queue
    private int front;      // Chỉ số của phần tử đầu tiên
    private int rear;       // Chỉ số của phần tử cuối cùng
    private int size;       // Số lượng phần tử hiện tại trong Queue
    private int capacity;   // Kích thước tối đa của Queue

    // Phương thức khởi tạo Queue với kích thước cố định
    public Queue(int capacity) {
        this.capacity = capacity;
        this.queueArray = (T[]) new Object[capacity]; // Khởi tạo mảng với kích thước cố định
        this.front = 0;
        this.rear = -1;
        this.size = 0;
    }

    // Phương thức thêm phần tử vào cuối Queue
    public void enqueue(T value) {
        if (isFull()) { // Kiểm tra nếu Queue đã đầy
            System.out.println("Queue is full. Cannot enqueue " + value);
            return;
        }
        rear = (rear + 1) % capacity; // Tăng chỉ số rear (tuần hoàn)
        queueArray[rear] = value;     // Thêm phần tử mới vào cuối
        size++;                       // Tăng kích thước của Queue
    }

    // Phương thức lấy phần tử từ đầu Queue
    public T dequeue() {
        if (isEmpty()) { // Kiểm tra nếu Queue rỗng
            System.out.println("Queue is empty. Cannot dequeue.");
            return null;
        }
        T value = queueArray[front]; // Lấy phần tử đầu
        front = (front + 1) % capacity; // Tăng chỉ số front (tuần hoàn)
        size--;                        // Giảm kích thước của Queue
        return value;                  // Trả về phần tử đã lấy
    }

    // Phương thức xem phần tử ở đầu Queue mà không lấy ra
    public T peek() {
        if (isEmpty()) { // Kiểm tra nếu Queue rỗng
            System.out.println("Queue is empty. Nothing to peek.");
            return null;
        }
        return queueArray[front]; // Trả về phần tử đầu
    }

    // Phương thức kiểm tra nếu Queue rỗng
    public boolean isEmpty() {
        return size == 0;
    }

    // Phương thức kiểm tra nếu Queue đầy
    public boolean isFull() {
        return size == capacity;
    }

    // Phương thức lấy kích thước hiện tại của Queue
    public int size() {
        return size;
    }
}

Với ví dụ MyQueue này, bạn đã thấy cách chúng ta có thể tự xây dựng một cấu trúc dữ liệu Queue chỉ bằng mảng trong Java mà không cần dùng đến các thư viện có sẵn. Việc tự triển khai giúp bạn hiểu sâu hơn về cách Queue hoạt động và quản lý dữ liệu "vào trước, ra trước" (FIFO). Điều này rất hữu ích để củng cố kiến thức nền tảng về cấu trúc dữ liệu và giải thuật.