ArrayDeque trong Java (Java ArrayDeque)

1. ArrayDeque là gì?

ArrayDeque là một lớp trong Java thuộc gói java.util. Nó cung cấp một hàng đợi hai đầu (double-ended queue) dựa trên một mảng động. Điều này có nghĩa là bạn có thể thêm và xóa phần tử từ cả hai đầu (đầu và đuôi) của hàng đợi một cách hiệu quả.

2. Các đặc điểm chính của ArrayDeque

1. Không giới hạn kích thước: Kích thước của mảng bên trong sẽ được tự động mở rộng nếu cần.
2. Hiệu suất cao:
   • Nhanh hơn Stack khi được sử dụng như một ngăn xếp.
   • Nhanh hơn LinkedList khi được sử dụng như một hàng đợi.
3. Không cho phép phần tử null: ArrayDeque không cho phép lưu trữ giá trị null.
4. Không đồng bộ: Nó không đồng bộ hóa, vì vậy không an toàn khi sử dụng trong môi trường đa luồng trừ khi bạn tự quản lý việc đồng bộ hóa.

3. Một số phương thức thường dùng

• Thêm/xóa ở đầu:
  • addFirst(E e) / offerFirst(E e): Thêm phần tử vào đầu hàng đợi.
  • pollFirst() / removeFirst(): Lấy và xóa phần tử ở đầu hàng đợi.
  • peekFirst() / getFirst(): Lấy nhưng không xóa phần tử ở đầu hàng đợi.
• Thêm/xóa ở cuối:
  • addLast(E e) / offerLast(E e): Thêm phần tử vào cuối hàng đợi.
  • pollLast() / removeLast(): Lấy và xóa phần tử ở cuối hàng đợi.
  • peekLast() / getLast(): Lấy nhưng không xóa phần tử ở cuối hàng đợi.
• Hoạt động như một ngăn xếp:
  • push(E e): Thêm phần tử vào đầu hàng đợi (giống như addFirst).
  • pop(): Lấy và xóa phần tử từ đầu hàng đợi (giống như removeFirst).

4. Cách sử dụng ArrayDeque

Dưới đây là một ví dụ minh họa việc sử dụng ArrayDeque:

import java.util.ArrayDeque;

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

        // Thêm phần tử vào cuối
        deque.addLast("A");
        deque.addLast("B");

        // Thêm phần tử vào đầu
        deque.addFirst("C");

        System.out.println("Deque ban đầu: " + deque);

        // Lấy và xóa phần tử ở đầu
        Object first = deque.pollFirst();
        System.out.println("Phần tử ở đầu: " + first);
        System.out.println("Deque sau khi xóa phần tử ở đầu: " + deque);

        // Lấy nhưng không xóa phần tử ở cuối
        Object last = deque.peekLast();
        System.out.println("Phần tử ở cuối: " + last);

        // Hoạt động như một ngăn xếp
        deque.push("XYZ");
        System.out.println("Deque sau khi push: " + deque);

        Object popped = deque.pop();
        System.out.println("Phần tử pop ra: " + popped);
        System.out.println("Deque cuối cùng: " + deque);
    }
}

– Kết quả in ra:

Deque ban đầu: [C, A, B]
Phần tử ở đầu: C
Deque sau khi xóa phần tử ở đầu: [A, B]
Phần tử ở cuối: B
Deque sau khi push: [XYZ, A, B]
Phần tử pop ra: XYZ
Deque cuối cùng: [A, B]

5. Câu hỏi phỏng vấn ArrayDequeue

1. ArrayDeque là gì trong Java?

Trả lời:
ArrayDeque là một lớp trong Java Collections Framework, nằm trong gói java.util. Nó là một Double-Ended Queue (Deque) dựa trên mảng (array-based), hỗ trợ chèn và xóa phần tử ở cả hai đầu với hiệu suất cao (O(1) trong hầu hết các trường hợp). ArrayDeque không có giới hạn kích thước cố định và có thể tự động mở rộng khi cần.

2. ArrayDeque khác gì so với LinkedList?

Trả lời:

• Hiệu suất:
  • ArrayDeque thường nhanh hơn LinkedList vì nó sử dụng mảng để lưu trữ, giảm chi phí bộ nhớ do không cần lưu trữ các con trỏ như trong LinkedList.
• Bộ nhớ:
  • ArrayDeque sử dụng mảng động để quản lý bộ nhớ.
  • LinkedList sử dụng cấu trúc liên kết (linked structure) với các node, chiếm nhiều bộ nhớ hơn.
• Null:
  • ArrayDeque không cho phép lưu trữ null elements.
  • LinkedList cho phép lưu trữ null.

3. ArrayDeque có thread-safe không?

Trả lời:
Không, ArrayDeque không phải là thread-safe. Nếu cần sử dụng trong môi trường đa luồng, bạn cần đồng bộ hóa thủ công hoặc sử dụng các lớp thread-safe như ConcurrentLinkedDeque.

4. Khi nào nên sử dụng ArrayDeque thay vì các Collection khác?

Trả lời:

• Khi bạn cần một deque hiệu suất cao mà không yêu cầu thread-safety.
• Khi cần thực hiện các thao tác chèn/xóa ở cả hai đầu nhanh hơn so với các cấu trúc khác như LinkedList.
• Khi bạn cần một cấu trúc dữ liệu làm stack hoặc queue:
  • Stack: Thay thế cho Stack class với các phương thức như push(), pop().
  • Queue: Làm queue với các phương thức offer(), poll().

5. Các phương thức chính của ArrayDeque là gì?

Trả lời:

• Thêm phần tử:
  • addFirst(E e) / addLast(E e)
  • offerFirst(E e) / offerLast(E e)
• Lấy và xóa phần tử:
  • removeFirst() / removeLast()
  • pollFirst() / pollLast()
• Lấy phần tử không xóa:
  • getFirst() / getLast()
  • peekFirst() / peekLast()
• Sử dụng như Stack:
  • push(E e): Thêm phần tử vào đầu.
  • pop(): Lấy và xóa phần tử đầu.

6. Sự khác biệt giữa addFirst và offerFirst là gì?

Trả lời:

• addFirst(E e):
  • Ném IllegalStateException nếu không thể thêm phần tử (dù điều này hiếm khi xảy ra với ArrayDeque).
• offerFirst(E e):
  • Trả về false nếu không thể thêm phần tử, thay vì ném ngoại lệ.

7. Viết một đoạn code minh họa cách sử dụng ArrayDeque như một Stack

import java.util.ArrayDeque;

public class App {
    public static void main(String[] args) {
        ArrayDeque stack = new ArrayDeque<>();

        // Thêm phần tử vào stack
        stack.push(10);
        stack.push(20);
        stack.push(30);

        // Lấy phần tử trên cùng
        System.out.println("phần tử đầu tiên: " + stack.peek());

        // Xóa và in các phần tử
        while (!stack.isEmpty()) {
            System.out.println("Phần tử: " + stack.pop());
        }
    }
}

8. Viết một đoạn code minh họa cách sử dụng ArrayDeque như một Queue.

import java.util.ArrayDeque;

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

        // Thêm phần tử vào hàng đợi
        queue.offer("Cam");
        queue.offer("Quýt");
        queue.offer("Mít");

        // Lấy phần tử đầu hàng đợi
        System.out.println("Quả đầu tiên: " + queue.peek());

        // Xóa và in các phần tử
        while (!queue.isEmpty()) {
            System.out.println("Quả: " + queue.poll());
        }
    }
}

9. ArrayDeque có giới hạn kích thước không?

Trả lời:
Không, ArrayDeque không có giới hạn kích thước cố định. Khi kích thước mảng nội bộ đầy, nó sẽ tự động mở rộng gấp đôi kích thước hiện tại.

10. ArrayDeque có cho phép lưu trữ giá trị null không?

Trả lời:
Không, ArrayDeque không cho phép lưu trữ các giá trị null. Điều này nhằm tránh nhầm lẫn khi sử dụng các phương thức như poll() hoặc peek().

11. ArrayDeque có ưu điểm gì so với Stack hoặc Vector?

Trả lời:

• So với Stack:
  • ArrayDeque nhanh hơn và không đồng bộ hóa (stack có thể gây hiệu suất thấp hơn vì nó synchronized).
  • Stack là một lớp lỗi thời từ JDK 1.0, trong khi ArrayDeque được giới thiệu trong JDK 1.6 và được khuyến nghị sử dụng.
• So với Vector:
  • Vector sử dụng bộ nhớ nhiều hơn do đồng bộ hóa.
  • ArrayDeque nhanh hơn trong hầu hết các trường hợp.

12. Cách ArrayDeque quản lý mảng bên trong như thế nào?

Trả lời:
ArrayDeque sử dụng một mảng tròn. Khi mảng đầy, nó tự động mở rộng kích thước gấp đôi và sao chép dữ liệu từ mảng cũ sang mảng mới, đảm bảo hiệu suất cao khi chèn và xóa phần tử.