Trong bài này, chúng ta sẽ tìm hiểu về class ArrayDeque và các hàm của nó qua các ví dụ. Ngoài ra, chúng ta sẽ học cách sử dụng ArrayDeque để triển khai một stack.
Trong Java, chúng ta có thể sử dụng class ArrayDeque để triển khai các cấu trúc dữ liệu queue và deque bằng cách sử dụng các mảng.
Các interface được triển khai bởi ArrayDeque
Class ArrayDeque triển khai hai interface sau:
Nội dung chính
1. Tạo ArrayDeque
Để tạo một ArrayDeque, chúng ta phải nhập gói java.util.ArrayDeque.
Sau đây là cách chúng ta có thể tạo một ArrayDeque trong Java:
ArrayDeque<Type> animal = new ArrayDeque<>();Ở đây, Type là kiểu dữ liệu của ArrayDeque. Ví dụ,
// Creating String type ArrayDeque
ArrayDeque<String> animals = new ArrayDeque<>();
// Creating Integer type ArrayDeque
ArrayDeque<Integer> age = new ArrayDeque<>();
2. Các hàm của ArrayDeque
Class ArrayDeque triển khai cho tất cả các hàm có trong Queue interface và Deque interface.
3. Chèn các phần tử vào Deque
1. Thêm các phần tử bằng các hàm add(), addFirst() và addLast()
- add() – chèn phần tử được chỉ định vào cuối ArrayDeque
- addFirst() – chèn phần tử được chỉ định vào đầu ArrayDeque
- addLast()- chèn các phần tử được chỉ định vào cuối ArrayDeque (tương đương add())
Lưu ý: Nếu ArrayDeque đầy, tất cả các hàm add(), addFirst() và addLast() này sẽ ném một IllegalStateException.
Ví dụ,
/**
* Cafedev.vn - Kênh thông tin IT hàng đầu Việt Nam
*
* @author cafedevn
* Contact: cafedevn@gmail.com
* Fanpage: https://www.facebook.com/cafedevn
* Instagram: https://instagram.com/cafedevn
* Twitter: https://twitter.com/CafedeVn
* Linkedin: https://www.linkedin.com/in/cafe-dev-407054199/
*/
import java.util.ArrayDeque;
class Main {
public static void main(String[] args) {
ArrayDeque<String> animals= new ArrayDeque<>();
// Using add()
animals.add("Dog");
// Using addFirst()
animals.addFirst("Cat");
// Using addLast()
animals.addLast("Horse");
System.out.println("ArrayDeque: " + animals);
}
}
Kết quả
ArrayDeque: [Cat, Dog, Horse]2. Chèn các phần tử bằng cách sử dụng các hàm Offer (), OfferFirst () và OfferLast ()
- offer() – chèn phần tử được chỉ định vào cuối ArrayDeque
- offerFirst() – chèn phần tử được chỉ định vào đầu ArrayDeque
- offerLast() – chèn phần tử được chỉ định vào cuối ArrayDeque
Lưu ý: offer() , offerFirst()và offerLast() trả về true nếu phần tử được chèn thành công; nếu ArrayDeque đầy, các hàm này trả về false.
Ví dụ,
/**
* Cafedev.vn - Kênh thông tin IT hàng đầu Việt Nam
*
* @author cafedevn
* Contact: cafedevn@gmail.com
* Fanpage: https://www.facebook.com/cafedevn
* Instagram: https://instagram.com/cafedevn
* Twitter: https://twitter.com/CafedeVn
* Linkedin: https://www.linkedin.com/in/cafe-dev-407054199/
*/
import java.util.ArrayDeque;
class Main {
public static void main(String[] args) {
ArrayDeque<String> animals= new ArrayDeque<>();
// Using offer()
animals.offer("Dog");
// Using offerFirst()
animals.offerFirst("Cat");
// Using offerLast()
animals.offerLast("Horse");
System.out.println("ArrayDeque: " + animals);
}
}
Kết quả
ArrayDeque: [Cat, Dog, Horse]Lưu ý: Nếu ArrayDeque đầy
- hàm add() sẽ ném một ngoại lệ
- hàm offer() trả về false
4. Truy cập các phần tử trong ArrayDeque
1. Truy cập các phần tử bằng hàm getFirst () và getLast ()
- getFirst() – trả về phần tử đầu tiên của ArrayDeque
- getLast() – trả về phần tử cuối cùng của ArrayDeque
Lưu ý: Nếu ArrayDeque trống thì hàm getFirst() và getLast() ném một NoSuchElementException.
Ví dụ,
/**
* Cafedev.vn - Kênh thông tin IT hàng đầu Việt Nam
*
* @author cafedevn
* Contact: cafedevn@gmail.com
* Fanpage: https://www.facebook.com/cafedevn
* Instagram: https://instagram.com/cafedevn
* Twitter: https://twitter.com/CafedeVn
* Linkedin: https://www.linkedin.com/in/cafe-dev-407054199/
*/
import java.util.ArrayDeque;
class Main {
public static void main(String[] args) {
ArrayDeque<String> animals= new ArrayDeque<>();
animals.add("Dog");
animals.add("Cat");
animals.add("Horse");
System.out.println("ArrayDeque: " + animals);
// Get the first element
String firstElement = animals.getFirst();
System.out.println("First Element: " + firstElement);
// Get the last element
String lastElement = animals.getLast();
System.out.println("Last Element: " + lastElement);
}
}
Kết quả
ArrayDeque: [Dog, Cat, Horse]
First Element: Dog
Last Element: Horse2. Truy cập các phần tử bằng hàm peek (), peekFirst () và peekLast ()
- peek() – trả về phần tử đầu tiên của ArrayDeque
- peekFirst()- trả về phần tử đầu tiên của ArrayDeque (tương đương peek())
- peekLast() – trả về phần tử cuối cùng của ArrayDeque
Ví dụ,
/**
* Cafedev.vn - Kênh thông tin IT hàng đầu Việt Nam
*
* @author cafedevn
* Contact: cafedevn@gmail.com
* Fanpage: https://www.facebook.com/cafedevn
* Instagram: https://instagram.com/cafedevn
* Twitter: https://twitter.com/CafedeVn
* Linkedin: https://www.linkedin.com/in/cafe-dev-407054199/
*/
import java.util.ArrayDeque;
class Main {
public static void main(String[] args) {
ArrayDeque<String> animals= new ArrayDeque<>();
animals.add("Dog");
animals.add("Cat");
animals.add("Horse");
System.out.println("ArrayDeque: " + animals);
// Using peek()
String element = animals.peek();
System.out.println("Head Element: " + element);
// Using peekFirst()
String firstElement = animals.peekFirst();
System.out.println("First Element: " + firstElement);
// Using peekLast
String lastElement = animals.peekLast();
System.out.println("Last Element: " + lastElement);
}
}Kết quả
ArrayDeque: [Dog, Cat, Horse]
Head Element: Dog
First Element: Dog
Last Element: HorseLưu ý: Nếu ArrayDeque rỗng, các hàm peek(), peekFirst() và getLast() sẽ ném một NoSuchElementException.
5. Xóa các phần tử khỏi ArrayDeque
1. Xóa các phần tử bằng hàm remove (), removeFirst (), removeLast ()
- remove() – trả về và loại bỏ phần tử đầu tiên của ArrayDeque
- remove(element) – trả về và loại bỏ phần tử đã chỉ định khỏi phần đầu của ArrayDeque
- removeFirst()- trả về và loại bỏ phần tử đầu tiên khỏi ArrayDeque (tương đương với remove())
- removeLast() – trả về và loại bỏ phần tử cuối cùng khỏi ArrayDeque
Lưu ý: Nếu ArrayDeque rỗng, các hàm remove(), removeFirst() và removeLast() sẽ ném một ngoại lệ. Ngoài ra, hàm remove(element) sẽ ném một ngoại lệ nếu không tìm thấy phần tử.
Ví dụ,
/**
* Cafedev.vn - Kênh thông tin IT hàng đầu Việt Nam
*
* @author cafedevn
* Contact: cafedevn@gmail.com
* Fanpage: https://www.facebook.com/cafedevn
* Instagram: https://instagram.com/cafedevn
* Twitter: https://twitter.com/CafedeVn
* Linkedin: https://www.linkedin.com/in/cafe-dev-407054199/
*/
import java.util.ArrayDeque;
class Main {
public static void main(String[] args) {
ArrayDeque<String> animals= new ArrayDeque<>();
animals.add("Dog");
animals.add("Cat");
animals.add("Cow");
animals.add("Horse");
System.out.println("ArrayDeque: " + animals);
// Using remove()
String element = animals.remove();
System.out.println("Removed Element: " + element);
System.out.println("New ArrayDeque: " + animals);
// Using removeFirst()
String firstElement = animals.removeFirst();
System.out.println("Removed First Element: " + firstElement);
// Using removeLast()
String lastElement = animals.removeLast();
System.out.println("Removed Last Element: " + lastElement);
}
}
Kết quả
ArrayDeque: [Dog, Cat, Cow, Horse]
Removed Element: Dog
New ArrayDeque: [Cat, Cow, Horse]
Removed First Element: Cat
Removed Last Element: Horse2. Xóa các phần tử bằng hàm poll (), pollFirst () và pollLast ()
- poll() – trả về và loại bỏ phần tử đầu tiên của ArrayDeque
- pollFirst()- trả về và loại bỏ phần tử đầu tiên của ArrayDeque (tương đương poll())
- pollLast() – trả về và loại bỏ phần tử cuối cùng của ArrayDeque
Lưu ý: Nếu ArrayDeque rỗng, các hàm poll(), pollFirst() và pollLast() trả về nullnếu phần tử không được tìm thấy.
Ví dụ,
/**
* Cafedev.vn - Kênh thông tin IT hàng đầu Việt Nam
*
* @author cafedevn
* Contact: cafedevn@gmail.com
* Fanpage: https://www.facebook.com/cafedevn
* Instagram: https://instagram.com/cafedevn
* Twitter: https://twitter.com/CafedeVn
* Linkedin: https://www.linkedin.com/in/cafe-dev-407054199/
*/
import java.util.ArrayDeque;
class Main {
public static void main(String[] args) {
ArrayDeque<String> animals= new ArrayDeque<>();
animals.add("Dog");
animals.add("Cat");
animals.add("Cow");
animals.add("Horse");
System.out.println("ArrayDeque: " + animals);
// Using poll()
String element = animals.poll();
System.out.println("Removed Element: " + element);
System.out.println("New ArrayDeque: " + animals);
// Using pollFirst()
String firstElement = animals.pollFirst();
System.out.println("Removed First Element: " + firstElement);
// Using pollLast()
String lastElement = animals.pollLast();
System.out.println("Removed Last Element: " + lastElement);
}
}Kết quả
ArrayDeque: [Dog, Cat, Cow, Horse]
Removed Element: Dog
New ArrayDeque: [Cat, Cow, Horse]
Removed First Element: Cat
Removed Last Element: Horse
3. Xóa phần tử: sử dụng hàm clear ()
Để loại bỏ tất cả các phần tử khỏi ArrayDeque, chúng ta sử dụng hàm clear(). Ví dụ,
/**
* Cafedev.vn - Kênh thông tin IT hàng đầu Việt Nam
*
* @author cafedevn
* Contact: cafedevn@gmail.com
* Fanpage: https://www.facebook.com/cafedevn
* Instagram: https://instagram.com/cafedevn
* Twitter: https://twitter.com/CafedeVn
* Linkedin: https://www.linkedin.com/in/cafe-dev-407054199/
*/
import java.util.ArrayDeque;
class Main {
public static void main(String[] args) {
ArrayDeque<String> animals= new ArrayDeque<>();
animals.add("Dog");
animals.add("Cat");
animals.add("Horse");
System.out.println("ArrayDeque: " + animals);
// Using clear()
animals.clear();
System.out.println("New ArrayDeque: " + animals);
}
}
Kết quả
ArrayDeque: [Dog, Cat, Horse]
New ArrayDeque: []6. Lặp với ArrayDeque
- iterator() – trả về một iterator có thể được sử dụng để lặp qua ArrayDeque
- descendingIterator() – trả về một iterator có thể được sử dụng để lặp qua ArrayDeque theo thứ tự ngược lại
Để sử dụng các hàm này, chúng ta phải nhập gói java.util.Iterator. Ví dụ,
/**
* Cafedev.vn - Kênh thông tin IT hàng đầu Việt Nam
*
* @author cafedevn
* Contact: cafedevn@gmail.com
* Fanpage: https://www.facebook.com/cafedevn
* Instagram: https://instagram.com/cafedevn
* Twitter: https://twitter.com/CafedeVn
* Linkedin: https://www.linkedin.com/in/cafe-dev-407054199/
*/
import java.util.ArrayDeque;
import java.util.Iterator;
class Main {
public static void main(String[] args) {
ArrayDeque<String> animals= new ArrayDeque<>();
animals.add("Dog");
animals.add("Cat");
animals.add("Horse");
System.out.print("ArrayDeque: ");
// Using iterator()
Iterator<String> iterate = animals.iterator();
while(iterate.hasNext()) {
System.out.print(iterate.next());
System.out.print(", ");
}
System.out.print("\nArrayDeque in reverse order: ");
// Using descendingIterator()
Iterator<String> desIterate = animals.descendingIterator();
while(desIterate.hasNext()) {
System.out.print(desIterate.next());
System.out.print(", ");
}
}
}Kết quả
ArrayDeque: [Dog, Cat, Horse]
ArrayDeque in reverse order: [Horse, Cat, Dog]7. Các hàm khác
| Hàm | Mô tả |
| element() | Trả về một phần tử từ phần đầu của ArrayDeque. |
| contains(element) | Tìm kiếm phần tử được chỉ định trong ArrayDeque.Nếu phần tử được tìm thấy, nó trả về true, nếu không thì nó trả về false. |
| size() | Trả về chiều dài của ArrayDeque. |
| toArray() | Chuyển đổi ArrayDeque thành mảng và trả về nó. |
| clone() | Tạo một bản sao của ArrayDeque và trả về nó. |
8. ArrayDeque như một stack
Để triển khai stack LIFO (Last-In-First-Out) trong Java, nên sử dụng một deque thay vì sử dụng class Stack . Class ArrayDeque thường nhanh hơn so với class Stack.
ArrayDeque cung cấp các hàm sau có thể được sử dụng để triển khai stack.
- push() – thêm một phần tử vào đầu stack
- peek() – trả về một phần tử từ đầu stack
- pop() – trả về và xóa một phần tử ở đầu stack
Ví dụ,
import java.util.ArrayDeque;
class Main {
public static void main(String[] args) {
ArrayDeque<String> stack = new ArrayDeque<>();
// Add elements to stack
stack.push("Dog");
stack.push("Cat");
stack.push("Horse");
System.out.println("Stack: " + stack);
// Access element from top of stack
String element = stack.peek();
System.out.println("Accessed Element: " + element);
// Remove elements from top of stack
String remElement = stack.pop();
System.out.println("Removed element: " + remElement);
}
}
Kết quả
Stack: [Horse, Cat, Dog]
Accessed Element: Horse
Removed Element: Horse9. ArrayDeque Vs. Class LinkedList
Cả ArrayDeque và Class LinkedList trong Java đều triển khai Deque interface. Tuy nhiên, có một số điểm khác biệt giữa chúng.
- LinkedList hỗ trợ phần tử không, trong khi ArrayDeque thì không.
- Mỗi nút trong LinkedList bao gồm các liên kết đến các nút khác. Đó là lý do tại sao LinkedList cần nhiều dung lượng hơn ArrayDeque.
- Nếu bạn đang triển khai cấu trúc dữ liệu queue hoặc cấu trúc dữ liệu deque thì dùng ArrayDeque thường sẽ nhanh hơn a LinkedList.
