# The Priority Queue

The priority queue is a somewhat similar data structure to the **queue. **The difference lies in how the elements are being processed:

- A standard queue strictly follows the FIFO (First In Last Out) principle.
- A priority queue does
**not**follow the FIFO principle.

In a priority queue, the elements are being removed from the queue based on their *priority. *This translates to the requirement that:

**Every element in a priority queue must have a priority associated with it.**

As you might have guessed – the element with the highest priority is removed from the queue (dequeued).

But how do should you define the priority of the elements in the queue?

## Defining priorities to elements

Basically, you have two alternatives for defining priorities to the elements in the queue. You can either:

- Order elements based on their natural ordering.
- Order elements with a custom Comparator.

In this article we’ll focus on how to implement a Priority Queue, so for simplicity’s sake we’ll order the elements based on their **natural ordering.**

In our example the priority queue will be limited to **int, **so natural ordering is perfectly fine. However, keep in mind that this is for demonstration purposes only.

If you were to implement a priority queue in real life, you probably want to make use of generics, – or just do like any other developer, and use the built in java.util.PriorityQueue.

To keep our example implementation compliant with the Java specification, the *least *element is defined as the element with the highest priority.

## Priority queue operations

The most basic set of operations for any implementation of a queue is:

- enqueue – Inserting an element into the queue.
- dequeue – Removing an element from the queue.
- isEmpty – Returning true if the queue is empty.
- size – Returning the size / number of elements in the queue.
- contains – Returning true if the queue contains the given element.
- peek – Returning the front element of the queue,
*without*removing it.

Please note that the Java implementation of the Priority Queue use different names for the methods. In a production environment, I highly suggest that you use the default implementation of the Priority Queue, instead of “home growing” it.

## Implementation of the priority queue

Now, let’s implement a *non-generic *priority queue in Java. We’ll implement one operation at a time, but first we have to decide which *inner data structure *we want to use.

An array is perfectly fine, so we’ll roll with that.

For those of you that are familiar with arrays, you probably know that arrays have a **fixed **size in Java. Our solution for this problem is that we’ll provide a private method *double(), *which “increases” the capacity of the array.

The code skeleton for the priority queue is presented below.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | package priorityqueue; public class PriorityQueue { private int[] innerArray; private int size; public PriorityQueue() { this.innerArray = new int[10]; size = 0; } public void enqueue(int x) { } public int dequeue() { return 0; } public int peek() { return 0; } public boolean contains(int x) { return false; } public boolean isEmpty() { return false; } public int size() { return 0; } private void doubleArray() { } } |

As you can see, we use an int array as the inner data structure, and initials it’s default size to 10 in the constructor. We also provide a private variable *size *to keep track of the number of elements.

### Implementing size, isEmpty & peek

The implementation of the *size* and *isEmpty* methods are as easy as it gets. One thing to keep in mind: the size variable is used so we can avoid having to loop through the array and count “valid” integers. In the constructor, all indexes have been assigned an int with the value of 0.

1 2 3 4 5 6 7 | public boolean isEmpty() { return size == 0; } public int size() { return size; } |

What about peek? It is in fact quite simple as well – if the size is more than 0, we return the first element. If it is less than zero, we throw a *NoSuchElementException.*

1 2 3 4 5 | public int peek() { if (isEmpty()) throw new NoSuchElementException("The queue is empty"); return innerArray[0]; } |

### Implementing contains

It’s time to implement *contains – *which should return true if the queue contains the provided parameter.

How should we implement this? One naive way would be to simply loop through the array, and return true if we encounter the provided int in the array.

However, this will not work! What if the user provides us with *0? *As previously mentioned, the array is initially assigned ints with the default value – which is zero.

Said in other words: We’ll get a *false positive.*

The solution? Only loop through the indexes which we *know *contains inserted values.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | public boolean contains(int x) { // Check for empty. if(isEmpty()) return false; // Looping through the positions which contains inserted values, // ignoring trailing default 0 values. for(int i = 0; i < size; i++) { // Comparing if(innerArray[i] == x) return true; } // None found return false; } |

### Implementing enqueue & dequeue

First, let’s think about what we want to happen if we insert / enqueue an element. Note that we ignore the *doubleArray *method for now.

*We want inserted elements to be placed in the queue, in the correct position according to it’s priority.*

This visualization of the *enqueue *operation tells us that we’ll have to shift all elements of lower priority one position up in the array.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | public void enqueue(int x) { // If it is empty, insert in front if (size == 0) { size++; innerArray[0] = x; return; } // If full, we'll have to double the array if (size() == innerArray.length) doubleArray(); // Looping through int temp = x; for (int i = 0; i < size; i++) { // If priority is higher, ie. values is lower, we shift. if (x <= innerArray[i]) { int next; temp = innerArray[i]; innerArray[i] = x; // Shifting while (i < size - 1) { next = innerArray[i + 1]; innerArray[i + 1] = temp; temp = next; i++; } break; } } // Placing, increasing size. innerArray[size] = temp; size++; } |

Dequeue works very much in the same way.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | public int dequeue() { // NoSuchElement if (isEmpty()) throw new NoSuchElementException("The queue is empty"); // Storing first int for return int retValue = innerArray[0]; // Shifting all values downwards for (int i = 1; i < size; i++) { innerArray[i - 1] = innerArray[i]; } innerArray[size - 1] = 0; size--; return retValue; } |

### Implementing doubleArray

All that’s left now is to implement the method which double the array if we exceed the initial size. We simply copy the array’s content over to a new array, which is twice the size.

1 2 3 4 5 6 7 8 9 | private void doubleArray() { int[] newArr = new int[innerArray.length * 2]; for(int i = 0; i < innerArray.length; i++) { newArr[i] = innerArray[i]; } innerArray = newArr; } |

## Complete implementation

The complete implementation can be found below. Happy coding. 🙂

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 | package priorityqueue; import java.util.NoSuchElementException; public class PriorityQueue { private int[] innerArray; private int size; public PriorityQueue() { this.innerArray = new int[10]; size = 0; } public void enqueue(int x) { // If it is empty, insert in front if (size == 0) { size++; innerArray[0] = x; return; } // If full, we'll have to double the array if (size() == innerArray.length) doubleArray(); // Looping through int temp = x; for (int i = 0; i < size; i++) { // If priority is higher, ie. values is lower, we shift. if (x <= innerArray[i]) { int next; temp = innerArray[i]; innerArray[i] = x; // Shifting while (i < size - 1) { next = innerArray[i + 1]; innerArray[i + 1] = temp; temp = next; i++; } break; } } // Placing, increasing size. innerArray[size] = temp; size++; } public int dequeue() { // NoSuchElement if (isEmpty()) throw new NoSuchElementException("The queue is empty"); // Storing first int for return int retValue = innerArray[0]; // Shifting all values downwards for (int i = 1; i < size; i++) { innerArray[i - 1] = innerArray[i]; } innerArray[size - 1] = 0; size--; return retValue; } public int peek() { if (isEmpty()) throw new NoSuchElementException("The queue is empty"); return innerArray[0]; } public boolean contains(int x) { // Check for empty. if (isEmpty()) return false; // Looping through the positions which contains inserted values, // ignoring trailing default 0 values. for (int i = 0; i < size; i++) { // Comparing if (innerArray[i] == x) return true; } // None found return false; } public boolean isEmpty() { return size == 0; } public int size() { return size; } private void doubleArray() { int[] newArr = new int[innerArray.length * 2]; for(int i = 0; i < innerArray.length; i++) { newArr[i] = innerArray[i]; } innerArray = newArr; } } |