How to implement a priority queue using two queues

Implementing a Priority Queue Using Two Standard Queues

Learn how to construct a functional priority queue data structure by leveraging the operations of two ordinary FIFO queues. This article covers the logic, implementation details, and practical considerations.

A priority queue is an abstract data type similar to a regular queue or stack, but where each element has a 'priority' associated with it. Elements with higher priority are served before elements with lower priority. If two elements have the same priority, their order is determined by their insertion sequence (FIFO). While typically implemented using heaps for optimal performance, it's a common interview question and a great conceptual exercise to implement one using only two standard FIFO queues.

The Core Idea: Prioritization Through Reordering

The fundamental challenge is that standard queues only support FIFO (First-In, First-Out) behavior. To simulate priority, when a new element is enqueued, we must ensure it ends up in the correct position relative to other elements based on its priority. This means potentially reordering existing elements. We achieve this by using one queue (let's call it the 'main queue') to hold the actual priority queue elements and another temporary queue (the 'helper queue') to facilitate the reordering process.

flowchart TD
    A[Enqueue (Element, Priority)] --> B{Is Main Queue Empty?}
    B -->|Yes| C[Add (Element, Priority) to Main Queue]
    B -->|No| D{Find Insertion Point}
    D --> E{Dequeue from Main Queue to Helper Queue until correct position or Main Queue empty}
    E --> F[Add (Element, Priority) to Main Queue]
    F --> G{Dequeue from Helper Queue to Main Queue}
    G --> H[Operation Complete]
    C --> H

Flowchart of the Enqueue operation using two queues

Enqueue Operation: Finding the Right Spot

When a new element with a given priority arrives, the enqueue operation is the most complex. We need to iterate through the mainQueue, comparing the new element's priority with existing elements. All elements with higher or equal priority than the new element (and thus should be processed after it) are temporarily moved to the helperQueue. Once the correct insertion point is found (either an element with lower priority is encountered, or the mainQueue becomes empty), the new element is added to the mainQueue. Finally, all elements from the helperQueue are moved back to the mainQueue, maintaining their relative order. This ensures that the mainQueue always has elements ordered by priority, with higher priority elements at the front.

from collections import deque

class PriorityQueue:
    def __init__(self):
        self.main_queue = deque()
        self.helper_queue = deque()

    def enqueue(self, item, priority):
        # If main queue is empty or new item has highest priority, just add it
        if not self.main_queue or priority > self.main_queue[0][1]:
            self.main_queue.appendleft((item, priority)) # Add to front for simplicity in this example
            return

        # Move elements from main_queue to helper_queue until we find the right spot
        while self.main_queue and priority <= self.main_queue[0][1]:
            self.helper_queue.append(self.main_queue.popleft())
        
        # Add the new item
        self.main_queue.appendleft((item, priority))

        # Move elements back from helper_queue to main_queue
        while self.helper_queue:
            self.main_queue.appendleft(self.helper_queue.pop()) # Maintain order

    def dequeue(self):
        if not self.main_queue:
            return None
        return self.main_queue.popleft()[0] # Return the item, not the priority

    def peek(self):
        if not self.main_queue:
            return None
        return self.main_queue[0][0]

    def is_empty(self):
        return len(self.main_queue) == 0

    def size(self):
        return len(self.main_queue)

# Example Usage:
pq = PriorityQueue()
pq.enqueue('Task A', 3)
pq.enqueue('Task B', 1)
pq.enqueue('Task C', 5)
pq.enqueue('Task D', 2)

print(f"Dequeued: {pq.dequeue()}") # Should be Task C (priority 5)
print(f"Dequeued: {pq.dequeue()}") # Should be Task A (priority 3)
pq.enqueue('Task E', 4)
print(f"Dequeued: {pq.dequeue()}") # Should be Task E (priority 4)
print(f"Dequeued: {pq.dequeue()}") # Should be Task D (priority 2)
print(f"Dequeued: {pq.dequeue()}") # Should be Task B (priority 1)
print(f"Is empty: {pq.is_empty()}")

Dequeue and Other Operations

The dequeue operation is straightforward: since the mainQueue is always maintained in priority order, we simply remove and return the element at the front of the mainQueue. Similarly, peek just returns the front element without removing it. is_empty and size operations are also trivial, relying on the underlying queue's capabilities.

sequenceDiagram
    participant Client
    participant PriorityQueue
    participant MainQueue
    participant HelperQueue

    Client->>PriorityQueue: dequeue()
    PriorityQueue->>MainQueue: isEmpty()?
    alt MainQueue is not empty
        PriorityQueue->>MainQueue: popLeft() (item, priority)
        MainQueue-->>PriorityQueue: (item, priority)
        PriorityQueue-->>Client: item
    else MainQueue is empty
        PriorityQueue-->>Client: None
    end

Sequence diagram for the Dequeue operation