GP Coder

Trang chia sẻ kiến thức lập trình Java

  • Java Core
    • Basic Java
    • OOP
    • Exception Handling
    • Multi-Thread
    • Java I/O
    • Networking
    • Reflection
    • Collection
    • Java 8
  • Design pattern
    • Creational Pattern
    • Structuaral Pattern
    • Behavior Pattern
  • Web Service
    • SOAP
    • REST
  • JPA
  • Java library
    • Report
    • Json
    • Unit Test
  • Message Queue
    • ActiveMQ
    • RabbitMQ
  • All
Trang chủ Java Core Collection Queue và PriorityQueue trong Java

Queue và PriorityQueue trong Java

Đăng vào 22/11/2017 . Được đăng bởi GP Coder . 28076 Lượt xem . Toàn màn hình

Nội dung

  • 1 Giới thiệu
  • 2 LinkedList
  • 3 PriorityQueue
  • 4 Ví dụ minh họa

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

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ácNém ra ngoại lệTrả về giá trị cụ thể
Thêm một phần tử vào hàng đợiadd(e)offer(e)
Truy xuất một phần tử từ đầu hàng đợiremove()poll()
Lấy và Xóa một phần tử khỏi đầu hàng đợielement()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

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.

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
4.7
12
Nếu bạn thấy hay thì hãy chia sẻ bài viết cho mọi người nhé! Và Donate tác giả

Shares

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

So sánh ArrayList và Vector trong Java
Deque và ArrayDeque trong Java

Có thể bạn muốn xem:

  • Vector trong Java (21/11/2017)
  • Loại bỏ các phần tử trùng trong một ArrayList như thế nào? (28/11/2017)
  • Loại bỏ các phần tử trùng trong một ArrayList như thế nào trong Java 8? (24/02/2019)
  • So sánh Array và ArrayList trong Java (12/11/2017)
  • Deque và ArrayDeque trong Java (23/11/2017)

Bình luận

bình luận

Tìm kiếm

Bài viết mới

  • Clean code 13/01/2024
  • Giới thiệu CloudAMQP – Một RabbitMQ server trên Cloud 02/10/2020
  • Kết nối RabbitMQ sử dụng Web STOMP Plugin 19/06/2020
  • Sử dụng publisher confirm trong RabbitMQ 16/06/2020
  • Sử dụng Dead Letter Exchange trong RabbitMQ 13/06/2020

Xem nhiều

  • Hướng dẫn Java Design Pattern – Factory Method (97349 lượt xem)
  • Hướng dẫn Java Design Pattern – Singleton (96986 lượt xem)
  • Giới thiệu Design Patterns (86647 lượt xem)
  • Lập trình đa luồng trong Java (Java Multi-threading) (85483 lượt xem)
  • Giới thiệu về Stream API trong Java 8 (83024 lượt xem)

Nội dung bài viết

  • 1 Giới thiệu
  • 2 LinkedList
  • 3 PriorityQueue
  • 4 Ví dụ minh họa

Lưu trữ

Thẻ đánh dấu

Annotation Authentication Basic Java Behavior Pattern Collection Creational Design Pattern Cấu trúc điều khiển Database Dependency Injection Design pattern Eclipse Exception Executor Service Google Guice Gson Hibernate How to Interceptor IO Jackson Java 8 Java Core JDBC JDK Jersey JMS JPA json JUnit JWT Message Queue Mockito Multithreading OOP PowerMockito RabbitMQ Reflection Report REST SOAP Structuaral Pattern Swagger Thread Pool Unit Test Webservice

Liên kết

  • Clean Code
  • JavaTpoint
  • Refactoring Guru
  • Source Making
  • TutorialsPoint
  • W3Schools Online Web Tutorials

Giới thiệu

GP Coder là trang web cá nhân, được thành lập với mục đích lưu trữ, chia sẽ kiến thức đã học và làm việc của tôi. Các bài viết trên trang này chủ yếu về ngôn ngữ Java và các công nghệ có liên quan đến Java như: Spring, JSF, Web Services, Unit Test, Hibernate, SQL, ...
Hi vọng góp được chút ít công sức cho sự phát triển cộng đồng Coder Việt.

Donate tác giả

Tìm kiếm các bài viết của GP Coder với Google Search

Liên hệ

Các bạn có thể liên hệ với tôi thông qua:
  • Trang liên hệ
  • Linkedin: gpcoder
  • Email: contact@gpcoder.com
  • Skype: ptgiang56it

Follow me

Copyright 2025 © GP Coder · All Rights Reserved · Giới thiệu · Chính sách · Điều khoản · Liên hệ ·

Share

Blogger
Delicious
Digg
Email
Facebook
Facebook messenger
Flipboard
Google
Hacker News
Line
LinkedIn
Mastodon
Mix
Odnoklassniki
PDF
Pinterest
Pocket
Print
Reddit
Renren
Short link
SMS
Skype
Telegram
Tumblr
Twitter
VKontakte
wechat
Weibo
WhatsApp
X
Xing
Yahoo! Mail

Copy short link

Copy link