Table of Contents
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). Trong FIFO, bạn chỉ có thể truy cập phần tử ở đầu hàng đợi, và khi loại bỏ phần tử nó loại phần tử đứng đầ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 trèn vào hàng đợi, vị trí được trèn vào có thể không phải là cuối hàng. Vị trí phần từ được trèn vào phụ thuộc vào loại hàng đợi và độ ưu tiên của phần tử.
Đặc điểm:
- Là tập hợp cho phép các phần tử trùng lặp.
- Không cho phép phần tử null.
Có hai class cài đặt (implement) interface Queue:
- java.util.LinkedList
- java.util.PriorityQueue
2. LinkedList
LinkedList là một hàng đợi khá chuẩn. Nhưng nhớ rằng LinkedList thi hành cả 2 interface List và Queue.
Chú ý rằng, một class có thể thi hành cả 2 interface List và Queue, chính vì vậy bạn không cần quan tâm tới các phần tử sắp xếp thế nào trong nội bộ của đối tượng class trên, nếu bạn coi nó như một hàng đợi thì hãy sử dụng cách thức truy cập vào phần tử của hàng đợi.
3. PriorityQueue
PriorityQueue lưu trữ các phần tử trong nội bộ theo trật tự tự nhiên của các phần tử (nếu các phần tử này là kiểu Comparable), hoặc theo một Comparator (bộ so sánh) được cung cấp cho PriorityQueue.
Các lớp String và Wrapper có bộ so sánh mặc định bên trong nó.
3.1. Các phương thức đặc trưng của Queue
| Thao tác | Ném ra ngoại lệ | Trả về giá trị cụ thể |
| Thêm một phần tử vào hàng đợi | add(e) | offer(e) |
| Truy xuất một phần tử từ đầu hàng đợi | remove() | poll() |
| Lấy và Xóa một phần tử khỏi đầu hàng đợi | element() | peek() |
3.2. boolean add(E)
Thêm một phần tử vào hàng đợi nếu có thể làm điều này ngay lập tức mà không bị giới hạn bởi kích thước hàng đợi, trả về true nếu thành công, ngược lại nó sẽ ném ra ngoại lệ IllegalStateException khi hàng đợi không còn chỗ.
3.3. boolean offer(E)
Thêm phần tử vào hàng đợi nếu có thể làm điều đó ngay lập tức nếu không bị giới hạn bởi kích thước hàng đợi. Khi sử dụng hàng đợi có kích thước giới hạn, phương thức này khá giống với add(E), tuy nhiên phương thức này không ném ra ngoại lệ khi không trèn được phần tử vào hàng đợi, mà nó trả về false trong tình huống đó.
3.4. E remove()
Lấy ra và loại bỏ luôn phần tử đầu tiên của hàng đợi. Phương thức này chỉ khác với poll() ở chỗ nếu hàng đợi không có phần tử ngoại lệ sẽ bị ném ra.
3.5. E poll()
Lấy ra và loại bỏ phần tử đầu tiên trong hàng đợi, hoặc trả về null nếu hàng đợi không có phần tử nào.
3.6. E element()
Lấy ra nhưng không loại bỏ phần tử đứng đầu của hàng đợi. Phương thức này chỉ khác với peek() là nó ném ra ngoại lệ nếu hàng đợi không có phần tử.
3.7. E peek()
Lấy ra, nhưng không loại bỏ phần tử đầu tiên trong hàng đợi, hoặc trả về null nếu hàng đợi không có phần tử nào.
3.8. Nhận xét
Các phương thức hàng đợi ở trên không có phương thức nào cho phép bạn truy cập các phần tử khác trong hàng đợi ngoài phần tử đầu tiên, bạn cũng không thể chỉ định vị trí phần tử sẽ được trèn vào.
4. Ví dụ minh họa
4.1. Ví dụ sử dụng Queue với LinkedList
package com.maixuanviet.collection.queue;
import java.util.LinkedList;
import java.util.Queue;
public class QueueLinkedListDemo {
public static void main(String[] args) {
// Khởi tạo hàng đợi LinkedList
Queue<String> names = new LinkedList<String>();
// offer(E): Thêm phần tử vào hàng đợi (queue).
// Với hàng đợi LinkedList phần tử sẽ được thêm vào cuối hàng đợi.
// Trả về true nếu trèn thành công.
// Trả về false nếu hàng đợi không còn chỗ.
names.offer("E");
names.offer("A");
names.offer("M");
// add(E): Thêm phần tử vào hàng đợi.
// Với hàng đợi LinkedList phần tử sẽ thêm vào cuối hàng đợi.
// Trả về true nếu thêm thành công
// Ném ra ngoại lệ nếu hàng đợi không còn chỗ.
names.add("G");
names.add("B");
while (true) {
// Lấy ra và loại bỏ phần tử đầu tiên ra khỏi hàng đợi.
// Trả về null nếu không còn phần tử nào trong hàng đợi.
String name = names.poll();
if (name == null) {
break;
}
System.out.println("Name=" + name);
}
}
}
Kết quả thực thi chương trình trên:
Name=E Name=A Name=M Name=G Name=B
4.2. Ví dụ sử dụng hàng đợi có ưu tiên PriorityQueue với kiểu dữ liệu cơ bản (Wrapper)
Hàng đợi PriorityQueue lưu trữ các phần tử trong nội bộ theo trật tự tự nhiên của phần tử (nếu các phần tử đó so sánh được với nhau – thi hành Comparable) hoặc một bộ so sánh Comparator được cung cấp cho PriorityQueue.
String là một class thi hành interface Comparable, chúng có thể so sánh được với nhau, và sắp xếp theo thứ tự alphabet (A-Z).
package com.maixuanviet.collection.queue;
import java.util.PriorityQueue;
import java.util.Queue;
public class PriorityQueueDemo {
public static void main(String[] args) {
// Với hàng đợi (queue) PriorityQueue phần tử sẽ được sắp xếp vị trí
// theo trật tự tự nhiên của chúng.
Queue<String> names = new PriorityQueue<String>();
// offer(E): Thêm phần tử vào hàng đợi (queue).
// Trả về true nếu thêm thành công.
// Trả về false nếu hàng đợi không còn chỗ.
names.offer("E");
names.offer("A");
names.offer("M");
// add(E): Thêm một phần tử vào hàng đợi (queue).
// Trả về true nếu thành công.
// Ném ra một Exception nếu hàng đợi đã đầy.
names.add("G");
names.add("B");
while (true) {
// poll(): Lấy ra và loại bỏ phần tử đầu tiên ra khỏi hàng đợi.
// Trả về null nếu không còn phần tử nào trong hàng đợi.
String name = names.poll();
if (name == null) {
break;
}
System.out.println("Name=" + name);
}
}
}
Kết quả thực thi chương trình trên:
Name=A Name=B Name=E Name=G Name=M
4.3. Ví dụ sử dụng hàng đợi có ưu tiên PriorityQueue với kiểu do người dùng tự định nghĩa (Object)
Để sử dụng PriorityQueue với kiểu do người dùng tự định nghĩa, bạn cần phải cài đặt interface Comparable hoặc Comparator và cung cấp nó cho PriorityQueue.
package com.maixuanviet.collection.queue;
import java.util.PriorityQueue;
import java.util.Queue;
class Book implements Comparable<Book> {
private int id;
private String name, author, publisher;
private int quantity;
public Book(int id, String name, String author, String publisher, int quantity) {
this.id = id;
this.name = name;
this.author = author;
this.publisher = publisher;
this.quantity = quantity;
}
@Override
public int compareTo(Book b) {
if (this.id > b.id) {
return 1;
} else if (this.id < b.id) {
return -1;
} else {
return 0;
}
}
@Override
public String toString() {
return "Book [id=" + id + ", name=" + name + ", author=" + author
+ ", publisher=" + publisher + ", quantity=" + quantity + "]";
}
}
public class PriorityQueueDemo2 {
public static void main(String[] args) {
// Init PriorityQueue
Queue<Book> queue = new PriorityQueue<Book>();
// Creating Books
Book b1 = new Book(121, "Let us C", "Yashwant Kanetkar", "BPB", 8);
Book b2 = new Book(233, "Operating System", "Galvin", "Wiley", 6);
Book b3 = new Book(101, "Data Communications & Networking", "Forouzan", "Mc Graw Hill", 4);
// Adding Books to the queue
queue.add(b1);
queue.add(b2);
queue.add(b3);
System.out.println("Traversing the queue elements:");
// Traversing queue elements
for (Book b : queue) {
System.out.println(b);
}
System.out.println("After removing one book record:");
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
}
}
Kết quả thực thi chương trình trên:
Traversing the queue elements: Book [id=101, name=Data Communications & Networking, author=Forouzan, publisher=Mc Graw Hill, quantity=4] Book [id=233, name=Operating System, author=Galvin, publisher=Wiley, quantity=6] Book [id=121, name=Let us C, author=Yashwant Kanetkar, publisher=BPB, quantity=8] After removing one book record: Book [id=101, name=Data Communications & Networking, author=Forouzan, publisher=Mc Graw Hill, quantity=4] Book [id=121, name=Let us C, author=Yashwant Kanetkar, publisher=BPB, quantity=8] Book [id=233, name=Operating System, author=Galvin, publisher=Wiley, quantity=6]
Như bạn thấy, đối tượng có id=101 sẽ được remove trước, do nó có độ ưu tiên thấp nhất. Kế tiếp remove id=121, id=233.
