CLRS Solutions | Exercise 6.5-7

Show how to implement a first-in, first-out queue with a priority queue. Show how to implement a stack with a priority queue. (Queues and stacks are defined in Section 10.1.)

The key to using a priority queue to simulate other data structures is to assign priorities that enforce the desired ordering. For a queue (first-in, first-out or FIFO), we want the oldest element to have highest priority. For a stack (last-in, first-out or LIFO), we want the newest element to have highest priority.

A queue works like people waiting at a ticket counter. You join the line at the back. You get served at the front.

A stack works like a vertical pile of plates in a cafeteria dispenser. You only touch the top plate. Last plate added is the first plate removed.

Implementing a FIFO Queue

A FIFO queue processes elements in the order they arrive. We can simulate this using a min-priority queue by assigning increasing priorities to elements as they arrive.

Using a min-priority queue:

$$\textsc{Enqueue}(Q, x)$$$$\begin{aligned} 1& \quad priority\,=\,priority\,+\,1 \\ 2& \quad \textsc{Min-Heap-Insert}(Q, \, x, \, priority) \\ \end{aligned}$$

$$\textsc{Dequeue}(Q)$$$$\begin{aligned} 1& \quad \textbf{return }\,\textsc{Heap-Extract-Min}(Q) \\ \end{aligned}$$

The element with the smallest priority (earliest arrival) has highest priority in the min-heap and is extracted first, giving FIFO behavior.

Implementing a Stack

A LIFO stack processes the most recently added element first. We can simulate this using a max-priority queue by assigning increasing priorities to elements as they arrive.

Using a max-priority queue:

$$\textsc{Push}(S, x)$$$$\begin{aligned} 1& \quad priority\,=\,priority\,+\,1 \\ 2& \quad \textsc{Max-Heap-Insert}(S, \, x, \, priority) \\ \end{aligned}$$

$$\textsc{Pop}(S)$$$$\begin{aligned} 1& \quad \textbf{return }\,\textsc{Heap-Extract-Max}(S) \\ \end{aligned}$$

The element with the largest priority (most recent arrival) has highest priority in the max-heap and is extracted first, giving LIFO behavior.

Analysis

Both implementations support all operations in $O(\lg n)$ time, where $n$ is the number of elements currently in the structure. This is slower than optimal queue and stack implementations (which achieve $O(1)$ for all operations using arrays or linked lists), but it demonstrates the versatility of priority queues. Priority queues are most valuable when elements truly have varying importance, not just temporal ordering.

Python Implementation

The following interactive demonstration implements both data structures from scratch. We build complete MinHeap and MaxHeap classes with insert and extract operations, then use these to implement the queue and stack.

# ============================================================ # Min-Heap Implementation (for FIFO Queue) # ============================================================ class MinHeap: """Min-heap implementation for priority queue""" def __init__(self): self.heap = [] def parent(self, i): return (i - 1) // 2 def left(self, i): return 2 * i + 1 def right(self, i): return 2 * i + 2 def swap(self, i, j): self.heap[i], self.heap[j] = self.heap[j], self.heap[i] def min_heapify(self, i): """Maintain min-heap property at index i""" l = self.left(i) r = self.right(i) smallest = i if l < len(self.heap) and self.heap[l][0] < self.heap[smallest][0]: smallest = l if r < len(self.heap) and self.heap[r][0] < self.heap[smallest][0]: smallest = r if smallest != i: self.swap(i, smallest) self.min_heapify(smallest) def insert(self, priority, value): """Insert element with given priority""" self.heap.append((priority, value)) i = len(self.heap) - 1 # Bubble up to maintain heap property while i > 0 and self.heap[self.parent(i)][0] > self.heap[i][0]: self.swap(i, self.parent(i)) i = self.parent(i) def extract_min(self): """Remove and return element with minimum priority""" if len(self.heap) == 0: return None if len(self.heap) == 1: return self.heap.pop() min_item = self.heap[0] self.heap[0] = self.heap.pop() self.min_heapify(0) return min_item def is_empty(self): return len(self.heap) == 0 # ============================================================ # Max-Heap Implementation (for LIFO Stack) # ============================================================ class MaxHeap: """Max-heap implementation for priority queue""" def __init__(self): self.heap = [] def parent(self, i): return (i - 1) // 2 def left(self, i): return 2 * i + 1 def right(self, i): return 2 * i + 2 def swap(self, i, j): self.heap[i], self.heap[j] = self.heap[j], self.heap[i] def max_heapify(self, i): """Maintain max-heap property at index i""" l = self.left(i) r = self.right(i) largest = i if l < len(self.heap) and self.heap[l][0] > self.heap[largest][0]: largest = l if r < len(self.heap) and self.heap[r][0] > self.heap[largest][0]: largest = r if largest != i: self.swap(i, largest) self.max_heapify(largest) def insert(self, priority, value): """Insert element with given priority""" self.heap.append((priority, value)) i = len(self.heap) - 1 # Bubble up to maintain heap property while i > 0 and self.heap[self.parent(i)][0] < self.heap[i][0]: self.swap(i, self.parent(i)) i = self.parent(i) def extract_max(self): """Remove and return element with maximum priority""" if len(self.heap) == 0: return None if len(self.heap) == 1: return self.heap.pop() max_item = self.heap[0] self.heap[0] = self.heap.pop() self.max_heapify(0) return max_item def is_empty(self): return len(self.heap) == 0 # ============================================================ # Priority Queue-Based FIFO Queue # ============================================================ class PriorityQueue: """FIFO Queue implemented using a min-priority queue""" def __init__(self): self.min_heap = MinHeap() self.priority = 0 def enqueue(self, value): """Add element to the back of the queue""" self.priority += 1 self.min_heap.insert(self.priority, value) print(" Enqueued '" + str(value) + "' with priority " + str(self.priority)) def dequeue(self): """Remove and return element from the front of the queue""" if self.min_heap.is_empty(): return None priority, value = self.min_heap.extract_min() print(" Dequeued '" + str(value) + "' (priority " + str(priority) + ")") return value def is_empty(self): return self.min_heap.is_empty() # ============================================================ # Priority Queue-Based LIFO Stack # ============================================================ class PriorityStack: """LIFO Stack implemented using a max-priority queue""" def __init__(self): self.max_heap = MaxHeap() self.priority = 0 def push(self, value): """Add element to the top of the stack""" self.priority += 1 self.max_heap.insert(self.priority, value) print(" Pushed '" + str(value) + "' with priority " + str(self.priority)) def pop(self): """Remove and return element from the top of the stack""" if self.max_heap.is_empty(): return None priority, value = self.max_heap.extract_max() print(" Popped '" + str(value) + "' (priority " + str(priority) + ")") return value def is_empty(self): return self.max_heap.is_empty() # ============================================================ # Demonstration # ============================================================ print("=" * 60) print("FIFO Queue using Priority Queue (Min-Heap)") print("=" * 60) q = PriorityQueue() print("\nEnqueuing elements: A, B, C, D") q.enqueue("A") q.enqueue("B") q.enqueue("C") q.enqueue("D") print("\nDequeuing all elements (should be: A, B, C, D)") while not q.is_empty(): q.dequeue() print("\n" + "=" * 60) print("LIFO Stack using Priority Queue (Max-Heap)") print("=" * 60) s = PriorityStack() print("\nPushing elements: A, B, C, D") s.push("A") s.push("B") s.push("C") s.push("D") print("\nPopping all elements (should be: D, C, B, A)") while not s.is_empty(): s.pop()