Mục lục
Hướng dẫn và ví dụ Java Deque
Xem thêm các chuyên mục:
Nhóm phát triển của chúng tôi vừa ra mắt website
langlearning.net
học tiếng
Anh,
Nga,
Đức,
Pháp,
Việt,
Trung,
Hàn,
Nhật,
...
miễn phí cho tất cả mọi người.Là một website được viết trên công nghệ web Flutter vì vậy hỗ trợ rất tốt cho người học, kể cả những người học khó tính nhất.
Hiện tại website đang tiếp tục được cập nhập nội dung cho phong phú và đầy đủ hơn. Mong các bạn nghé thăm và ủng hộ website mới của chúng tôi.
Hãy theo dõi chúng tôi trên Fanpage để nhận được thông báo mỗi khi có bài viết mới.
Facebook
Deque là một từ viết tắt của "Double Ended Queue" (Hàng đợi hai đầu). Giống như những người đang xếp hàng tại siêu thị, chỉ người đứng đầu tiên và đứng ở vị cuối cùng được phục vụ. Deque cung cấp sự linh hoạt hơn một chút so với một hàng đợi thông thường.
public interface Deque<E> extends Queue<E>
Deque là interface con của Queue, nó cung cấp các phương thức để chèn một phần tử vào đầu hoặc cuối, và các phương thức để truy cập hoặc loại bỏ phần tử đầu hoặc phần tử cuối của nó.
Deque cũng bao gồm các phương thức cho phép nó hoạt động như một stack (Ngăn xếp) (Xem thêm giải thích trong bài viết).
Methods of Deque
void addFirst(E e);
void addLast(E e);
boolean offerFirst(E e);
boolean offerLast(E e);
E removeFirst();
E removeLast();
E pollFirst();
E pollLast();
E getFirst();
E getLast();
E peekFirst();
E peekLast();
void push(E e);
E pop();
boolean removeFirstOccurrence(Object o);
boolean removeLastOccurrence(Object o);
Iterator<E> descendingIterator();
// Methods inherited from Queue:
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
// Methods inherited from Collection:
boolean addAll(Collection<? extends E> c);
boolean remove(Object o);
boolean contains(Object o);
int size();
Iterator<E> iterator();
...
Danh sách 12 phương thức đặc trưng của Deque:
| First Element (Head) | Last Element (Tail) | |||
|---|---|---|---|---|
| Throws exception | Special value | Throws exception | Special value | |
| Insert | addFirst(E) | offerFirst(E) | addLast(E) | offerLast(E) |
| Remove | removeFirst() | pollFirst() | removeLast() | pollLast() |
| Examine | getFirst() | peekFirst() | getLast() | peekLast() |
boolean addFirst(E) / boolean offerFirst(E)
| boolean addFirst(E) | Chèn một phần tử vào phía trước của Deque, phương thức này sẽ ném ra ngoại lệ nếu sức chứa của Deque đã đầy. Phương thức trả về true nếu việc chèn thành công. |
| boolean offerFirst(E) | Chèn một phần tử vào phía trước của Deque. Nếu sức chứa của Deque đã đầy hoặc việc chèn không thì thành công phương thức sẽ trả về false, ngược lại trả về true. |
Chú ý: Tuỳ thuộc vào kiểu Deque, nó có thể giới hạn (hoặc không giới hạn) số lượng phần tử.
boolean addLast(E) / boolean offerLast(E)
| boolean addLast(E) | Chèn một phần tử vào phía cuối của Deque, phương thức này sẽ ném ra ngoại lệ nếu sức chứa của Deque đã đầy. Phương thức trả về true nếu việc chèn thành công. |
| boolean offerLast(E) | Chèn một phần tử vào phía cuối của Deque. Nếu sức chứa của Deque đã đầy hoặc việc chèn không thì thành công phương thức sẽ trả về false, ngược lại trả về true. |
E removeFirst() / E pollFirst()
| E removeFirst() | Trả về phần tử đầu tiên của Deque đồng thời loại bỏ nó ra khỏi Deque. Phương thức này sẽ ném ra ngoại lệ nếu Deque không có phần tử nào. |
| E pollFirst() | Trả về phần tử đầu tiên của Deque đồng thời loại bỏ nó ra khỏi Deque. Phương thức này sẽ trả về null nếu Deque không có phần tử nào. |
E removeLast() / E pollLast()
| E removeLast() | Trả về phần tử cuối cùng của Deque đồng thời loại bỏ nó ra khỏi Deque. Phương thức này sẽ ném ra ngoại lệ nếu Deque không có phần tử nào. |
| E pollLast() | Trả về phần tử cuối cùng của Deque đồng thời loại bỏ nó ra khỏi Deque. Phương thức này sẽ trả về null nếu Deque không có phần tử nào. |
E getFirst() / E peekFirst()
| E getFirst() | Trả về phần tử đầu tiên của Deque nhưng không loại bỏ nó ra ra khỏi Deque. Phương thức này ném ra ngoại lệ nếu Deque không có phần tử nào. |
| E peekFirst() | Trả về phần tử đầu tiên của Deque nhưng không loại bỏ nó ra ra khỏi Deque. Phương thức này trả về null nếu Deque không có phần tử nào. |
E getLast() / E peekLast()
| E getLast() | Trả về phần tử cuối cùng của Deque nhưng không loại bỏ nó ra ra khỏi Deque. Phương thức này ném ra ngoại lệ nếu Deque không có phần tử nào. |
| E peekLast() | Trả về phần tử cuối cùng của Deque nhưng không loại bỏ nó ra ra khỏi Deque. Phương thức này trả về null nếu Deque không có phần tử nào. |
Methods inherited from Queue:
Các phương thức thừa kế từ Queue và các phương thức tương ứng trong Deque:
| Queue Method | Equivalent Deque Method | Note |
|---|---|---|
| boolean add(E) | boolean addLast(E) | (*) |
| boolean offer(E) | boolean offerLast(E) | |
| E remove() | E removeFirst() | |
| E poll() | E pollFirst() | |
| E element() | E getFirst() | |
| E peek() | E peekFirst() |
(*) - Trong hầu hết các kiểu Queue, 2 phương thức add(E) và offer(E) sẽ chèn phần tử vào cuối. Nhưng điều này không đúng với PriorityQueue, vì PriorityQueue chỉ định vị trí của phần tử được chèn vào dựa trên độ ưu tiên của phần tử.
Stack?
Deque có thể hoạt động như một stack (Ngăn xếp), vì nó cung cấp các phương thức để hoạt động theo cơ chế LIFO (Last In First Out) (Phần tử thêm vào lần cuối sẽ được lấy ra đầu tiên).
| Stack Method | Equivalent Deque Method |
|---|---|
| boolean push(e) | boolean addFirst(e) |
| E pop() | E removeFirst() |
| E peek() | E getFirst() |
Deque là một interface vì vậy để tạo ra đối tượng Deque bạn phải sử dụng một trong các lớp con của nó, chẳng hạn ArrayDeque, ConcurrentLinkedDeque, LinkedList, LinkedBlockingDeque.
Deque<String> deque = new ArrayDeque<>();
Deque<String> deque = new LinkedList<>();
Lớp Customer sẽ tham gia vào các ví dụ:
Customer.java
package com.o7planning.deque.ex;
public class Customer {
private Integer cusId;
private String cusName;
public Customer(Integer cusId, String cusName) {
super();
this.cusId = cusId;
this.cusName = cusName;
}
public Integer getCusId() {
return cusId;
}
public String getCusName() {
return cusName;
}
}
DequeEx1.java
package com.o7planning.deque.ex;
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeEx1 {
public static void main(String[] args) {
// Create a Deque with maximum capacity of 10 elements.
Deque<Customer> deque = new ArrayDeque<Customer>(10);
deque.addFirst(new Customer(1, "Tom"));
deque.addFirst(new Customer(2, "Jerry"));
deque.addLast(new Customer(3, "Donald"));
Customer current = null;
// Retrieve first element and remove it from Deque.
while((current = deque.pollFirst())!= null) {
System.out.println("Serving customer: " + current.getCusName());
}
}
}
Output:
Serving customer: Jerry
Serving customer: Tom
Serving customer: Donald
Deque có thể được sử dụng như một stack (ngăn xếp), hãy xem một ví dụ mô phỏng các lá bài (cards):
DequeStackEx1.java
package com.o7planning.deque.ex;
import java.util.Deque;
import java.util.LinkedList;
public class DequeStackEx1 {
public static void main(String[] args) {
// Create a Deque to use as a Stack.
Deque<String> stackOfCards = new LinkedList<>();
// Pushing new items to the Stack
stackOfCards.push("Jack");
stackOfCards.push("Queen");
stackOfCards.push("King");
stackOfCards.push("Ace");
System.out.println("Stack => " + stackOfCards);
System.out.println();
// Popping items from the Stack
String cardAtTop = stackOfCards.pop(); // Throws NoSuchElementException if the stack is empty
System.out.println("Stack.pop() => " + cardAtTop);
System.out.println("Current Stack => " + stackOfCards);
System.out.println();
// Get the item at the top of the stack without removing it
cardAtTop = stackOfCards.peek();
System.out.println("Stack.peek() => " + cardAtTop);
System.out.println("Current Stack => " + stackOfCards);
}
}
Output:
Stack => [Ace, King, Queen, Jack]
Stack.pop() => Ace
Current Stack => [King, Queen, Jack]
Stack.peek() => King
Current Stack => [King, Queen, Jack]
