Interface Deque<E>

Deque (double-ended queue) là một tập hợp tuyến tính cho phép chèn và xóa phần tử từ cả hai đầu của nó. Tên deque là viết tắt của "double-ended queue" và thường được phát âm là "deck". Hầu hết các triển khai của Deque không đặt giới hạn cố định về số lượng phần tử mà chúng có thể chứa, nhưng interface này hỗ trợ cả Deque có giới hạn dung lượng và Deque không có giới hạn kích thước cố định.

Đặc điểm nổi bật của Interface Deque<E>

Chèn và xóa từ Cả hai đầu: Interface Deque định nghĩa các phương thức để truy cập các phần tử ở cả hai đầu của deque. Các phương thức này cho phép bạn chèn, xóa và kiểm tra các phần tử. Mỗi phương thức có 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 còn lại trả về giá trị đặc biệt (hoặc null hoặc false, tùy thuộc vào thao tác). Dạng thứ hai của thao tác chèn được thiết kế đặc biệt cho các triển khai Deque có giới hạn dung lượng; trong hầu hết các triển khai, thao tác chèn không thể thất bại.

Phương thức chính của Interface Deque<E>

↳ Chèn phần tử: addFirst(e) / offerFirst(e) (thêm vào đầu), addLast(e) / offerLast(e) (thêm vào cuối).

↳ Xóa phần tử: removeFirst() / pollFirst() (xóa từ đầu), removeLast() / pollLast() (xóa từ cuối).

↳ Truy cập phần tử: getFirst() / peekFirst() (xem đầu), getLast() / peekLast() (xem cuối).

So sánh với Queue và Stack

↳ Queue: Khi Deque được sử dụng như một hàng đợi (queue), hành vi FIFO (First-In-First-Out) được thực hiện. Phần tử được thêm vào cuối deque và xóa từ đầu. Các phương thức từ Queue được kế thừa tương đương với các phương thức của Deque như sau:

↳ Stack: Khi Deque được sử dụng như một ngăn xếp (stack), hành vi LIFO (Last-In-First-Out) được thực hiện. Các phương thức của Stack tương đương với các phương thức của Deque như sau:

Các phương thức bổ sung

↳ Xóa phần tử bên trong: removeFirstOccurrence và removeLastOccurrence cho phép bạn xóa phần tử đầu tiên hoặc cuối cùng xuất hiện trong deque.

↳ Truy cập theo chỉ số: Khác với interface List, Deque không hỗ trợ truy cập theo chỉ số các phần tử.

Lưu ý

↳ Phần tử null: Mặc dù các triển khai Deque không bắt buộc phải cấm chèn phần tử null, nhưng khuyến khích không nên sử dụng phần tử null vì nó có thể được dùng như một giá trị trả về đặc biệt để chỉ ra rằng deque là rỗng.

↳ Phương thức equals và hashCode: Các triển khai Deque thường không định nghĩa các phiên bản dựa trên phần tử của equals và hashCode, mà thay vào đó kế thừa các phiên bản dựa trên danh tính từ lớp Object.

Khai báo Interface Deque<E> trong Java

Để sử dụng Interface Deque<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 trong Java.

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

import java.util.Queue;

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

public interface Deque<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: Là phạm vi truy cập. Interface Deque được khai báo là public nên có thể được sử dụng ở bất kỳ đâu trong chương trình.

↳ interface: Đây là một interface, nghĩa là nó chỉ chứa các phương thức trừu tượng (abstract methods) hoặc phương thức mặc định (default methods).

↳ Deque<E>: Tên interface là Deque và sử dụng generic E, đại diện cho kiểu phần tử chứa trong hàng đợi hai đầu (deque).

↳ extends Collection<E>: Interface Deque kế thừa từ Collection<E>, nghĩa là nó là một loại Collection đặc biệt và kế thừa toàn bộ phương thức của Collection.

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

↳ Hỗ trợ hai đầu: Deque (Double-ended Queue) hỗ trợ việc thêm và loại bỏ phần tử từ cả hai đầu của cấu trúc dữ liệu, tức là cả từ đầu (front) và cuối (end). Điều này khác với Queue, nơi chỉ hỗ trợ thao tác từ một đầu (thường là cuối) khi thêm phần tử và từ đầu khi loại bỏ phần tử.

↳ Chèn và loại bỏ: Bạn có thể sử dụng các phương thức như addFirst(E e), removeFirst(), addLast(E e), và removeLast() để thực hiện các thao tác ở đầu và cuối của deque.

↳ Truy cập và kiểm tra: Deque cũng cung cấp các phương thức để kiểm tra các phần tử ở đầu và cuối như getFirst(), peekFirst(), getLast(), và peekLast().

↳ Tính chất của Deque: Deque có thể hoạt động như một hàng đợi (queue) theo quy tắc FIFO (First-In-First-Out) hoặc như một ngăn xếp (stack) theo quy tắc LIFO (Last-In-First-Out), tùy vào cách bạn sử dụng nó.

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

Giao diện Deque cung cấp các phương thức linh hoạt để thêm, lấy và xóa phần tử từ đầu hoặc cuối của deque. Nó có thể được sử dụng như một hàng đợi, một stack hoặc một cấu trúc dữ liệu kết hợp cả hai. Dưới đây là danh sách tất cả các phương thức của Interface Deque<E> trong Java:

↳ add(E e), offer(E e): Thêm phần tử vào cuối deque (tail).

↳ addFirst(E e), offerFirst(E e): Thêm phần tử vào đầu deque (head).

↳ addLast(E e), offerLast(E e): Thêm phần tử vào cuối deque (tail).

↳ contains(Object o): Kiểm tra xem deque có chứa phần tử o hay không.

↳ descendingIterator(): Trả về một iterator duyệt qua các phần tử theo thứ tự ngược.

↳ element(), getFirst(), getLast(): Lấy phần tử đầu hoặc cuối của deque mà không xóa nó.

↳ iterator(): Trả về một iterator duyệt qua các phần tử theo thứ tự đúng.

↳ peek(): Lấy phần tử đầu của deque mà không xóa nó.

↳ peekFirst(), peekLast(): Lấy phần tử đầu hoặc cuối của deque mà không xóa nó.

↳ poll(), pollFirst(), pollLast(): Lấy và xóa phần tử đầu hoặc cuối của deque.

↳ pop(), push(): Thực hiện các thao tác tương tự như stack (đống).

↳ remove(): Xóa phần tử đầu của deque.

↳ remove(Object o): Xóa phần tử đầu tiên xuất hiện của o khỏi deque.

↳ removeFirst(), removeFirstOccurrence(Object o): Xóa phần tử đầu tiên xuất hiện của o khỏi deque.

↳ removeLast(), removeLastOccurrence(Object o): Xóa phần tử cuối cùng xuất hiện của o khỏi deque.

↳ size(): Trả về số lượng phần tử trong deque.

Sự khác biệt giữa các phương thức

↳ peek và poll: Các phương thức peek lấy phần tử mà không xóa nó, trong khi các phương thức poll lấy và xóa phần tử.

↳ First và Last: Các phương thức First và Last chỉ định vị trí đầu hoặc cuối của deque.

↳ pop và push: Các phương thức này được sử dụng khi deque được xem như một stack. pop lấy phần tử đầu (đỉnh của stack), push thêm phần tử vào đầu (đáy của stack).

Sự khác biệt giữa Deque và Queue

Dưới đây là bảng so sánh giữa Deque<E> và Queue<E>:

Như vậy, qua bảng so sánh, bạn đã thấy rõ sự khác biệt cốt lõi giữa Deque<E> và Queue<E>. Trong khi Queue tuân thủ nghiêm ngặt nguyên tắc FIFO (First-In-First-Out), hoạt động như một hàng đợi truyền thống (thêm vào cuối, lấy ra từ đầu), thì Deque linh hoạt hơn rất nhiều.

Deque mang đến khả năng thêm và xóa phần tử từ cả hai đầu (đầu và cuối), biến nó thành một cấu trúc dữ liệu đa năng có thể hoạt động như cả một hàng đợi thông thường và một ngăn xếp (Stack - LIFO). Việc lựa chọn giữa Queue và Deque phụ thuộc vào nhu cầu cụ thể của bài toán: dùng Queue khi bạn cần xử lý tuần tự, và Deque khi bạn cần sự linh hoạt hơn trong việc thêm/xóa phần tử ở cả hai phía.