Ở đây chúng ta sẽ thảo luận về giao diện Hàng đợi Java. Bạn sẽ tìm hiểu cấu trúc dữ liệu Hàng đợi là gì, nó được thể hiện như thế nào trong Java, phương thức nào là quan trọng nhất đối với tất cả các hàng đợi. Ngoài ra, những triển khai của Hàng đợi bằng ngôn ngữ Java. Sau đó, chúng ta xem xét kỹ hơn các triển khai quan trọng nhất và tìm hiểu chúng bằng các ví dụ.
![Giao diện hàng đợi Java và các triển khai của nó - 1]()
Vì vậy, trong khi làm việc với hàng đợi, các phần tử mới được thêm vào cuối và nếu bạn muốn lấy phần tử nào thì phần tử đó sẽ được lấy từ đầu. Đây là nguyên tắc chính của công việc cấu trúc dữ liệu hàng đợi cổ điển.
Nó có nghĩa là gì? Trước hết, Hàng đợi Java là một phần của Khung Bộ sưu tập và triển khai giao diện Bộ sưu tập. Vì vậy, nó hỗ trợ tất cả các phương thức của giao diện Bộ sưu tập như chèn, xóa, v.v. Hàng đợi triển khai giao diện Iterable, cho phép một đối tượng trở thành mục tiêu của câu lệnh "cho mỗi vòng lặp".
![Giao diện hàng đợi Java và các triển khai của nó - 2]()
Bạn có thể nói rằng LinkedList không hiệu quả lắm về mặt sử dụng bộ nhớ. Điều đó đúng, nhưng cấu trúc dữ liệu này có thể hữu ích trong trường hợp thực hiện thao tác chèn và xóa. Tuy nhiên, điều đó chỉ xảy ra nếu bạn sử dụng trình vòng lặp cho chúng (trong trường hợp này, nó xảy ra trong thời gian không đổi). Hoạt động truy cập theo chỉ mục được thực hiện bằng cách tìm kiếm từ đầu đến cuối (tùy theo cái nào gần hơn) đến phần tử mong muốn. Tuy nhiên, đừng quên chi phí bổ sung để lưu trữ các tham chiếu giữa các phần tử. Vì vậy, LinkedList là triển khai hàng đợi phổ biến nhất trong Java. Nó cũng là một triển khai của List và Deque và nó cho phép chúng ta tạo một hàng đợi hai chiều bao gồm bất kỳ đối tượng nào kể cả null. LinkedList là một tập hợp các phần tử.
Cấu trúc dữ liệu hàng đợi
Hàng đợi là một cấu trúc dữ liệu trừu tượng tuyến tính với thứ tự thực hiện các hoạt động cụ thể - Nhập trước xuất trước (FIFO). Điều đó có nghĩa là bạn chỉ có thể thêm một phần tử (hoặc enqueue, đưa vào hàng đợi) ở cuối cấu trúc và chỉ lấy một phần tử (xếp hàng hoặc xóa khỏi hàng đợi) ngay từ đầu. Bạn có thể hình dung cấu trúc dữ liệu Queue rất dễ dàng. Nó có vẻ giống như một hàng đợi hoặc một dòng khách hàng trong cuộc sống thực. Khách hàng đến trước cũng sẽ được phục vụ trước. Nếu bạn có bốn người xếp hàng ở McDonalds hoặc những nơi khác, thì người đầu tiên xếp hàng sẽ là người đầu tiên vào cửa hàng. Nếu khách hàng mới đến, anh ấy/cô ấy sẽ là người xếp hàng thứ 5 để lấy hamburger.
Vì vậy, trong khi làm việc với hàng đợi, các phần tử mới được thêm vào cuối và nếu bạn muốn lấy phần tử nào thì phần tử đó sẽ được lấy từ đầu. Đây là nguyên tắc chính của công việc cấu trúc dữ liệu hàng đợi cổ điển.
Hàng đợi trong Java
Hàng đợi trong Java là một giao diện. Theo tài liệu của Oracle, giao diện Hàng đợi có 2 siêu giao diện, 4 giao diện khác nhau kế thừa từ hàng đợi và một danh sách các lớp cực kỳ ấn tượng.|
Siêu giao diện: Bộ sưu tập<E>, Có thể lặp lại<E> Tất cả các giao diện con đã biết: BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E> Tất cả các lớp triển khai đã biết: AbstractQueue, ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue, PriorityBlockingQueue, PriorityQueue, SynchronousQueue |
Phương thức xếp hàng Java
Queue khai báo một số phương thức. Là các phương thức của giao diện, chúng nên được biểu diễn trong tất cả các lớp triển khai Hàng đợi. Các Phương thức xếp hàng quan trọng nhất, Java:- Boolean offer() – chèn một phần tử mới vào hàng đợi nếu có thể
- Boolean add(E e) – chèn một phần tử mới vào hàng đợi nếu có thể. Trả về true trong trường hợp thành công và ném IllegalStateException nếu không có khoảng trống.
- Thăm dò đối tượng () – lấy và xóa một phần tử khỏi phần đầu của đối tượng. Trả về null nếu hàng đợi trống.
- Loại bỏ đối tượng () – lấy và loại bỏ một phần tử khỏi phần đầu của hàng đợi.
- Đối tượng peek() – truy xuất, nhưng không xóa phần tử khỏi đầu hàng đợi. Trả về null nếu hàng đợi trống.
- Phần tử đối tượng() – truy xuất, nhưng không xóa phần tử khỏi đầu hàng đợi.
Giao diện con của hàng đợi Java
Giao diện hàng đợi được kế thừa bởi 4 giao diện con – BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E> . Bạn có thể chia chúng thành 3 nhóm: Deques, Blocking Queues và Transfer Queues với BlockingDeque thuộc 2 nhóm đầu tiên. Chúng ta hãy xem qua các nhóm này.Deques
Deque có nghĩa là D ouble- E nded Q ueue và hỗ trợ thêm hoặc loại bỏ từ một trong hai phần đuôi của dữ liệu dưới dạng hàng đợi (vào trước ra trước/FIFO) hoặc từ phần đầu dưới dạng một cấu trúc dữ liệu phổ biến khác được gọi là ngăn xếp ( vào cuối xuất trước/LIFO). Các lớp triển khai Giao diện Deque: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList.Chặn hàng đợi
Hàng đợi chặn là hàng đợi chặn một luồng trong hai trường hợp:- chủ đề đang cố lấy các phần tử từ một hàng đợi trống
- chủ đề đang cố gắng đưa các phần tử vào hàng đợi đầy đủ
chuyển hàng đợi
Giao diện TransferQueue mở rộng giao diện BlockingQueue. Tuy nhiên, không giống như việc triển khai hàng đợi giao diện BlockingQueue, trong đó các luồng có thể bị chặn nếu hàng đợi trống (đọc) hoặc nếu hàng đợi đầy (ghi), hàng đợi giao diện TransferQueue chặn luồng ghi cho đến khi luồng khác truy xuất phần tử. Sử dụng một phương pháp chuyển giao cho việc này. Nói cách khác, việc triển khai BlockingQueue đảm bảo rằng phần tử do Nhà sản xuất tạo phải nằm trong hàng đợi, trong khi việc triển khai TransferQueue đảm bảo rằng phần tử Nhà sản xuất được Người tiêu dùng "nhận". Chỉ có một triển khai Java chính thức của giao diện TransferQueue — LinkedTransferQueue.Triển khai hàng đợi Java
Có nhiều lớp triển khai giao diện Hàng đợi:- AbstractQueue theo tài liệu Queue Java 8, lớp trừu tượng này cung cấp các triển khai cơ bản của một số thao tác Hàng đợi. Nó không cho phép các phần tử null. Có thêm 3 phương thức add, remove và element dựa trên Queue classic offer , poll và peek tương ứng. Tuy nhiên, họ đưa ra các ngoại lệ thay vì chỉ ra lỗi thông qua trả về sai hoặc null.
- ArrayBlockingQueue — hàng đợi chặn FIFO có kích thước cố định được hỗ trợ bởi một mảng
- ArrayDeque - triển khai mảng có thể thay đổi kích thước của giao diện Deque
- ConcurrentLinkedDeque — deque đồng thời không giới hạn dựa trên các nút được liên kết.
- ConcurrentLinkedQueue — một hàng đợi an toàn cho luồng không giới hạn dựa trên các nút được liên kết.
- DelayQueue - hàng đợi lập lịch dựa trên thời gian được hỗ trợ bởi một đống
- LinkedBlockingDeque — triển khai đồng thời giao diện Deque.
- LinkedBlockingQueue — hàng đợi chặn FIFO được giới hạn tùy chọn được hỗ trợ bởi các nút được liên kết
- LinkedList — triển khai danh sách liên kết đôi của giao diện List và Deque. Thực hiện tất cả các hoạt động danh sách tùy chọn và cho phép tất cả các phần tử (bao gồm cả null)
- LinkedTransferQueue — một TransferQueue không giới hạn dựa trên các nút được liên kết
- PriorityBlockingQueue — hàng đợi ưu tiên chặn không giới hạn được hỗ trợ bởi một đống
- PriorityQueue — hàng đợi ưu tiên dựa trên cấu trúc dữ liệu heap
- SynchronousQueue — hàng đợi chặn trong đó mỗi thao tác chèn phải chờ thao tác xóa tương ứng bởi một luồng khác và ngược lại.
LinkedList
Lớp LinkedList trong Java triển khai các giao diện List và Deque. Vì vậy, nó là sự kết hợp của List và Deque, một hàng đợi hai chiều, hỗ trợ thêm và xóa các phần tử từ cả hai phía. Trong Java LinkedList là Danh sách được liên kết kép: mọi phần tử của Danh sách gọi Nút và chứa một đối tượng và tham chiếu đến hai đối tượng lân cận - đối tượng trước và đối tượng tiếp theo.
Bạn có thể nói rằng LinkedList không hiệu quả lắm về mặt sử dụng bộ nhớ. Điều đó đúng, nhưng cấu trúc dữ liệu này có thể hữu ích trong trường hợp thực hiện thao tác chèn và xóa. Tuy nhiên, điều đó chỉ xảy ra nếu bạn sử dụng trình vòng lặp cho chúng (trong trường hợp này, nó xảy ra trong thời gian không đổi). Hoạt động truy cập theo chỉ mục được thực hiện bằng cách tìm kiếm từ đầu đến cuối (tùy theo cái nào gần hơn) đến phần tử mong muốn. Tuy nhiên, đừng quên chi phí bổ sung để lưu trữ các tham chiếu giữa các phần tử. Vì vậy, LinkedList là triển khai hàng đợi phổ biến nhất trong Java. Nó cũng là một triển khai của List và Deque và nó cho phép chúng ta tạo một hàng đợi hai chiều bao gồm bất kỳ đối tượng nào kể cả null. LinkedList là một tập hợp các phần tử.
| Tìm hiểu thêm về LinkedList: Cấu trúc dữ liệu Java của LinkedList |
LinkedList Constructor
LinkedList() không có tham số được sử dụng để tạo danh sách trống. LinkedList(Collection<? extends E> c) dùng để tạo danh sách chứa các phần tử của bộ sưu tập đã chỉ định, theo thứ tự, chúng được trả về bởi bộ lặp của bộ sưu tập.Các phương thức LinkedList chính:
- add(E element) Nối phần tử đã chỉ định vào cuối danh sách này;
- add(int index, E element) Chèn phần tử vào chỉ số vị trí xác định;
- get(int index) Trả về phần tử ở vị trí xác định trong danh sách này;
- remove(int index) Loại bỏ phần tử ở vị trí chỉ mục;
- remove(Object o) Loại bỏ sự xuất hiện đầu tiên của phần tử ?o khỏi danh sách này nếu nó ở đó.
- remove() Lấy và loại bỏ phần tử đầu tiên của danh sách.
- addFirst(), addLast() thêm phần tử vào đầu/cuối danh sách
- clear() xóa tất cả các phần tử khỏi danh sách
- chứa(Đối tượng o) trả về true nếu danh sách chứa phần tử o.
- indexOf(Object o) trả về chỉ mục của lần xuất hiện đầu tiên của phần tử o hoặc -1 nếu nó không có trong danh sách.
- set(int index, E element) thay thế phần tử ở vị trí chỉ mục bằng phần tử
- size() Trả về số lượng phần tử trong danh sách.
- toArray() trả về một mảng chứa tất cả các phần tử của danh sách từ phần tử đầu tiên đến phần tử cuối cùng.
- pop() bật một phần tử từ ngăn xếp (được biểu thị bằng danh sách)
- push(E e) đẩy một phần tử vào ngăn xếp (được biểu thị bằng danh sách này)
import java.util.*;
public class LinkedListTest {
public static void main(String args[]){
LinkedList<Integer> myLinkedList= new LinkedList<Integer>();
myLinkedList.add(1);
myLinkedList.add(2);
myLinkedList.add(4);
System.out.println("three added elements: " + myLinkedList);
//put one element into the head, not to the tail:
myLinkedList.push(5);
System.out.println("The new element last in will be the first: " + myLinkedList);
//add new element at the specified position:
myLinkedList.add(4,3);
//put one element into the head, not to the tail (same as push):
myLinkedList.addFirst(6);
System.out.println(myLinkedList);
//now remove element no 2 (it is 1):
myLinkedList.remove(2);
System.out.println(myLinkedList);
//now remove the head of the list
myLinkedList.pop();
System.out.println(myLinkedList);
//remove with the other method
myLinkedList.remove();
System.out.println(myLinkedList);
//and with one more
myLinkedList.poll();
System.out.println(myLinkedList);
}
}
Hàng đợi ưu tiên
PriorityQueue không chính xác là hàng đợi theo nghĩa chung của FIFO. Các phần tử của hàng đợi ưu tiên được sắp xếp theo thứ tự tự nhiên của chúng hoặc theo Bộ so sánh được cung cấp tại thời điểm xây dựng hàng đợi, tùy thuộc vào hàm tạo nào được sử dụng. Tuy nhiên, nó không phải là một thứ tự giống như nó có thể ở cấu trúc tuyến tính, chẳng hạn như danh sách (từ lớn nhất đến nhỏ nhất hoặc ngược lại). Một hàng đợi ưu tiên dựa trên một đống tối thiểu ưu tiên. Heap là một cấu trúc dữ liệu dựa trên cây nhị phân. Ưu tiên của mỗi bậc cha mẹ lớn hơn ưu tiên của con cái. Một cây được gọi là nhị phân đầy đủ nếu mỗi cha mẹ có không quá hai con và việc lấp đầy các cấp đi từ trên xuống dưới (từ cùng một cấp - từ trái sang phải). Heap nhị phân tự tổ chức lại mỗi khi một phần tử mới được thêm vào hoặc xóa khỏi nó. Trong trường hợp min-heap, phần tử nhỏ nhất sẽ chuyển đến thư mục gốc bất kể thứ tự chèn của nó. Hàng đợi ưu tiên dựa trên đống nhỏ này, vì vậy nếu chúng ta có một PriorityQueue gồm các số nguyên, thì phần tử đầu tiên của nó sẽ là phần tử nhỏ nhất trong số này. Nếu bạn xóa gốc, phần nhỏ nhất tiếp theo sẽ trở thành gốc.Các phương thức PriorityQueue chính:
- boolean add(object) chèn phần tử đã chỉ định vào hàng đợi ưu tiên. Trả về true trong trường hợp thành công. Nếu hàng đợi đầy, phương thức sẽ đưa ra một ngoại lệ.
- boolean offer(object) chèn phần tử đã chỉ định vào hàng đợi ưu tiên này. Nếu hàng đợi đầy, phương thức trả về false.
- boolean remove(object) xóa một phiên bản duy nhất của phần tử đã chỉ định khỏi hàng đợi này, nếu nó hiện diện.
- Object poll() truy xuất và loại bỏ phần đầu của hàng đợi này. Trả về null nếu hàng đợi trống.
- void clear() xóa tất cả các phần tử khỏi hàng đợi ưu tiên.
- Phần tử đối tượng() truy xuất phần đầu của hàng đợi này mà không xóa nó. Ném NoSuchElementException nếu hàng đợi trống.
- Đối tượng peek() truy xuất phần đầu của hàng đợi mà không xóa nó. Trả về null nếu hàng đợi trống.
- boolean contains(Object o) trả về true nếu hàng đợi chứa phần tử o.
- int size() trả về số phần tử trong hàng đợi này.
Ví dụ về PriorityQueue
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
public class PriorityQueueExample {
public static void main(String[] args) {
Queue<Integer> queueL = new LinkedList<>();
for (int i = 5; i > 0; i--) {
queueL.add(i);
}
System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
Queue<Integer> priorityQueue = new PriorityQueue<>();
for (int i = 5; i > 0; i--) {
priorityQueue.offer(i);
}
System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
System.out.println("Print PriorityQueue using poll() (by retrieval): " );
while (!priorityQueue.isEmpty()) {
System.out.println(priorityQueue.poll());
}
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our PriorityQueue using poll() (by retrieval):
1
2
3
4
5
MảngChặnHàng đợi
Cấu trúc dữ liệu bên trong của ArrayBlockingQueuedựa trên một mảng tròn để lưu trữ các phần tử. Đó là một hàng đợi điển hình (FIFO) trong trường hợp các phần tử mới được chèn vào cuối hàng đợi và các hoạt động trích xuất trả về một phần tử từ phần đầu của hàng đợi. Không thể thay đổi dung lượng hàng đợi sau khi đã tạo. Nỗ lực chèn (đặt) một phần tử vào hàng đợi đầy đủ dẫn đến chặn luồng; cố gắng lấy một phần tử từ hàng đợi trống cũng chặn luồng. Như chúng tôi đã nói trước đây, mảng này là hình tròn. Điều đó có nghĩa là phần tử đầu tiên và phần tử cuối cùng của mảng được xử lý liền kề một cách hợp lý. Hàng đợi tăng chỉ số của phần tử đầu và đuôi mỗi khi bạn đặt phần tử vào hàng đợi hoặc xóa nó khỏi hàng đợi. Nếu một số chỉ mục tăng phần tử cuối cùng của mảng, nó sẽ bắt đầu lại từ 0. Do đó, hàng đợi không phải dịch chuyển tất cả các phần tử trong trường hợp loại bỏ phần đầu (như trong mảng thông thường). Tuy nhiên, trong trường hợp loại bỏ một phần tử ở giữa (dùng Iterator.remove) thì các phần tử đó sẽ bị dịch chuyển. ArrayBlockingQueue hỗ trợ một chính sách công bằng bổ sung với tham số fair trong hàm tạo để sắp xếp công việc của các luồng đang chờ của nhà sản xuất (chèn phần tử) và người tiêu dùng (trích xuất phần tử). Theo mặc định, thứ tự không được đảm bảo. Tuy nhiên, nếu hàng đợi được tạo bằng "fair == true", thì việc triển khai lớp ArrayBlockingQueue sẽ cung cấp quyền truy cập luồng theo thứ tự FIFO. Vốn chủ sở hữu thường làm giảm băng thông, nhưng cũng làm giảm sự biến động và tránh cạn kiệt tài nguyên.Trình xây dựng lớp ArrayBlockingQueue
- ArrayBlockingQueue(int capacity) tạo hàng đợi có dung lượng cố định và với chính sách truy cập mặc định.
- ArrayBlockingQueue(int capacity, boolean fair) tạo một hàng đợi có dung lượng cố định và chính sách truy cập được chỉ định.
- ArrayBlockingQueue(int capacity, boolean fair, Collection <? extends E> c) tạo một hàng đợi có dung lượng cố định được chỉ định bởi chính sách truy cập và bao gồm các phần tử trong hàng đợi.
import java.util.concurrent.*;
public class ArrayBlockingQueueExample {
private BlockingQueue<Integer> blockingQueue;
private final Integer[] myArray = {1,2,3,4,5};
public ArrayBlockingQueueExample ()
{ blockingQueue = new ArrayBlockingQueue<Integer>(1, true);
(new Thread(new Producer())).start();
(new Thread(new Consumer())).start();
}
class Producer implements Runnable
{
public void run() {
try {
int counter = 0;
for (int i=0; i < myArray.length; i++) {
blockingQueue.put(myArray[i]);
if (counter++ < 2)
Thread.sleep(3000);
} blockingQueue.put(-1);
}
catch (InterruptedException e) {
System.err.println(e.getMessage());
}
}
}
class Consumer implements Runnable
{
public void run() {
try {
Integer message = 0;
while (!((message = blockingQueue.take()).equals(-1)))
System.out.println(message);
} catch (InterruptedException e) {
System.err.println(e.getMessage());
}
}
}
public static void main(String[] args) {
new ArrayBlockingQueueExample();
}
}
kết luận
- Queue được sử dụng để chèn các phần tử vào cuối hàng đợi và loại bỏ khỏi đầu hàng đợi. Nó tuân theo khái niệm FIFO.
- Hàng đợi Java là một phần của Khung Bộ sưu tập và triển khai giao diện Bộ sưu tập. Vì vậy, nó hỗ trợ tất cả các phương thức của giao diện Bộ sưu tập như chèn, xóa, v.v.
- Các triển khai Hàng đợi được sử dụng thường xuyên nhất là LinkedList, ArrayBlockingQueue và PriorityQueue.
- Các phần tử của hàng đợi ưu tiên được sắp xếp theo thứ tự tự nhiên của chúng hoặc theo Bộ so sánh được cung cấp tại thời điểm xây dựng hàng đợi, tùy thuộc vào hàm tạo nào được sử dụng.
- Nếu bất kỳ thao tác null nào được thực hiện trên BlockingQueues, thì NullPulumException sẽ bị ném.
GO TO FULL VERSION