Queues and Priority Queues
Tags: java, programming, learning, beginners
Published: 2024-07-09 21:54:52

In a priority queue, the element with the highest priority is removed first. A _queue_ is a first-in, first-out data structure. Elements are appended to the end of the queue and are removed from the beginning of the queue. In a _priority queue_, elements are assigned priorities. When accessing elements, the element with the highest priority is removed first. This section introduces queues and priority queues in the Java API.

## The Queue Interface

The **Queue** interface extends **java.util.Collection** with additional insertion, extraction, and inspection operations, as shown in Figure below.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7f05tr0jbi7dnw6lgd2s.png)

The **offer** method is used to add an element to the queue. This method is similar to the **add** method in the **Collection** interface, but the **offer** method is preferred for queues. The **poll** and **remove** methods are similar, except that **poll()** returns **null** if the queue is empty, whereas **remove()** throws an exception. The **peek** and **element** methods are similar, except that **peek()** returns **null** if the queue is empty, whereas **element()** throws an exception.

## Deque and LinkedList

The **LinkedList** class implements the **Deque** interface, which extends the **Queue** interface, as shown in Figure below. Therefore, you can use **LinkedList** to create a queue. **LinkedList** is ideal for queue operations because it is efficient for inserting and removing elements from both ends of a list.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6y4yrk4zqy1d3hga450r.png)

**Deque** supports element insertion and removal at both ends. The name _deque_ is short for “double-ended queue” and is usually pronounced “deck.” The **Deque** interface extends **Queue** with additional methods for inserting and removing elements from both ends of the queue. The methods **addFirst(e)**, **removeFirst()**, **addLast(e)**, **removeLast()**, **getFirst()**, and **getLast()** are defined in the **Deque** interface.

The code below shows an example of using a queue to store strings. Line 6 creates a queue using **LinkedList**. Four strings are added to the queue in lines 7–10. The **size()** method defined in the **Collection** interface returns the number of elements in the queue (line 12). The **remove()** method retrieves and removes the element at the head of the queue (line 13).

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/we4p9nbl9b4tsbqy7tpi.png)

The **PriorityQueue** class implements a priority queue, as shown in Figure  below. By default, the priority queue orders its elements according to their natural ordering using **Comparable**. The element with the least value is assigned the highest priority and thus is removed from the queue first. If there are several elements with the same highest priority, the tie is broken arbitrarily. You can also specify an ordering using **Comparator** in the constructor **PriorityQueue(initialCapacity, comparator)**.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wf6ewfpai3wtc2mmuzby.png)

The code below shows an example of using a priority queue to store strings. Line 7 creates a priority queue for strings using its no-arg constructor. This priority queue orders the strings using their natural order, so the strings are removed from the queue in increasing order. Lines 18 create a priority queue using the comparator obtained from **Collections.reverseOrder()**, which orders the elements in reverse order, so the strings are removed from the queue in decreasing order.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1xyhpuf2gsyv97r1yo1q.png)