Giao diện hàng đợi Java và các triển khai của nó

Ở đâ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ụ.

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. Giao diện hàng đợi Java và các triển khai của nó - 1

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.

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

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".

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 đủ

Khi một luồng cố gắng lấy các mục từ một hàng đợi trống, nó sẽ đợi cho đến khi một số luồng khác đặt các mục đó vào hàng đợi. Tương tự, khi một luồng cố gắng đưa các phần tử vào một hàng đợi đầy đủ, nó sẽ đợi cho đến khi một số luồng khác lấy các phần tử ra khỏi hàng đợi để có không gian trống cho các phần tử. Chắc chắn, khái niệm "hàng đợi đầy đủ" ngụ ý rằng hàng đợi có kích thước giới hạn, kích thước này thường được chỉ định trong hàm tạo. Hàng đợi chặn tiêu chuẩn bao gồm LinkedBlockingQueue, SynchronousQueue và ArrayBlockingQueue. Triển khai các lớp giao diện BlockingQueue : ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedTransferQueue, PriorityBlockingQueue, SynchronousQueue. ChặnDequelà một giao diện con cho BlockingQueue. BlockingDeque chẳng hạn như BlockingQueue là hàng đợi chặn, nhưng hai chiều. Vì vậy, nó kế thừa các thuộc tính của giao diện Deque. Nó được định hướng để thực thi đa luồng, không cho phép các phần tử bằng không và dung lượng có thể bị hạn chế. Việc triển khai giao diện BlockingDeque chặn hoạt động lấy phần tử nếu hàng đợi trống và thêm phần tử vào hàng đợi nếu nó đầ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.

Các triển khai phổ biến nhất là LinkedList, ArrayBlockingQueue và PriorityQueue. Hãy xem xét chúng và làm một số ví dụ để hiểu rõ hơn.

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. Giao diện hàng đợi Java và các triển khai của nó - 2

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ử.

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)

Ví dụ về hàng đợi Java — LinkedList (đặt và xóa các phần tử theo các cách khác nhau)

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

Điều quan trọng là phải hiểu rằng hàng đợi ưu tiên dựa trên đống nhị phân, vì vậy chúng không giữ các phần tử theo thứ tự được sắp xếp tuyến tính. Mọi cách từ gốc đến lá đều được sắp xếp, nhưng các cách khác nhau từ gốc thì không. Điều đó có nghĩa là bạn có thể lấy phần tử tối thiểu của hàng đợi rất nhanh. Nếu bạn xóa phần đầu mỗi lần, bạn sẽ in một cấu trúc được sắp xếp.

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.

Ở đây chúng ta có ví dụ BlockingQueueExample. Chúng tôi tạo một hàng đợi của ArrayBlockingQueue với sức chứa một phần tử và cờ công bằng. Hai chủ đề được bắt đầu. Cái đầu tiên, chuỗi Producer, xếp hàng đợi các tin nhắn từ mảng tin nhắn bằng cách sử dụng phương thức put. Chuỗi thứ hai, Người tiêu dùng, đọc các phần tử từ hàng đợi bằng phương thức take và hiển thị chúng trong bảng điều khiển. Thứ tự của các phần tử là thứ tự nhiên cho 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();
       }
   }

Đầu ra là hàng đợi theo thứ tự tự nhiên; hai yếu tố đầu tiên xuất hiện với độ trễ. Để củng cố những gì bạn đã học, chúng tôi khuyên bạn nên xem một video bài học từ Khóa học Java của chúng tôi

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.