Deque và ArrayDeque trong Java

Deque Interface

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>

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:

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:

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:

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.

Lớp ArrayDeque

Đặ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.

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 {

}

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

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

package com.gpcoder.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>

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

package com.gpcoder.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

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

package com.gpcoder.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

Chuyên mục: Collection Được gắn thẻ: Collection

Bình luận

bình luận