Deque và ArrayDeque trong Java

1. Deque Interface

1.1. Giới thiệu

Java Deque Interface là một collection mà nó hỗ trợ thêm và loại bỏ phần tử ở cả hai đầu. Deque là từ viết tắt của double ended queue.

Deque Interface cung cấp các phương thức cần thiết để bạn có thể chèn, truy xuất và loại bỏ các phần tử khỏi cả hai đầu.

Lớp java.util.Dequeue được định nghĩa như sau:

public interface Deque<E> extends Queue<E>

1.2. Các phương thức của Dequeue Interface

Ưu điểm chính của Deque là bạn có thể sử dụng nó như là cả Queue (FIFO) cũng như Stack (LIFO). Deque Interface có tất cả các phương thức cần thiết cho hoạt động FIFO và LIFO. Một số trong những phương thức này đưa ra một ngoại lệ nếu không thể thực hiện được và một số phương thức trả về một giá trị cụ thể (null hoặc false) nếu thao tác thất bại. Bên dưới là danh sách các phương pháp Deque:

1.3. Sử dụng Deque như Queue

Deque Intefac kế thừa (extend) Queue Interface, nó thừa hưởng tất cả các phương thức của Queue Interface. Vì vậy, bạn có thể sử dụng tất cả những phương thức thừa kế để thực hiện các hoạt động Queue. Ngoài ra, các phương thức được định nghĩa trong Deque Interface cũng có thể được sử dụng cho các hoạt động Queue. Dưới đây là danh sách các phương thức Queue và phương pháp Deque tương đương của chúng:

1.4. Sử dụng Deque như Stack

Deque Interface có thêm hai phương thức là pop() và push(). Hai phương thức này làm cho Deque hoạt động như một ngăn xếp (Last-In-First-Out). Ngoài ra, bạn cũng có thể sử dụng addFirst(), peekFirst() và removeFirst() cho các hoạt động ngăn xếp. Dưới đây là danh sách các phương thức Stack và các phương thức tương đương của Deque:

Thao tácStackDeque
Thêmpush()addFirst()
Truy xuấtpeek()peekFirst()
Truy xuất và xóa bỏpop()removeFirst()

1.5. Các đặc điểm của Dequeue

  • Không giống như Queue, Deque có thể có các phần tử null. Tuy nhiên, không nên chèn các phần tử null vì nhiều phương thức trả về null để cho biết Deque là rỗng.
  • Deque có thể có các phần tử trùng lặp.
  • Không thể đặt hoặc truy xuất hoặc chèn các phần tử ở vị trí bất kỳ của Deque. Tức là không thể truy cập ngẫu nhiên (Random access) với Deque.
  • Có thể sử dụng các phương thức removeFirstOccurrenec (E e), removeLastOccurrence (E e) và remove (E e) để xóa các phần tử khỏi Deque.
  • Các lớp cài đặt Dequeue Interface là LinkedList và ArrayDeque.

2. Lớp ArrayDeque

2.1. Đặc điểm

Những điểm quan trọng về lớp ArrayDeque là:

  • Lớp ArrayDeque mở rộng lớp AbstractCollection và cài đặt Deque Interface.
  • Không giống như Queue, Dequeue có thể thêm hoặc xóa các phần tử từ cả hai đầu.
  • ArrayDeque là cài đặt một mảng có thể thay đổi kích thước, Deque Interface tương tự như lớp ArrayList là một cài đặt List Interface có thể điều chỉnh lại kích thước. Tuy nhiên, ArrayDeque không phải là List.
  • ArrayDeque không có giới hạn dung lượng (compacity). Nó sẽ phát triển tự động khi chúng ta thêm các phần tử.
  • Dung lượng ban đầu mặc định của ArrayDeque là 16. Nó sẽ tự tăng dung lượng với số mũ của 2 khi kích thước vượt quá dung lượng.
  • ArrayDeque không phải là thread an toàn.
  • ArrayDeque có thể được sử dụng như một ngăn xếp (Stack – LIFO) cũng như một hàng đợi (Queue – FIFO). ArrayDeque nhanh hơn lớp Stack khi được sử dụng như một ngăn xếp (Stack) và nhanh hơn lớp LinkedList khi được sử dụng như một hàng đợi (Queue).
  • Hiệu suất của ArrayDeque đôi khi được coi là tốt nhất trong Collection Framework. Nó cho phép thực hiện O(1) để chèn, loại bỏ và truy xuất. Lớp ArrayDeque được đề nghị thay vì lớp Stack (khi bạn muốn cấu trúc ngăn xếp dữ liệu) và thay vì lớp LinkedList (khi bạn muốn cấu trúc dữ liệu hàng đợi).
  • Không thể thực hiện các thao tác liên quan đến index (random access) trên ArrayDeque. ArrayDeque không có phương thức để hỗ trợ các thao tác đó.
  • Các phần tử Null không được phép trong ArrayDeque.

2.2. Phân cấp ArrayDeque

Lớp java.util.ArrayDeque được định nghĩa như sau:

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable {
 
}

3. Ví dụ minh họa sử dụng ArrayDeque

3.1. Ví dụ sử dụng ArrayDeque như Collection

package com.maixuanviet.collection.queue;
 
import java.util.ArrayDeque;
import java.util.Deque;
 
public class ArrayDequeExample3 {
    public static void main(String[] args) {
        // Creating Deque and adding elements
        Deque<String> deque = new ArrayDeque<String>();
        deque.add("Basic");
        deque.add("OOP");
        deque.add("Collection");
        // Traversing elements
        for (String str : deque) {
            System.out.println(str);
        }
    }
}

Kết quả thực thi chương trình trên:

Basic
OOP
Collection<span data-mce-type="bookmark" style="display: inline-block; width: 0px; overflow: hidden; line-height: 0;" class="mce_SELRES_start"></span>

3.2. Ví dụ sử dụng ArrayDeque như Queue

package com.maixuanviet.collection.queue;
 
import java.util.ArrayDeque;
import java.util.Deque;
 
public class ArrayDequeExample {
    public static void main(String[] args) {
        // Creating an array deque
        Deque<String> arrayDeque = new ArrayDeque<String>();
 
        // Adding elements at the tail of arrayDeque
        arrayDeque.offer("One");
        arrayDeque.offer("Two");
        arrayDeque.offer("Three");
        arrayDeque.offer("Four");
        arrayDeque.offer("Five");
 
        // Printing the elements of arrayDeque
        System.out.println(arrayDeque); // Output : [One, Two, Three, Four, Five]
 
        // Removing the elements from the head of arrayDeque
        System.out.println(arrayDeque.poll()); // Output : One
        System.out.println(arrayDeque.poll()); // Output : Two
    }
}

Kết quả thực thi chương trình trên:

[One, Two, Three, Four, Five]
One
Two

3.3. Ví dụ sử dụng ArrayDeque như Stack

package com.maixuanviet.collection.queue;
import java.util.ArrayDeque;
import java.util.Deque;
 
public class ArrayDequeExample2 {
    public static void main(String[] args) {
        // Creating an array deque
        Deque<String> arrayDeque = new ArrayDeque<String>();
 
        // pushing elements into arrayDeque
        arrayDeque.push("One");
        arrayDeque.push("Two");
        arrayDeque.push("Three");
        arrayDeque.push("Four");
        arrayDeque.push("Five");
 
        // Printing the elements of arrayDeque
        System.out.println(arrayDeque); // Output : [Five, Four, Three, Two, One]
 
        // popping up the elements from arrayDeque
        System.out.println(arrayDeque.pop()); // Output : Five
        System.out.println(arrayDeque.pop()); // Output : Four
    }
}

Kết quả thực thi chương trình trên:

[Five, Four, Three, Two, One]
Five
Four

Related posts:

Java Program to Implement Weight Balanced Tree
String Operations with Java Streams
Stack Memory and Heap Space in Java
Introduction to Spring Data JPA
Java Program to Solve Travelling Salesman Problem for Unweighted Graph
Java Program to Perform Partition of an Integer in All Possible Ways
Java Program to Apply Above-Below-on Test to Find the Position of a Point with respect to a Line
Guide to the Java Queue Interface
Different Ways to Capture Java Heap Dumps
Java Program to Check Cycle in a Graph using Graph traversal
Java Program to Implement Quick Hull Algorithm to Find Convex Hull
Java InputStream to Byte Array and ByteBuffer
OAuth2.0 and Dynamic Client Registration
Spring Cloud – Bootstrapping
Comparing getPath(), getAbsolutePath(), and getCanonicalPath() in Java
Using JWT with Spring Security OAuth
Java Program to implement Bit Matrix
How to Return 404 with Spring WebFlux
Custom Error Pages with Spring MVC
Java Program to Solve a Matching Problem for a Given Specific Case
Java Program to Implement LinkedHashSet API
Java Program to Implement a Binary Search Algorithm for a Specific Search Sequence
Spring REST API + OAuth2 + Angular
Java Program to Generate a Random Subset by Coin Flipping
Hướng dẫn Java Design Pattern – Iterator
Ways to Iterate Over a List in Java
How to Change the Default Port in Spring Boot
Getting Started with Custom Deserialization in Jackson
Introduction to Spring Method Security
Java String Conversions
Guava – Join and Split Collections
Spring Boot Configuration with Jasypt