PriorityQueue ใน Java: คู่มือการใช้งานฉบับสมบูรณ์

วิธีใช้ PriorityQueue ใน Java

Priority queues ถูกใช้ในการเขียนโปรแกรมเพื่อสร้างโครงสร้างข้อมูลที่รายการข้อมูลที่มีค่าสูงสุดควรถูกประมวลผลก่อนโดยโครงสร้างนั้น

เมื่อคุณเขียนโค้ดใน Java คุณอาจพบสถานการณ์ที่คุณต้องการ implement priority queue นี่คือที่มาของ Java Queue interface อย่างไรก็ตาม เนื่องจาก Queue เป็น interface คุณไม่สามารถ implement มันเข้าไปในโค้ดของคุณได้โดยตรง หากคุณต้องการสร้าง priority queue ด้วย heap data structure คุณจะต้องการใช้ PriorityQueue แทน

บทช่วยสอนนี้จะอภิปรายพื้นฐานของ PriorityQueue ใน Java และสำรวจวิธีสร้าง queue บทช่วยสอนนี้ยังจะสำรวจ methods หลักที่ PriorityQueue เสนอซึ่งสามารถใช้ retrieve และ manipulate เนื้อหาของ queue

Java Queues และ PriorityQueues

Queues เหมือนกับ stacks เป็นโครงสร้างข้อมูลที่มีลำดับเฉพาะในการดำเนินการ operations ในกรณีของ queues operations ถูกดำเนินการในลำดับ First-In, First-Out (FIFO) นี่หมายความว่ารายการแรกในรายการจะเป็นรายการแรกที่ออกเสมอ — queue ถูกจัดเรียงตามลำดับของ elements เมื่อพวกมันถูก insert

สมมติว่าคุณอยู่ในร้านอาหาร และคุณสั่งอาหาร คุณจะต้องการได้รับบริการตามลำดับของเวลาที่ลูกค้าแต่ละคนสั่งอาหาร เพราะนั่นเป็นวิธีที่公平ที่สุด ดังนั้น หากคุณสั่งอาหารหลัง Jack คุณจะต้องการได้รับบริการทันทีหลัง Jack นั่นคือตัวอย่างของ queue

เพื่อวัตถุประสงค์ของบทช่วยสอนนี้ เราจะโฟกัสที่ PriorityQueue implementation ของ Queue interface ซึ่งใช้สำหรับสร้าง priority queues ใน Java

PriorityQueues เป็นประเภทของ queue ที่ elements ของมันถูกจัดเรียงตาม priority ของพวกมัน นี่หมายความว่า ใน queue ที่มีค่า 5 และ 10, 10 จะอยู่ที่จุดเริ่มต้นของ queue ตลอดเวลา แม้จะถูกเพิ่มทีหลังสุด

สร้าง Priority Queue

เพื่อสร้าง priority queue ใน Java คุณต้อง import แพ็คเกจ java.util.PriorityQueue ก่อน แพ็คเกจนี้มีเมธอด PriorityQueue ที่เราสามารถใช้สร้าง queues ของเราได้ เราสามารถ import PriorityQueue package ด้วยโค้ดนี้:

81% ของผู้เข้าร่วมระบุว่ารู้สึกมั่นใจมากขึ้นเกี่ยวกับโอกาสงานทางเทคโนโลยีหลังจากเข้าร่วมบูทแคมป์ ได้รับการจับคู่กับบูทแคมป์วันนี้

นักศึกษาจบบูทแคมป์เฉลี่ยใช้เวลาน้อยกว่า 6 เดือนในการเปลี่ยนอาชีพ ตั้งแต่เริ่มบูทแคมป์จนหางานแรก

import java.util.PriorityQueue;

ตอนนี้เรา import PriorityQueue แล้ว เราสามารถสร้าง queue โดยใช้แพ็คเกจ นี่คือ syntax ที่ใช้สร้าง PriorityQueue:

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

มาแยกส่วนนี้:

• PriorityQueue บอกโปรแกรมของเราว่าเราต้องการสร้าง priority queue
• DataType คือประเภทข้อมูลที่ queue ของเราจะจัดเก็บ
• queue_name คือชื่อของตัวแปรที่จะถูกกำหนด queue ที่เราสร้าง
• new PriorityQueue(); เริ่มต้น priority queue

ดังนั้น สมมติว่าเราต้องการสร้าง queue ที่จัดเก็บออเดอร์ของลูกค้าในร้านอาหารของเรา เราต้องการให้ queue ของเราจัดเก็บหมายเลขโต๊ะของลูกค้าแต่ละคน เราสามารถสร้าง stack นี้ได้โดยใช้โค้ดต่อไปนี้:

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

ในตัวอย่างนี้ เราสร้าง instance ของ PriorityQueue ชื่อ orders ซึ่งจัดเก็บค่า integer ใน queue ของเรา elements จะถูก accessed และ removed โดยใช้โครงสร้างข้อมูล FIFO

เพิ่ม Item เข้า PriorityQueue

ใน Java แต่ละ element ใน queue เรียกว่า item

เพื่อเพิ่ม item เข้า queue เราสามารถใช้เมธอด add() เมธอดนี้รับพารามิเตอร์หนึ่ง: ค่าของ item ที่คุณต้องการเพิ่มเข้า queue หาก queue เต็ม เมธอด add() จะคืนค่า exception

นอกจากนี้ เราสามารถใช้เมธอด offer() เพื่อเพิ่ม item เข้า queue ความแตกต่างระหว่าง add() และ offer() คือ offer() คืนค่า false หาก queue เต็ม ในขณะที่ add() โยน exception

สมมติว่าเราต้องการเพิ่มโต๊ะ #22 และ #17 ตามลำดับเข้า stack เพราะพวกเขาเพิ่งสั่งอาหารกลางวัน เราสามารถทำได้ด้วยโค้ดนี้:

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); } }

โค้ดของเราส่งคืน:

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

มาแยกตัวอย่างของเรา ก่อนอื่น เรา import PriorityQueue class ซึ่งเราใช้ต่อไปในโค้ดของเรา จากนั้นเรา declare class ที่ชื่อ AddCustomer ซึ่งจัดเก็บโค้ดสำหรับตัวอย่างนี้ นี่คือวิธีการทำงานของโค้ดภายใน class ของเรา:

1. เราใช้ new PriorityQueue<>(); เพื่อสร้าง priority queue ชื่อ orders
2. เราใช้เมธอด add() เพิ่มโต๊ะ #22 เข้า stack ของเรา
3. เราพิมพ์คำว่า Orders: ตามด้วยเนื้อหาของ stack ของเราไปที่ console
4. เราใช้เมธอด offer() เพิ่มโต๊ะ #17 เข้า stack ของเรา
5. เราพิมพ์คำว่า Updated orders: ตามด้วยเนื้อหาที่ปรับปรุงแล้วของ stack ของเราไปที่ console

22 ปรากฏก่อนใน stack ของเรา และดังนั้นจะเป็นรายการแรกที่ออกเมื่อเรา remove element กล่าวคือ โต๊ะ #22 อยู่ที่ยอดของ stack ของเรา โต๊ะ #17 จัดเก็บในตำแหน่งที่สองใน stack ของเรา จำไว้ priority queues จัดเรียงในลำดับ FIFO

โค้ดของเราส่งคืน array พร้อม orders ต้นฉบับ แล้ว array พร้อม updated orders

ลบ Item จาก PriorityQueue

มีสองเมธอดที่สามารถใช้ลบ item จาก PriorityQueue:

• remove() ลบ instance เดียวของ element จาก queue
• poll() ลบ element แรกจาก queue และคืนค่า item ที่ถูกลบ

สมมติว่า sous-chef ของเราได้ประมวลผลออเดอร์ #17 และต้องการลบมันจาก stack หลังจากออเดอร์นั้นถูกประมวลผล chef ของเราได้เตรียมออเดอร์ #22 และต้องการลบมันจาก stack

ออเดอร์ #17 อยู่ตำแหน่ง 2 ใน stack ของเรา และออเดอร์ #22 อยู่ตำแหน่ง 1 เราต้องการลบ items เหล่านี้ในลำดับนั้น เราสามารถใช้โค้ดนี้เพื่อลบออเดอร์:

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."); } }

โค้ดของเราส่งคืน:

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

มาแยกโค้ดของเรา ก่อนเราใช้เมธอด remove() เพื่อลบออเดอร์ที่ตำแหน่ง 2 ใน stack ของเรา นี่ลบออเดอร์ #17

จากนั้นโค้ดของเราพิมพ์ข้อความระบุ Was order #17 removed? ตามด้วยผลลัพธ์ของเมธอด remove() remove() ลบ #17 จาก stack ของเราสำเร็จ ดังนั้นเมธอดคืนค่า true

ต่อไป เราใช้เมธอด poll() เพื่อลบ item บนสุดใน stack ของเรา ในกรณีนี้คือออเดอร์ #22 poll() ลบออเดอร์ #22 และคืนค่า item ที่ถูกลบ หลังจาก item ถูกลบ เราพิมพ์ข้อความ Order #[order number removed] was removed from the queue. ไปที่ console

ดึง Item

เมธอด peek() ใช้ retrieve head ของ queue item (item แรกใน queue) สมมติว่าเราต้องการรู้ค่าของออเดอร์ถัดไปใน stack ของเรา เพราะ sous-chef ของเราพร้อมรับออเดอร์ใหม่

เราสามารถใช้โค้ดนี้เพื่อดึงหมายเลขโต๊ะของลูกค้าที่อยู่คิวถัดไป:

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 + "."); } }

โค้ดของเราส่งคืน:

The next order to be processed is table #22.

Item แรกใน stack ของเราคือ 22 และดังนั้นเมื่อเราใช้เมธอด peek() โปรแกรมของเราคืนค่า 22 บรรทัดสุดท้ายของโค้ดของเรา เราพิมพ์ข้อความระบุ The next order to be processed is table #[number of first order in stack]. โดยหมายเลขของออเดอร์แรกใน stack ถูกค้นพบโดย peek()

Iterate ผ่าน Priority Queue

บ่อยครั้ง เมื่อคุณทำงานกับ queues คุณจะต้องการสร้าง iterator บน elements ของ priority queue

เพื่อทำเช่นนั้น เราสามารถใช้เมธอด iterator() ซึ่งเป็นส่วนหนึ่งของแพ็คเกจ java.util.Iterator แต่ก่อนที่เราจะใช้เมธอด iterator() เราต้อง import Iterator package ก่อนด้วยโค้ดนี้:

import java.util.Iterator;

สมมติว่าเราต้องการพิมพ์รายการทุก item ใน queue ของออเดอร์ร้านอาหารของเราไปที่ console เราสามารถทำได้ด้วยโค้ดนี้:

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()); } } }

โค้ดของเราส่งคืน:

22 17 14 19

ในโค้ดของเรา เราเพิ่มค่าสี่ค่าเข้า queue ก่อน แล้วเราใช้เมธอด iterator() สร้าง iterator ที่เราสามารถใช้ไปทุก item ใน priority queue ของเรา เราจึงสร้างลูป while ที่วิ่งผ่านทุก item ใน iterator ของเรา — สำหรับทุก item ใน queue orders — และพิมพ์ค่าถัดไปใน queue

PriorityQueue Methods เพิ่มเติม

มีอีกสามเมธอดที่มักใช้กับ PriorityQueue class ดังนี้:

Method Name	Description
size()	คืนความยาวของ queue
toArray()	แปลง queue เป็น array
contains(elementName)	ค้นหา element ใน queue

สรุป

PriorityQueue class ใช้ใน Java เพื่อ implement Queue interface Queues ใช้โครงสร้างข้อมูล FIFO ดังนั้น item แรกที่เข้าเป็นรายการแรกที่ออก

บทช่วยสอนนี้เดินทางผ่านพื้นฐานของ queues และ PriorityQueues ใน Java เรายังอภิปรายวิธีสร้าง queue และเมธอดหลักที่คุณสามารถใช้ retrieve items จากและ manipulate queue

ตอนนี้คุณมีเครื่องมือที่จำเป็นเพื่อเริ่มใช้ Java PriorityQueue class อย่างมืออาชีพแล้ว!