Giới thiệu
- java.util.LinkedList
- java.util.PriorityQueue
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.
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ó.
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() |
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ỗ.
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 đó.
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.
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.
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ử.
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.
Nhận xét
Ví dụ minh họa
Ví dụ sử dụng Queue với LinkedList
package com.gpcoder.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
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.gpcoder.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
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.gpcoder.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.
Tài liệu tham khảo:
- http://o7planning.org/vi/10165/huong-dan-su-dung-nen-tang-tap-hop-trong-java
- https://www.javatpoint.com/java-priorityqueue