Computer >> Máy Tính >  >> Lập trình >> Java

PriorityQueue Java

Cách sử dụng PriorityQueue trong Java

Hàng đợi ưu tiên được sử dụng trong lập trình để tạo cấu trúc dữ liệu trong đó mục dữ liệu có giá trị cao nhất sẽ được cấu trúc xử lý trước.

Khi viết mã bằng Java, bạn có thể gặp phải trường hợp muốn triển khai hàng đợi ưu tiên. Đó là nơi xuất hiện giao diện Hàng đợi Java. Tuy nhiên, vì Hàng đợi là một giao diện nên bạn không thể triển khai trực tiếp nó vào mã của mình. Nếu bạn muốn tạo một hàng đợi ưu tiên với cấu trúc dữ liệu heap, thay vào đó, bạn sẽ muốn sử dụng PriorityQueue.

Hướng dẫn này sẽ thảo luận về những điều cơ bản của PriorityQueue trong Java và khám phá cách tạo một hàng đợi. Hướng dẫn này cũng sẽ khám phá các phương pháp chính do PriorityQueue cung cấp có thể được sử dụng để truy xuất và thao tác nội dung của hàng đợi.

Hàng đợi Java và Hàng đợi Ưu tiên

Hàng đợi, giống như ngăn xếp, là cấu trúc dữ liệu có thứ tự cụ thể trong đó các hoạt động được thực hiện. Trong trường hợp hàng đợi, các hoạt động được thực hiện theo thứ tự Nhập trước, Xuất trước (FIFO). Điều này có nghĩa là mục đầu tiên trong danh sách sẽ luôn là mục đầu tiên - hàng đợi được sắp xếp theo thứ tự của các phần tử khi chúng được chèn vào.

Giả sử bạn đang ở trong một nhà hàng và bạn đã đặt hàng. Bạn sẽ muốn được phục vụ theo thứ tự khi mỗi khách hàng gọi món ăn của họ, vì đó là cách tiếp cận công bằng nhất. Vì vậy, nếu bạn đặt đồ ăn sau Jack, bạn sẽ muốn được phục vụ ngay sau Jack. Đó là một ví dụ về hàng đợi.

Với mục đích của hướng dẫn này, chúng tôi sẽ tập trung vào việc triển khai PriorityQueue của giao diện Queue, được sử dụng để tạo các hàng đợi ưu tiên trong Java.

PriorityQueues là một loại hàng đợi mà các phần tử được sắp xếp thứ tự dựa trên mức độ ưu tiên của chúng. Điều này có nghĩa là, trong hàng đợi có giá trị 5 và 10, 10 sẽ luôn ở đầu hàng đợi, ngay cả khi nó được thêm vào sau cùng.

Tạo hàng đợi ưu tiên

Để tạo hàng đợi ưu tiên trong Java, trước tiên bạn phải nhập java.util.PriorityQueue Bưu kiện. Gói này chứa phương thức PriorityQueue mà chúng ta có thể sử dụng để tạo hàng đợi của mình. Chúng tôi có thể nhập gói PriorityQueue bằng mã này:

81% người tham gia cho biết họ cảm thấy tự tin hơn về triển vọng công việc công nghệ của mình sau khi tham gia chương trình đào tạo. Kết hợp với bootcamp ngay hôm nay.

Sinh viên tốt nghiệp bootcamp trung bình dành ít hơn sáu tháng để chuyển đổi nghề nghiệp, từ khi bắt đầu bootcamp đến khi tìm được công việc đầu tiên của họ. 

import java.util.PriorityQueue;

Bây giờ chúng ta đã nhập PriorityQueue, chúng ta có thể tạo một hàng đợi bằng cách sử dụng gói. Đây là cú pháp được sử dụng để tạo PriorityQueue:

PriorityQueue<DataType> queue_name = new PriorityQueue<>();

Hãy phân tích điều này:

  • PriorityQueue cho chương trình biết rằng chúng tôi muốn tạo một hàng đợi ưu tiên.
  • DataType là loại dữ liệu mà hàng đợi của chúng ta sẽ lưu trữ.
  • queue_name là tên của biến sẽ được gán cho hàng đợi mà chúng tôi tạo.
  • PriorityQueue mới (); khởi tạo hàng đợi ưu tiên.

Vì vậy, giả sử chúng tôi muốn tạo một hàng đợi lưu trữ các đơn đặt hàng của khách hàng trong nhà hàng của chúng tôi. Chúng tôi muốn hàng đợi của chúng tôi lưu trữ số bàn của mỗi khách hàng. Chúng tôi có thể tạo ngăn xếp này bằng cách sử dụng mã sau:

PriorityQueue<Integer> orders = new PriorityQueue<>();

Trong ví dụ này, chúng tôi đã tạo một phiên bản của PriorityQueue được gọi là orders nơi lưu trữ các giá trị số nguyên. Trong hàng đợi của chúng tôi, các phần tử sẽ được truy cập và xóa bằng cấu trúc dữ liệu FIFO.

Thêm mục vào PriorityQueue

Trong Java, mỗi phần tử trong hàng đợi được gọi là item .

Để thêm một mục vào hàng đợi, chúng ta có thể sử dụng add() phương pháp. Phương thức này chấp nhận một tham số:giá trị của mục bạn muốn thêm vào hàng đợi của mình. Nếu hàng đợi đã đầy, add() phương thức sẽ trả về một ngoại lệ.

Ngoài ra, chúng ta có thể sử dụng offer() phương pháp để thêm một mục vào hàng đợi. Sự khác biệt giữa add() và offer() đó có phải là offer() không trả về false nếu hàng đợi đã đầy, trong khi add() ném một ngoại lệ.

Giả sử chúng ta muốn thêm bảng # 22 và # 17 theo thứ tự đó vào ngăn xếp của mình vì họ vừa đặt đơn hàng ăn trưa. Chúng tôi có thể làm như vậy bằng cách sử dụng mã này:

import java.util.PriorityQueue;

class AddCustomer {
	public static void main(String[] args) {
		PriorityQueue<Integer> orders = new PriorityQueue<>();

		orders.add(22);
		System.println("Orders: " + orders);

		orders.offer(17);
		System.out.println("Updated orders: " + orders);
	}
}

Mã của chúng tôi trả về:

Orders: [22]
Updated orders: [22, 17]

Hãy phân tích ví dụ của chúng tôi. Đầu tiên, chúng tôi đã nhập lớp PriorityQueue, lớp mà chúng tôi sử dụng sau này trong mã của mình. Sau đó, chúng tôi khai báo một lớp có tên là AddCustomer, lớp này lưu trữ mã của chúng tôi cho ví dụ này. Đây là cách mã bên trong lớp của chúng tôi hoạt động:

  1. Chúng tôi sử dụng new PriorityQueue<>(); để tạo một hàng đợi ưu tiên được gọi là orders .
  2. Chúng tôi sử dụng add() để thêm bảng # 22 vào ngăn xếp của chúng tôi.
  3. Chúng tôi in ra từ Orders: tiếp theo là nội dung của ngăn xếp của chúng tôi vào bảng điều khiển.
  4. Chúng tôi sử dụng offer() để thêm bảng số 17 vào ngăn xếp của chúng tôi.
  5. Chúng tôi in ra điều khoản Updated orders: tiếp theo là nội dung đã sửa đổi trong ngăn xếp của chúng tôi đối với bảng điều khiển.

22 xuất hiện đầu tiên trong ngăn xếp của chúng tôi và vì vậy nó sẽ là ô đầu tiên xuất hiện khi chúng tôi loại bỏ một phần tử. Nói cách khác, bảng # 22 nằm ở đầu ngăn xếp của chúng ta. Bảng # 17 được lưu trữ ở vị trí thứ hai trong ngăn xếp của chúng tôi. Hãy nhớ rằng, các hàng đợi ưu tiên được sắp xếp theo thứ tự FIFO.

Mã của chúng tôi trả về một mảng với các đơn đặt hàng ban đầu của chúng tôi, sau đó là một mảng với các đơn đặt hàng đã cập nhật của chúng tôi.

Xóa mục khỏi PriorityQueue

Có hai phương pháp có thể được sử dụng để xóa một mục khỏi PriorityQueue:

  • remove() xóa một bản sao của một phần tử khỏi hàng đợi.
  • poll() xóa phần tử đầu tiên khỏi hàng đợi và trả về mục đã xóa.

Giả sử sous-chef của chúng tôi đã xử lý đơn đặt hàng số 17 và muốn xóa đơn đặt hàng đó khỏi ngăn xếp. Sau khi đơn đặt hàng đó được xử lý, đầu bếp của chúng tôi đã chuẩn bị đơn đặt hàng số 22 và muốn xóa đơn đặt hàng đó khỏi ngăn xếp.

Đơn hàng số 17 ở vị trí 2 trong ngăn xếp của chúng tôi và đơn hàng số 22 ở vị trí 1. Chúng tôi muốn xóa các mục này theo thứ tự đó. Chúng tôi có thể sử dụng mã này để xóa các đơn đặt hàng:

import java.util.PriorityQueue;

class RemoveOrders {
	public static void main(String[] args) {
		PriorityQueue<Integer> orders = new PriorityQueue<>();

		orders.add(22);
		orders.add(17);

		boolean removed = orders.remove(2);
		System.out.println("Was order #17 removed?" + removed);

		int second_removed = orders.poll();
		System.out.println("Order #" + second_removed + " was removed from the queue.");
	}
}

Mã của chúng tôi trả về:

Was order #17 removed? true
Order #22 was removed from the queue.

Hãy chia nhỏ mã của chúng ta. Đầu tiên, chúng tôi sử dụng remove() phương pháp để loại bỏ thứ tự ở vị trí 2 trong ngăn xếp của chúng tôi. Đơn đặt hàng số 17 đã bị xóa này.

Sau đó, mã của chúng tôi in ra một thông báo cho biết, Was order #17 removed? theo sau là kết quả của remove() phương pháp. remove() đã xóa thành công # 17 khỏi ngăn xếp của chúng tôi, vì vậy phương thức trả về true.

Tiếp theo, chúng tôi sử dụng poll() phương pháp để loại bỏ mục hàng đầu trong ngăn xếp của chúng tôi. Trong trường hợp này, đó là đơn đặt hàng số 22. poll() đã xóa đơn đặt hàng số 22 và trả lại mặt hàng đã xóa. Sau khi mặt hàng bị xóa, chúng tôi in thông báo Order #[order number removed] was removed from the queue. vào bảng điều khiển.

Lấy mục

peek() phương thức được sử dụng để truy xuất phần đầu của một mục hàng đợi (mục đầu tiên trong hàng đợi). Giả sử chúng tôi muốn biết giá trị của đơn hàng tiếp theo trong ngăn xếp của mình vì người phụ trách đầu bếp của chúng tôi đã sẵn sàng nhận một đơn đặt hàng mới.

Chúng tôi có thể sử dụng mã này để truy xuất số bàn của khách hàng ở dòng tiếp theo:

import java.util.PriorityQueue;

class RetrieveOrder {
	public static void main(String[] args) {
		PriorityQueue<Integer> orders = new PriorityQueue<>();

		orders.add(22);
		orders.add(17);

		int next_order = orders.peek();
		System.out.println("The next order to be processed is table #" + next_order + ".");
	}
}

Mã của chúng tôi trả về:

The next order to be processed is table #22.

Mục đầu tiên trong ngăn xếp của chúng tôi là 22 và vì vậy khi chúng tôi sử dụng peek() , chương trình của chúng tôi trả về giá trị 22. Trên dòng cuối cùng của mã, chúng tôi in ra một thông báo cho biết, The next order to be processed is table #[number of first order in stack]. , trong đó số thứ tự đầu tiên trong ngăn xếp được phát hiện bởi peek() .

Lặp lại qua hàng đợi ưu tiên

Thông thường, khi bạn đang làm việc với hàng đợi, bạn sẽ muốn tạo một trình lặp trên các phần tử của hàng đợi ưu tiên.

Để làm như vậy, chúng ta có thể sử dụng iterator() , là một phần của gói java.util.Iterator. Nhưng trước khi chúng ta sử dụng iterator() , trước tiên chúng ta phải nhập gói Iterator bằng cách sử dụng mã này:

import java.util.Iterator;

Giả sử chúng tôi muốn in ra danh sách mọi món trong hàng đợi đặt hàng nhà hàng của chúng tôi ra bảng điều khiển. Chúng tôi có thể làm như vậy bằng cách sử dụng mã này:

import java.util.PriorityQueue;
import java.util.Iterator;

class PrintOrders {
	public static void main(String[] args) {
		PriorityQueue<Integer> orders = new PriorityQueue<>();

		orders.add(22);
		orders.add(17);
orders.add(14);
orders.add(19);

		Iterator<Integer> iterate = orders.iterator();
		while(iterate.hasNext()) {
			System.out.println(iterate.next());
		}
	}
}

Mã của chúng tôi trả về:

22
17
14
19

Trong mã của chúng tôi, đầu tiên chúng tôi thêm bốn giá trị vào hàng đợi của chúng tôi. Sau đó, chúng tôi sử dụng iterator() để tạo một trình lặp mà chúng ta có thể sử dụng để xem qua mọi mục trong hàng đợi ưu tiên của chúng ta. Sau đó, chúng tôi tạo một while vòng lặp chạy qua mọi mục trong trình lặp của chúng tôi - cho mọi mục trong orders hàng đợi - và in ra giá trị tiếp theo trong hàng đợi.

Các phương thức ưu tiên bổ sung

Có ba phương thức khác thường được sử dụng với lớp PriorityQueue. Những điều này như sau:

Tên phương pháp Mô tả
size () Trả về độ dài của hàng đợi.
toArray () Chuyển đổi hàng đợi thành một mảng.
chứa (tên phần tử) Tìm kiếm hàng đợi cho một phần tử.

Kết luận

Lớp PriorityQueue được sử dụng trong Java để triển khai giao diện Queue. Hàng đợi sử dụng cấu trúc dữ liệu FIFO, vì vậy mục đầu tiên vào là mục đầu tiên được xuất ra.

Hướng dẫn này đã trình bày những kiến ​​thức cơ bản về hàng đợi và PriorityQueues trong Java. Chúng tôi cũng đã thảo luận về cách tạo hàng đợi và các phương pháp chính mà bạn có thể sử dụng để truy xuất các mục từ đó và thao tác với hàng đợi.

Bây giờ, bạn đã có các công cụ cần thiết để bắt đầu sử dụng lớp Java PriorityQueue như một người chuyên nghiệp!