Concepts / Queues and Their Operations

Queues and Their Operations

A priority queue is an abstract data type whose items each carry a priority, and whose remove operation returns an item with the minimum priority currently present, not the item that arrived first.

  • Programming
Interactive lab

Try it: Stack and Queue

The difference between a stack (last in, first out) and a queue (first in, first out).

How it works

  1. A stack adds (push) and removes (pop) at the same end, the top — the last item added leaves first.
  2. A queue adds (enqueue) at the back and removes (dequeue) from the front — the first item added leaves first.
  3. peek / front look at the next item without removing it.
  4. Adding to a full structure is an overflow; removing from an empty one is an underflow.

Default run (3 steps): Stack (bottom → top): 4, 7. 2 of 8 slots used. Choose an operation. Example: push 9. … Stack is now: 4, 7, 9. Size 3/8.

Simplified: Fixed capacity of 8 items so overflow can be shown; Python lists and collections.deque grow as needed.

Educational simulation

Loading the simulation…

Testing the Line Assumption

The phrase priority queue sounds like a line of people waiting for service, and that picture carries a strong assumption: the person who arrived first leaves first, and the person who arrived last waits their turn. That assumption is natural, and it is exactly what this article will test and then correct. A priority queue follows a different rule, so the best way to find out how it works is to make a prediction before reading the answer.

What do you think happens?

Three items are added in this order: A with priority 3, B with priority 1, and C with priority 2. Lower priority numbers are the minimum. In what order does a plain first-in, first-out queue remove them, and in what order does a priority queue remove them?

  • Plain queue: A, B, C. Priority queue: A, B, C.

  • Plain queue: A, B, C. Priority queue: B, C, A.

  • Plain queue: C, B, A. Priority queue: A, B, C.

Reveal answer
Answer:

A plain queue removes A, B, C, which is the arrival order. A priority queue removes B, C, A, because each removal returns the item with the minimum priority currently present.

The source defines a priority queue as an abstract data type whose remove operation returns an item with the minimum priority currently present, not the item that arrived first. The first arrival, A, has the largest priority value here, so it leaves last.

What a Priority Queue Actually Promises

Definition

A priority queue is an abstract data type that represents a collection of items. Each item has an assigned priority, and that priority allows any two items to be compared. Its remove operation returns an item with the minimum priority currently present in the queue.

The key word in that definition is priority. Position in the line is not what decides which item comes out. Notice also what the definition leaves out. It does not promise that items leave in the order they arrived, and it does not promise any particular order for the items that are still waiting. It makes one promise on each removal: the returned item has the minimum priority among what remains.

That is why the word abstract appears in the definition. The rule describes the behavior a user can rely on, not the internal layout that produces it. A programmer using a priority queue only needs to trust the removal rule. How the structure keeps track of the minimum is a separate question, and it is answered later in this article in terms of cost rather than layout.

Add A (priority 3)arrives firstAdd A (priority 3)arrives firstAdd B (priority 1)arrives secondAdd B (priority 1)arrives secondAdd C (priority 2)arrives thirdAdd C (priority 2)arrives thirdFirst removal: Aarrival orderFirst removal: Bminimum priority 1Second removal: Barrival orderSecond removal: Cminimum priority 2Third removal: Carrival orderThird removal: Aminimum priority 3
Given the same insertion order, how does the removal order of a priority queue differ from that of a FIFO queue?

Tracing Add and Remove Step by Step

The best way to see the rule at work is to follow the contents of the queue through a short sequence of calls. Each add places one item into the collection. Each remove takes out the item with the minimum priority that is present at that moment, and the remaining items stay in the queue. Here the priorities are the plain numbers themselves, so the smallest number is the one that leaves first.

Empty queuecontents: noneadd 3contents: 3add 1contents: 1, 3add 2contents: 1, 2, 3remove returns 1contents: 2, 3remove returns 2contents: 3isEmpty returns falsecontents: 3next callnext callnext callnext callnext callnext call
After a series of add and remove calls, which item is returned at each step and how do the remaining contents change?
Worked example

Tracing a Sequence of Adds and Removes

Starting from an empty priority queue, the calls are add 3, add 1, add 2, remove, remove, isEmpty. What does each remove return, and what remains?

  1. 1
    Add 3, then add 1

    After these two calls the queue holds the items 3 and 1. Both are waiting, and neither has been removed.

  2. 2
    Add 2

    The queue now holds 1, 2, and 3. Adding the item 2 does not remove anything, so all three remain.

  3. 3
    First remove

    The minimum priority present is 1. The remove operation returns 1, and the queue now holds 2 and 3.

  4. 4
    Second remove

    The minimum priority present is now 2. The remove operation returns 2, leaving only 3.

  5. 5
    isEmpty

    One item, 3, is still waiting, so isEmpty returns false.

Result

The removals return 1 and then 2. After them the queue still contains 3, and isEmpty returns false.

The Three Essential Operations

The source identifies three operations as essential to a priority queue: add, remove, and isEmpty. The Java PriorityQueue class is written as a parameterized class, PriorityQueue<T>, which implements a priority queue of objects of type T. It also implements the Collection<T> interface, so a priority queue has every method that interface defines, but only these three are essential to its definition.

  • add places a new item into the queue, and its priority determines where it stands relative to the other items.
  • remove takes out and returns the item with the minimum priority currently present.
  • isEmpty reports whether the queue holds no items at all.
java
Output
1
3
false
5
true
Notes on the code
  • The queue is declared with the generic type Integer, so each item is an object that can be compared.
  • Three items are added in the order 5, 1, 3. Adding does not return anything, so the program prints nothing for these calls.
  • The first remove returns 1, the smallest item present, not 5, which arrived first.
  • The second remove returns 3, the smallest of the remaining items.
  • isEmpty returns false because the item 5 still waits.
  • The third remove returns 5, and the queue is then empty, so isEmpty returns true.

What do you think happens?

Starting from an empty queue, the calls are add 4, add 2, add 9, remove, add 1, remove, remove. What does each remove return?

Reveal answer
Answer:

The first remove returns 2, the second returns 1, and the third returns 4.

After add 4, add 2, and add 9, the smallest present is 2. After that removal the queue holds 4 and 9. Adding 1 makes 1 the smallest, so the next removal returns 1. The last removal returns 4, the smallest of the remaining 4 and 9.

Making Items Comparable

A remove operation that returns the minimum item only makes sense if the queue can decide, for any two items, which one is smaller. The source compares this to sorting, since in both cases we need to compare any two items. Items in a priority queue must therefore be comparable. The source gives two ways to supply that comparison, and they mirror the two standard approaches to sorting objects in Java.

Two Ways to Build the Queue

The source describes two broad implementations. The simplest keeps a linked list of items in order of increasing priority. Remove is then cheap, because it removes and returns the first item in the list. Add is the expensive part, because the new item must be inserted at its correct position, and that insertion has average run time Theta(n), where n is the number of items in the list.

The source also states that a priority queue can be implemented so that both add and remove run in Theta(log(n)) time, which is much more efficient for large queues. That efficient version uses a heap. The source does not explain how a heap arranges its items and says it will not discuss that implementation in the section, so this article does not describe the arrangement either. The reliable takeaway is the cost contrast between the two designs.

ImplementationCost of addCost of remove
Linked list kept in priority orderTheta(n) on averageCheap: removes the first item
Heap-based implementationTheta(log(n))Theta(log(n))

Complexity contrast between the two implementations described in the source

Two Different Meanings of Heap

The word heap appears in two unrelated senses. The first is the heap data structure, which is the efficient implementation behind a priority queue described above. The second is the heap where Java objects are created. The two share a name but serve different purposes, and confusing them is a common source of trouble when reading about priority queues.

Heap data structurean implementation techniqueHeap where objectsare createda memory area for objectsBacks a priorityqueuegives Theta(log(n)) add andremoveHolds objects createdat run timenot a priority-orderingtool
How do the heap that backs a priority queue and the heap where Java objects live differ in their purpose?
MEDIUM

A colleague says that because a priority queue uses a heap, the objects it stores must be kept in the heap where Java objects are created. Explain why this statement mixes up two different ideas, using only what the source says about the two meanings of heap.

Hints
  • Ask what job the heap data structure does for a priority queue.
  • Ask whether the source links the heap data structure to where objects are created.

Mistakes Learners Make with Priority Queues

  • Common mistake

    Assuming remove returns the item that was added first

    What it looks like

    After add 5, add 1, add 3, a learner expects the first remove to return 5.

    Why it fails

    Remove returns the item with the minimum priority currently present, not the earliest arrival.

    Do this instead

    The first remove returns 1, the minimum present, and the item 5 leaves later.

  • Common mistake

    Assuming any class can be stored without ordering information

    What it looks like

    A Task class with no compareTo method and no comparator is added to a priority queue.

    Why it fails

    Items must be comparable so the queue can decide which is smaller.

    Do this instead

    Implement Comparable and compareTo in the class, or supply a Comparator to the constructor.

  • Common mistake

    Calling remove on an empty queue without checking

    What it looks like

    A loop calls remove after every item has already been taken out.

    Why it fails

    In Java, remove throws an exception when the queue is empty.

    Do this instead

    Check isEmpty before calling remove.

  • Common mistake

    Treating the two heaps as the same thing

    Why it fails

    The heap data structure is an implementation technique for a priority queue. The heap where objects are created is a separate area used for objects.

    Do this instead

    Keep the implementation technique and the object storage area as distinct ideas.

Practice Tracing a Priority Queue

MEDIUM

Starting from an empty priority queue of integers, perform these calls in order: add 7, add 3, remove, add 5, add 2, remove, isEmpty. Write down what each remove returns and what items remain before answering.

Hints
  • After add 7 and add 3, which item has the minimum priority?
  • Remember that the item 7 is not removed until it is the minimum present.

What do you think happens?

What does the first remove return, and what does the second remove return, in the practice sequence?

Reveal answer
Answer:

The first remove returns 3, and the second remove returns 2. The final isEmpty returns false because 5 and 7 remain.

After add 7 and add 3, the minimum is 3, so the first remove returns 3 and leaves 7. Adding 5 and 2 makes 2 the minimum among 2, 5, and 7, so the second remove returns 2, leaving 5 and 7. Since items remain, isEmpty returns false.

Key Takeaways

  • A priority queue is an abstract data type whose remove operation returns the item with the minimum priority currently present, not the item that arrived first.
  • The essential operations are add, remove, and isEmpty, and in Java remove throws an exception when the queue is empty.
  • Items must be comparable, either by implementing Comparable and compareTo or by supplying a Comparator to the PriorityQueue constructor.
  • A linked-list implementation has average add cost Theta(n), while a heap-based implementation achieves Theta(log(n)) for both add and remove.
  • The heap that implements a priority queue is a data structure, and it is distinct from the heap where Java objects are created.

Related Topics