PriorityQueue Java

How to Use PriorityQueue in Java

Priority queues are used in programming to create data structures where the item of data with the highest value should be processed first by the structure.

When you’re coding in Java, you may encounter a situation where you want to implement a priority queue. That’s where the Java Queue interface comes in. However, because Queue is an interface, you cannot directly implement it into your code. If you want to create a priority queue with the heap data structure, you’ll instead want to use PriorityQueue.

This tutorial will discuss the basics of PriorityQueue in Java and explore how to create a queue. This tutorial will also explore the main methods offered by PriorityQueue that can be used to retrieve and manipulate the contents of the queue.

Java Queues and PriorityQueues

Queues, like stacks, are data structures that have a specific order in which operations are performed. In the case of queues, operations are performed in First-In, First-Out (FIFO) order. This means that the first item in the list will always be the first one out — the queue is sorted in order of the elements as they are inserted.

Suppose you are in a restaurant, and you have placed an order. You’ll want to be served in order of when each customer ordered their food, because that is the fairest approach. So, if you ordered your food after Jack, you’ll want to be served immediately after Jack. That’s an example of a queue.

For the purposes of this tutorial, we are going to focus on the PriorityQueue implementation of the Queue interface, which is used to create priority queues in Java.

PriorityQueues are a type of queue whose elements are ordered based on their priority. This means that, in a queue with the values 5 and 10, 10 will be at the start of the queue at all times, even if it was added last.

Create a Priority Queue

To create a priority queue in Java, you must first import the java.util.PriorityQueue package. This package contains the PriorityQueue method that we can use to create our queues. We can import the PriorityQueue package using this code:

import java.util.PriorityQueue;

Now we have imported PriorityQueue, we can create a queue using the package. Here’s the syntax used to create a PriorityQueue:

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

Let’s break this down:

• PriorityQueue tells our program we want to create a priority queue.
• DataType is the type of data our queue will store.
• queue_name is the name of the variable that will be assigned the queue we create.
• new PriorityQueue(); initializes a priority queue.

So, suppose we wanted to create a queue which stores the orders of customers in our restaurant. We want our queue to store the table number of each customer. We could create this stack using the following code:

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

In this example, we have created an instance of PriorityQueue called orders which stores integer values. In our queue, elements will be accessed and removed using the FIFO data structure.

Add Item to PriorityQueue

In Java, each element in a queue is called an item.

To add an item to a queue, we can use the add() method. This method accepts one parameter: the value of the item you want to add to your queue. If the queue is full, the add() method will return an exception.

In addition, we can use the offer() method to add an item to a queue. The difference between add() and offer() is that offer() returns false if the queue is full, whereas add() throws an exception.

Suppose we want to add tables #22 and #17 in that order to our stack because they have just placed their lunch orders. We could do so using this code:

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

Our code returns:

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

Let’s break down our example. First, we imported the PriorityQueue class, which we use later on in our code. Then we declared a class called AddCustomer, which stores our code for this example. Here is how the code inside our class works:

1. We use new PriorityQueue<>(); to create a priority queue called orders.
2. We use the add() method to add table #22 to our stack.
3. We print out the word Orders: followed by the contents of our stack to the console.
4. We use the offer() method to add table #17 to our stack.
5. We print out the term Updated orders: followed by the revised contents of our stack to the console.

22 appears first in our stack, and so it will be the first one out when we remove an element. In other words, table # 22 is at the top of our stack. Table #17 is stored in the second position in our stack. Remember, priority queues are ordered in the FIFO order.

Our code returns an array with our original orders, then an array with our updated orders.

Remove Item from PriorityQueue

There are two methods which can be used to remove an item from a PriorityQueue:

• remove() removes a single instance of an element from a queue.
• poll() removes the first element from a queue and returns the removed item.

Suppose our sous-chef has processed order #17 and wants to remove it from the stack. After that order was processed, our chef has prepared order #22 and wants to remove it from the stack.

Order #17 is at position 2 in our stack, and order #22 is at position 1. We want to remove these items in that order. We could use this code to remove the orders:

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

Our code returns:

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

Let’s break down our code. First, we used the remove() method to remove the order at position 2 in our stack. This removed order #17.

Then our code printed out a message stating, Was order #17 removed?followed by the result of the remove() method. remove() successfully removed #17 from our stack, so the method returned true.

Next, we used the poll() method to remove the top item in our stack. In this case, that was order #22. poll() removed order #22 and returned the removed item. After the item was removed, we printed the message Order #[order number removed] was removed from the queue. to the console.

"Career Karma entered my life when I needed it most and quickly helped me match with a bootcamp. Two months after graduating, I found my dream job that aligned with my values and goals in life!"

Venus, Software Engineer at Rockbot

Find Your Bootcamp Match

Retrieve Item

The peek() method is used to retrieve the head of a queue item (the first item in the queue). Suppose we wanted to know the value of the next order in our stack because our sous-chef is ready to take on a new order.

We could use this code to retrieve the table number of the customer who is next in line:

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

Our code returns:

The next order to be processed is table #22.

The first item in our stack is 22, and so when we use the peek() method, our program returns the value 22. On the last line of our code, we print out a message stating, The next order to be processed is table #[number of first order in stack]., where the number of the first order in the stack was discovered by peek().

Iterate Through a Priority Queue

Often, when you’re working with queues, you’ll want to create an iterator over the elements of the priority queue.

To do so, we can use the iterator() method, which is part of the java.util.Iterator package. But before we use the iterator() method, we must first import the Iterator package using this code:

import java.util.Iterator;

Suppose we wanted to print out a list of every item in our queue of restaurant orders to the console. We could do so using this code:

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

Our code returns:

22
17
14
19

In our code, we first add four values to our queue. Then we use the iterator() method to create an iterator that we can use to go through every item in our priority queue. We then create a while loop that runs through every item in our iterator — for every item in the orders queue — and prints out the next value in the queue.

Additional PriorityQueue Methods

There are three more methods which are often used with the PriorityQueue class. These are as follows:

Conclusion

The PriorityQueue class is used in Java to implement the Queue interface. Queues use the FIFO data structure, so the first item in is the first one out.

This tutorial walked through the basics of queues and PriorityQueues in Java. We also discussed how to create a queue and the main methods you can use to retrieve items from and manipulate a queue.

You now have the tools you need to start using the Java PriorityQueue class like a pro!