Queue, Deque, Stack: làm việc với hàng đợi và ngăn xếp

1. Giao diện Queue: hàng đợi cổ điển (FIFO)

Trong lập trình cũng như đời sống, có những tình huống không chỉ cần lưu tập hợp phần tử mà còn phải kiểm soát thứ tự xử lý của chúng. Hãy hình dung hàng đợi ở siêu thị: ai gần đầu hơn sẽ được phục vụ trước. Đây là nguyên lý FIFO — “vào trước — ra trước”. Còn chồng đĩa trong tủ hoạt động theo nguyên lý LIFO — “vào sau — ra trước”. Trong Java có các cấu trúc tương ứng: hàng đợi Queue, hàng đợi hai đầu Deque và ngăn xếp Stack.

Ứng dụng ở đâu:

• Xử lý tác vụ theo thứ tự đến (hàng đợi tác vụ, in tài liệu, xử lý sự kiện).
• Hiện thực hoàn tác/khôi phục (undo/redo) — ngăn xếp.
• Phân tích biểu thức, duyệt cây và đồ thị (tìm kiếm theo chiều rộng/sâu) và nhiều tình huống khác.

Hàng đợi là gì?

Hàng đợi (Queue) là một tập hợp được xây dựng theo nguyên lý FIFO. Phần tử được thêm vào cuối và lấy ra từ đầu. Như ở cửa hàng: ai đến sớm được phục vụ trước.

Các phương thức chính của giao diện Queue

offer(e)

add(e)

poll()

remove()

peek()

element()

Bạn sẽ thấy các cặp phương thức có hành vi tương tự. Khác biệt nằm ở “mức độ an toàn”: offer, poll, peek trả về giá trị đặc biệt khi không thành công (thường là null hoặc false) và không ném ngoại lệ, còn add, remove, element sẽ ném ngoại lệ trong các tình huống biên (hàng đợi rỗng, đôi khi tràn).

Ví dụ: hàng đợi tác vụ

import java.util.*;

public class QueueDemo {
    public static void main(String[] args) {
        Queue<String> tasks = new LinkedList<>();
        tasks.offer("Đánh răng");
        tasks.offer("Tập thể dục");
        tasks.offer("Uống cà phê");

        while (!tasks.isEmpty()) {
            String task = tasks.poll(); // Lấy tác vụ từ đầu hàng đợi
            System.out.println("Đang thực hiện: " + task);
        }
    }
}

Kết quả:

Đang thực hiện: Đánh răng
Đang thực hiện: Tập thể dục
Đang thực hiện: Uống cà phê

Vì sao thường dùng LinkedList?

Giao diện là một hợp đồng, và có nhiều hiện thực khác nhau. LinkedList thường được dùng vì nó thêm/xóa nhanh ở cả hai đầu. Tuy nhiên, một lựa chọn tuyệt vời là ArrayDeque. Cũng có các biến thể chuyên biệt: PriorityQueue (hàng đợi theo ưu tiên), sẽ nói ở phần dưới.

2. Giao diện Deque: hàng đợi hai đầu

Deque (Double Ended Queue) là hàng đợi có thể thêm và xóa phần tử ở cả hai phía: từ đầu và từ cuối. Như một chiếc xe buýt có hai cửa: có thể lên/xuống ở bên nào cũng được.

Deque = “lính đa năng”: có thể hoạt động như hàng đợi (FIFO), như ngăn xếp (LIFO) và cả kiểu lai.

Các phương thức chính của Deque

addFirst(e)

ochered.addFirst("A")

addLast(e)

ochered.addLast("B")

removeFirst()

ochered.removeFirst()

removeLast()

ochered.removeLast()

peekFirst()

ochered.peekFirst()

peekLast()

ochered.peekLast()

offerFirst(e)

ochered.offerFirst("C")

offerLast(e)

ochered.offerLast("D")

Ví dụ: Deque vừa là hàng đợi vừa là ngăn xếp

import java.util.*;

public class DequeDemo {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();

        // Dùng như hàng đợi (FIFO)
        deque.offerLast("A");
        deque.offerLast("B");
        deque.offerLast("C");
        System.out.println("Hàng đợi (FIFO):");
        while (!deque.isEmpty()) {
            System.out.println(deque.pollFirst());
        }

        // Dùng như ngăn xếp (LIFO)
        deque.offerLast("1");
        deque.offerLast("2");
        deque.offerLast("3");
        System.out.println("Ngăn xếp (LIFO):");
        while (!deque.isEmpty()) {
            System.out.println(deque.pollLast());
        }
    }
}

Kết quả:

Hàng đợi (FIFO):
A
B
C
Ngăn xếp (LIFO):
3
2
1

Vì sao ArrayDeque?

ArrayDeque là hiện thực Deque dựa trên mảng, nhanh và gọn. Với ngăn xếp và hàng đợi, nó thường nhanh và ổn định hơn Stack cũ, và không có kích thước cố định (chỉ giới hạn bởi bộ nhớ).

3. Stack: ngăn xếp — vào sau, ra trước (LIFO)

Ngăn xếp là cấu trúc theo nguyên lý LIFO: phần tử được lấy ra ở đỉnh là phần tử vừa được đưa vào sau cùng. Trong lập trình, ngăn xếp hữu ích cho lịch sử thao tác (undo), duyệt cấu trúc đệ quy (cây/đồ thị), tính toán biểu thức, v.v.

Lớp Stack (và vì sao không nên dùng)

Trong Java có lớp Stack, kế thừa từ Vector đã lỗi thời. Ngày nay không khuyến nghị dùng nó trong dự án mới. Nên ưu tiên Deque/ArrayDeque.

Các phương thức ngăn xếp (trên Deque)

push(e)

pop()

peek()

Lưu ý: trong Deque, các thao tác này tương ứng với addFirst/removeFirst/peekFirst, nhưng để tương thích, cũng có các tên “kiểu ngăn xếp” push/pop/peek.

Ví dụ: ngăn xếp bằng ArrayDeque

import java.util.*;

public class StackDemo {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();
        stack.push("Thứ nhất");
        stack.push("Thứ hai");
        stack.push("Thứ ba");

        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}

Kết quả:

Thứ ba
Thứ hai
Thứ nhất

Vì sao không dùng Stack?

• Stack được đồng bộ hóa (chậm hơn) và kế thừa từ Vector đã lỗi thời.
• ArrayDeque thường nhanh và gọn hơn, không khóa luồng.
• Nếu thấy Stack trong mã mới — thường là ứng viên để thay bằng ArrayDeque.

4. Khi nào dùng cái gì

LinkedList, ArrayDeque, PriorityQueue

ArrayDeque

ArrayDeque, LinkedList

Ví dụ đời thực:

• Hàng đợi ở ngân hàng — Queue.
• Lịch sử thao tác trong trình chỉnh sửa — Stack.
• Hàng xe buýt, vào/ra ở cả hai đầu — Deque.

5. Ví dụ mã: hiện thực hàng đợi và ngăn xếp trong mini‑app

Ví dụ 1: Hàng đợi in tài liệu

import java.util.*;

public class PrintQueueApp {
    public static void main(String[] args) {
        Queue<String> printQueue = new ArrayDeque<>();
        printQueue.offer("TaiLieu1.pdf");
        printQueue.offer("TaiLieu2.docx");
        printQueue.offer("TaiLieu3.xls");

        while (!printQueue.isEmpty()) {
            String doc = printQueue.poll();
            System.out.println("Đang in: " + doc);
        }
    }
}

Ví dụ 2: Ngăn xếp hoàn tác (undo)

import java.util.*;

public class UndoStackApp {
    public static void main(String[] args) {
        Deque<String> undoStack = new ArrayDeque<>();
        undoStack.push("Chèn văn bản");
        undoStack.push("Đổi màu");
        undoStack.push("Xóa hình ảnh");

        System.out.println("Hành động gần nhất: " + undoStack.peek()); // Xóa hình ảnh

        while (!undoStack.isEmpty()) {
            System.out.println("Hoàn tác: " + undoStack.pop());
        }
    }
}

Ví dụ 3: Hàng đợi hai đầu

import java.util.*;

public class DequeApp {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();
        deque.addFirst("A");
        deque.addLast("B");
        deque.addFirst("C");
        deque.addLast("D");

        System.out.println("Lấy từ đầu: " + deque.removeFirst()); // C
        System.out.println("Lấy từ cuối: " + deque.removeLast());   // D
        System.out.println("Còn lại: " + deque); // [A, B]
    }
}

6. Đặc điểm triển khai và lưu ý

• ArrayDeque là hiện thực nhanh và đa năng nhất cho hàng đợi/ngăn xếp trong đa số bài toán.
• LinkedList cũng hiện thực Deque; có thể hữu ích, nhưng với hàng đợi ngắn thường chậm hơn ArrayDeque.
• PriorityQueue là hàng đợi theo ưu tiên: thứ tự do ưu tiên quyết định (tự nhiên hoặc qua Comparator), không phải hàng đợi FIFO thông thường.
• Stack đã lỗi thời, được đồng bộ hóa; trong dự án mới nên ưu tiên ArrayDeque.
• Deque thuận tiện vì có thể thao tác cả đầu và cuối cấu trúc, bao phủ kịch bản của cả hàng đợi và ngăn xếp bằng một trừu tượng.

7. Lỗi thường gặp khi làm việc với hàng đợi và ngăn xếp

Lỗi số 1: Dùng Stack thay vì Deque.
Nhiều người mới thấy lớp Stack và dùng theo “cái tên”. Trong các dự án hiện đại, thay vào đó dùng ArrayDeque (hoặc LinkedList) với các phương thức push/pop.

Lỗi số 2: Vi phạm nguyên lý hoạt động của cấu trúc.
Cố truy cập phần tử theo chỉ số, ví dụ queue.get(0) hoặc stack.get(0). Không nên làm vậy — hãy dùng các phương thức tương ứng của hàng đợi và ngăn xếp (peek, poll, pop, v.v.).

Lỗi số 3: Dùng remove()/element()/add() mà không kiểm tra.
Các phương thức remove, element, add có thể ném ngoại lệ khi cấu trúc rỗng/tràn. An toàn hơn là dùng các phương thức “mềm” offer, poll, peek vốn trả về giá trị đặc biệt.

Lỗi số 4: Dùng ArrayDeque với phần tử null.
ArrayDeque không chấp nhận null. Cố gắng thêm null sẽ dẫn tới NullPointerException.

Lỗi số 5: Dùng PriorityQueue như hàng đợi thường.
Trong PriorityQueue, thứ tự do ưu tiên quyết định (tự nhiên hoặc cung cấp qua Comparator). Với FIFO nghiêm ngặt, hãy dùng ArrayDeque hoặc LinkedList.

Lỗi số 6: Sửa đổi hàng đợi/ngăn xếp khi duyệt bằng for-each.
Xóa phần tử khỏi bộ sưu tập trong khi for-each có thể dẫn đến ConcurrentModificationException. Để xóa, hãy dùng iterator hoặc các phương thức poll/pop trong vòng lặp như trong ví dụ.