Queue và PriorityQueue trong Java

Giới thiệu

Các phương thức đặc trưng của Queue

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

Chuyên mục: Collection Được gắn thẻ: Collection

Bình luận

bình luận