Queue - Hàng đợi
1. Giới thiệu
Queue (hàng đợi) là một Interface con của Collection, nó có đầy đủ các tính năng của Collection, nó khá giống với List, tuy nhiên mục đích sử dụng hơi khác nhau. Queue hoạt động theo cách thức FIFO (First In First Out - vào trước ra trước).
Trong FIFO, bạn chỉ có thể truy cập và loại bỏ phần tử ở đầu hàng đợi. Nó giống như hàng người xếp hàng ở siêu thị, chỉ người đứng đầu hàng đợi mới được phục vụ, người mới đến sẽ được chèn vào hàng đợi, vị trí được chèn vào có thể không phải là cuối hàng. Vị trí phần từ được chèn vào phụ thuộc vào loại hàng đợi và độ ưu tiên của phần tử.
Cấu trúc dữ liệu hàng đợi có nhiều ứng dụng: khử đệ quy, tổ chức lưu vết các quá trình tìm kiếm theo chiều rộng và quay lui, vét cạn, tổ chức quản lý và phân phối tiến trình trong các hệ điều hành, tổ chức bộ đệm bàn phím.
Cấu trúc dữ liệu hàng đợi còn có thể định nghĩa như sau: Hàng đợi là một cấu trúc dữ liệu trừu tượng (ADT) tuyến tính. Tương tự như ngăn xếp, hàng đợi hỗ trợ các thao tác:
- EnQueue(o): thêm đối tượng
ovào cuối hàng đợi. - DeQueue(): lấy đối tượng ở đầu queue ra khỏi hàng đợi và trả về giá trị của nó. Nếu hàng đợi rỗng thì lỗi sẽ xảy ra.
- IsEmpty(): kiểm tra xem hàng đợi có rỗng không.
- Front(): trả về giá trị của phần tử nằm ở đầu hàng đợi mà không hủy nó. Nếu hàng đợi rỗng thì lỗi sẽ xảy ra.
Các thao tác thêm, trích và huỷ một phần tử phải được thực hiện ở hai phía khác nhau của hàng đợi, dựa theo nguyên tắc FIFO. Cũng như ngăn xếp, cấu trúc mảng một chiều hoặc cấu trúc danh sách liên kết có thể dùng để biểu diễn cấu trúc hàng đợi.
Là một Interface, hàng đợi cần một lớp cụ thể để khai báo và các lớp phổ biến nhất là PriorityQueue và LinkedList trong Java. Cần lưu ý rằng cả hai cách triển khai đều không an toàn cho luồng. Và PriorityBlockingQueue là một triển khai thay thế nếu cần triển khai an toàn luồng.
2. Tạo đối tượng hàng đợi
Vì Queue là một Interface, không thể tạo các đối tượng thuộc loại Queue. Chúng ta luôn cần một lớp mở rộng danh sách này để tạo một đối tượng. Ngoài ra, sau khi giới thiệu Generics trong Java 1.5, có thể hạn chế loại đối tượng có thể được lưu trữ trong Queue. Queue an toàn kiểu này có thể được định nghĩa là:
1
Queue<Obj> queue = new PriorityQueue<Obj> ();
Code demo:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.LinkedList;
import java.util.Queue;
public class QueueDemo {
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
// Thêm các phần tử {0, 1, 2, 3, 4} vào Queue
for (int i = 0; i < 5; i++)
q.add(i);
// In nội dung của Queue
System.out.println("Elements of queue: " + q);
// Xoá phần tử đầu tiên của Queue
int removedele = q.remove();
System.out.println("Removed element: " + removedele);
System.out.println(q);
// Xem phần tử đầu tiên của Queue
int head = q.peek();
System.out.println("Head of queue: " + head);
// Kích thước của Queue
int size = q.size();
System.out.println("Size of queue: " + size);
}
}
3. Làm việc với Queue Interface
Adding Elements: Để thêm một phần tử trong hàng đợi, chúng ta có thể sử dụng phương thức add(). Thứ tự chèn không được giữ lại trong PriorityQueue. Các phần tử được lưu trữ dựa trên thứ tự ưu tiên tăng dần theo mặc định.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.PriorityQueue;
import java.util.Queue;
public class QueueAdd {
public static void main(String args[]) {
Queue<String> pq = new PriorityQueue<>();
// Thêm các phần tử vào Queue
pq.add("Tom");
pq.add("And");
pq.add("Jerry");
// In Queue
System.out.println(pq);
}
}
Removing Elements: Để loại bỏ một phần tử khỏi hàng đợi, chúng ta có thể sử dụng phương thức remove(). Nếu có nhiều đối tượng như vậy, thì lần xuất hiện đầu tiên của đối tượng sẽ bị loại bỏ. Ngoài ra, phương thức poll() cũng được sử dụng để loại bỏ phần đầu và về phần tử đó.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.PriorityQueue;
import java.util.Queue;
public class QueueRemove {
public static void main(String args[]) {
Queue<String> pq = new PriorityQueue<>();
// Thêm các phần tử vào Queue
pq.add("Tom");
pq.add("And");
pq.add("Jerry");
// In Queue
System.out.println(pq);
// Remove "Tom"
pq.remove("Tom");
System.out.println("After Remove " + pq);
System.out.println("Poll Method " + pq.poll());
System.out.println("Final Queue " + pq);
}
}
Iterating the Queue: Có nhiều cách để lặp lại hàng đợi. Cách nổi tiếng nhất là chuyển đổi hàng đợi thành mảng và duyệt qua bằng vòng lặp FOR. Tuy nhiên, hàng đợi cũng có một trình vòng lặp có sẵn có thể được sử dụng để lặp lại qua hàng đợi.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Queue;
public class QueueIterator {
public static void main(String args[]) {
Queue<String> pq = new PriorityQueue<>();
// Thêm các phần tử vào Queue
pq.add("Tom");
pq.add("And");
pq.add("Jerry");
Iterator iterator = pq.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
}
}
Đặc điểm của hàng đợi:
- Queue được sử dụng để chèn các phần tử vào cuối hàng đợi và xóa khỏi đầu hàng đợi. Nó tuân theo khái niệm FIFO.
- Hàng đợi Java hỗ trợ tất cả các phương thức của Collection interface bao gồm chèn, xóa, v.v.
- LinkedList, ArrayBlockingQueue và PriorityQueue là những triển khai được sử dụng thường xuyên nhất.
- Nếu bất kỳ thao tác rỗng nào được thực hiện trên BlockingQueues, NullPointerException sẽ được ném ra.
- Hàng đợi có sẵn trong gói java.util là Hàng đợi không giới hạn.
- Hàng đợi có sẵn trong gói java.util.concurrent là Hàng đợi bị ràng buộc.
- Tất cả Hàng đợi ngoại trừ Deques hỗ trợ chèn và loại bỏ ở phần đuôi và phần đầu của hàng đợi tương ứng. Deques hỗ trợ chèn và loại bỏ phần tử ở cả hai đầu.
PriorityQueue: Lớp PriorityQueue được triển khai trong collection framework cung cấp cho chúng ta một cách để xử lý các đối tượng dựa trên mức độ ưu tiên. Người ta biết rằng một hàng đợi tuân theo thuật toán First-In-First-Out, nhưng đôi khi các phần tử của hàng đợi cần được xử lý theo mức độ ưu tiên, đó là khi PriorityQueue hoạt động. Hãy xem cách tạo đối tượng hàng đợi bằng lớp này.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Queue;
public class PriorityQueue {
public static void main(String args[]) {
// Tạo một priority queue rỗng
Queue<Integer> pQueue = new PriorityQueue<Integer>();
// Thêm các phần tử
pQueue.add(10);
pQueue.add(20);
pQueue.add(15);
// In các phần tử của PriorityQueue
System.out.println(pQueue.peek());
// In các phần tử ở TOP và xoá nó
System.out.println(pQueue.poll());
// In lại phần tử ở TOP
System.out.println(pQueue.peek());
}
}
LinkedList: là một lớp được triển khai trong collection framework vốn đã triển khai cấu trúc dữ liệu danh sách liên kết. Nó là một cấu trúc dữ liệu tuyến tính trong đó các phần tử không được lưu trữ ở các vị trí liền kề và mỗi phần tử là một đối tượng riêng biệt gồm phần dữ liệu và phần địa chỉ. Các phần tử được liên kết bằng cách sử dụng con trỏ và địa chỉ. Mỗi phần tử được gọi là một nút. Do tính năng động và dễ dàng chèn và xóa, chúng được ưu tiên hơn các mảng hoặc hàng đợi. Hãy xem cách tạo đối tượng hàng đợi bằng lớp này.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class LinkedList {
public static void main(String args[]) {
// Tạo rỗng một LinkedList
Queue<Integer> ll = new LinkedList<Integer>();
// Thêm các phần tử
ll.add(10);
ll.add(20);
ll.add(15);
// In các phần tử TOP của LinkedList
System.out.println(ll.peek());
// In và xoá phần tử TOP của LinkedList
System.out.println(ll.poll());
// In lại phần tử TOP
System.out.println(ll.peek());
}
}
PriorityBlockingQueue: Cần lưu ý rằng cả PriorityQueue và LinkedList đều không an toàn cho luồng. PriorityBlockingQueue là một triển khai thay thế nếu cần triển khai an toàn luồng. PriorityBlockingQueue là hàng đợi chặn không giới hạn sử dụng các quy tắc sắp xếp giống như lớp PriorityQueue và các hoạt động truy xuất chặn nguồn cung cấp.
Vì nó không bị ràng buộc nên việc thêm các phần tử đôi khi có thể không thành công do tài nguyên cạn kiệt dẫn đến OutOfMemoryError. Hãy xem cách tạo đối tượng hàng đợi bằng lớp này.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.Queue;
public class PriorityBlockingQueue {
public static void main(String args[]) {
// Tạo một PriorityBlockingQueue rỗng
Queue<Integer> pbq = new PriorityBlockingQueue<Integer>();
// Thêm các phần tử
pbq.add(10);
pbq.add(20);
pbq.add(15);
// In phần tử tại TOP của PriorityBlockingQueue
System.out.println(pbq.peek());
// In và xoá phần tử tại TOP của PriorityBlockingQueue
System.out.println(pbq.poll());
// In lại phần tử tại TOP
System.out.println(pbq.peek());
}
}
Phương thức nâng cao trong Queue Interface
Queue Interface kế thừa tất cả các phương thức có trong collections interface trong khi triển khai các phương thức sau:
- add(element): Phương thức này được sử dụng để thêm các phần tử vào cuối hàng đợi. Cụ thể hơn, ở cuối danh sách liên kết nếu nó được sử dụng, hoặc theo mức độ ưu tiên trong trường hợp triển khai hàng đợi ưu tiên.
Trong đó tham số bắt buộc e là phần tử được chèn vào cuối Queue. Phương thức này trả về true khi chèn thành công.
Hàm này ném bốn ngoại lệ được mô tả như sau:
- ClassCastException: khi lớp của phần tử được nhập ngăn nó được thêm vào container.
- IllegalStateException: khi dung lượng của container đầy và việc chèn được thực hiện.
- IllegalArgumentException: khi một số thuộc tính của phần tử ngăn nó được thêm vào Queue
- NullPointerException: khi phần tử được chèn được chuyển dưới dạng null và interface của Queue không cho phép phần tử rỗng.
Dùng Linked List:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.*;
public class PhuongThucAdd {
public static void main(String[] args) throws IllegalStateException {
Queue<Integer> Q = new LinkedList<Integer>();
Q.add(7855642);
Q.add(35658786);
Q.add(5278367);
Q.add(74381793);
System.out.println("Queue: " + Q);
}
}
Dùng ArrayDeque:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.*;
public class PhuongThucAdd {
public static void main(String[] args) throws IllegalStateException {
Queue<Integer> Q = new ArrayDeque<Integer>();
Q.add(7855642);
Q.add(35658786);
Q.add(5278367);
Q.add(74381793);
System.out.println("Queue: " + Q);
}
}
Dùng LinkedBlockingDeque:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.*;
public class PhuongThucAdd {
public static void main(String[] args) throws IllegalStateException {
Queue<Integer> Q = new LinkedBlockingDeque<Integer>();
Q.add(7855642);
Q.add(35658786);
Q.add(5278367);
Q.add(74381793);
System.out.println("Queue: " + Q);
}
}
Dùng ConcurrentLinkedDeque:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.*;
public class PhuongThucAdd {
public static void main(String[] args) throws IllegalStateException {
Queue<Integer> Q = new ConcurrentLinkedDeque<Integer>();
Q.add(7855642);
Q.add(35658786);
Q.add(5278367);
Q.add(74381793);
System.out.println("Queue: " + Q);
}
}
element(): Phương thức này tương tự như peek(). Nó ném NoSuchElementException khi hàng đợi trống.
(code tương tự như phương thức
add()bên trên, chỉ thêm dòng bên dưới là được)
1
System.out.println("Queue's head: " + Q.element());
offer(element): Phương thức này được sử dụng để chèn một phần tử vào hàng đợi. Phương thức này thích hợp hơn phương thức add() vì phương thức này không ném ra ngoại lệ khi dung lượng của vùng chứa đầy vì nó trả về false. Tuy nhiên, phương thức này ít thấy các lập trình viên sử dụng, nếu bạn muốn tìm hiểu về nó có thể tự nghiên cứu thêm – vì nó khá đơn giản (tương tự như phương thức add).
peek(): Phương thức này được sử dụng để xem phần đầu của hàng đợi mà không cần loại bỏ nó. Nó trả về Null nếu hàng đợi trống.
(code tương tự như phương thức
add()bên trên, chỉ thêm dòng bên dưới là được)
1
System.out.println("Queue's head: " + Q.peek());
poll(): Phương thức này loại bỏ và trả về phần đầu của hàng đợi. Nó trả về null nếu hàng đợi trống. Phương thức này loại bỏ và trả về phần đầu của hàng đợi. Nó trả về null nếu hàng đợi trống.
(code tương tự như phương thức
add()bên trên, chỉ thêm dòng bên dưới là được)
1
System.out.println("Queue's head: " + Q.poll());
remove(): Phương thức này loại bỏ và trả về phần đầu của hàng đợi. Nó ném NoSuchElementException khi hàng đợi trống.
(code tương tự như phương thức
add()bên trên, chỉ thêm dòng bên dưới là được)
1
System.out.println("Queue's head: " + Q.remove());
Như vậy, cấu trúc dữ liệu hàng đợi đã được chia sẽ một cách chi tiết và cẩn thận, bạn có thể dựa vào đó để nghiên cứu và áp dụng cho thực tiễn của riêng mình. So với các cấu trúc dữ liệu trước đó, hàng đợi có ưu thế nổi bậc nhưng không phải lúc nào cũng là điểm mạnh. Là người lập trình chuyên nghiệp, bạn cần cân nhắc lựa chọn sử dụng sao cho tối ưu.
Bài viết mang tính chất “ghi chú, lưu trữ, chia sẻ và phi lợi nhuận”.
Nếu bạn thấy hữu ích, đừng quên chia sẻ với bạn bè và đồng nghiệp của mình nhé!
Happy coding! 😎 👍🏻 🚀 🔥