Queues, circular queues and priority queues
Definitions, array and linked representations, algorithms and complexity of queues, circular queues (with modulo wrap-around), and priority queues (via heaps), with Python implementations and exam-focused notes.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Queues model real-world waiting lines and scheduling: CPU job scheduling, print spooling, network packet buffering, and breadth-first search (BFS) in graphs. Efficient and correct queue variants—linear, circular, and priority—avoid overflow/underflow bugs and meet performance needs in operating systems, embedded systems, and network software.
Key ideas
- Abstract Data Type (ADT): A mathematical model that specifies what operations are performed, not how they are implemented.
- Queue (ADT): A linear, ordered collection in which insertions happen at one end and deletions at the other. Exact definition: “A queue is a data structure that supports First-In First-Out (FIFO) access; the element inserted earliest is removed first.” Assumptions: elements are comparable for equality; operations are total functions on their domain unless preconditions (like non-emptiness) fail.
- FIFO (First-In First-Out): Access discipline where the first element inserted is the first one removed.
- Enqueue: The operation to insert an element at the rear (back) of the queue.
- Dequeue: The operation to remove and return the element at the front of the queue.
- Peek/Front: Return (without removing) the element currently at the front.
- Underflow: An error condition when attempting to remove (or peek) from an empty queue.
- Overflow: An error condition when attempting to insert into a full queue (fixed-capacity representation).
- Linear queue (array-based): An implementation of the queue ADT using a fixed-size array with two indices: front and rear. A simple version that only increments indices can waste space after many dequeues (false overflow) because freed positions at the front are not reused.
- Exact statement (false overflow problem): “In a linear array queue with monotonically increasing indices front and rear, even when the number of elements is less than capacity, enqueue may be impossible when rear reaches the last index, causing overflow despite available free cells at lower indices.” Assumption: no wrap-around of indices.
- Circular queue: A fixed-size array queue where indices wrap around using modulo arithmetic. Exact definition: “A circular queue is an array-based queue in which the next position after the last index is the first index, implemented by computing (index + 1) mod capacity.” This eliminates false overflow by reusing freed positions.
- Representation (circular queue): Maintain integers front, rear, and size (or only front and rear with a ‘one empty slot’ rule). Common, unambiguous choice: store size. Invariants when using size:
- 0 ≤ size ≤ capacity
- front indicates the index of the current front if size > 0
- rear indicates the next insertion position
- Queue is empty iff size == 0
- Queue is full iff size == capacity
- After enqueue: arr[rear] = x; rear = (rear + 1) mod capacity; size++
- After dequeue: x = arr[front]; front = (front + 1) mod capacity; size--
- Alternative invariant (without size): one empty slot rule: full iff (rear + 1) mod capacity == front; empty iff front == rear; then stored capacity is effectively capacity − 1. Use this only if explicitly stated.
- Linked-list queue: A queue where nodes are linked; maintain head (front) and tail (rear) pointers. No overflow until memory is exhausted; all queue operations are O(1). Mentioned for completeness; details are in “Stacks and queues using linked lists”.
- Priority: A numeric value attached to each element indicating its urgency or importance.
- Priority queue (ADT): A data structure where removal returns the element with the highest priority (or lowest key for a min-priority queue). Exact definition: “A priority queue supports insert and delete-min (min-priority) or delete-max (max-priority) operations so that elements are removed in order of priority, not arrival time.” FIFO does not apply; possible tie-breaking by insertion order for equal priorities is an implementation choice.
- Binary heap: A complete binary tree stored in an array where each node’s key obeys heap order (min-heap: parent ≤ children; max-heap: parent ≥ children). It implements a priority queue with O(log n) insert and delete-min/max and O(1) find-min/max.
- Binary heap array mapping (0-based indexing):
- Parent index of i: floor((i − 1) / 2)
- Left child of i: 2i + 1
- Right child of i: 2i + 2
- Heapify-up (sift-up): After inserting at the end, swap the new key upward until heap order holds.
- Heapify-down (sift-down): After removing the root, move the last element to the root and swap it downward with the smaller (min-heap) child until heap order holds.
- Exact time bounds (assuming random-access array and integer arithmetic):
- Array-based or linked-list queue: enqueue/dequeue/peek are O(1) time; space O(n)
- Circular queue indexing operations are O(1)
- Binary heap priority queue: insert O(log n), delete-min (or delete-max) O(log n), peek O(1), space O(n). Build-heap from n keys is O(n) using Floyd’s method. Alternative implementations: unsorted array/list gives insert O(1), delete-min O(n); sorted array/list gives insert O(n), delete-min O(1).
- Stability in priority queues: If two elements have equal priority, a stable implementation removes them in the order inserted. A binary heap is not inherently stable; stability can be achieved by pairing (priority, tie-breaker) where tie-breaker is a monotonically increasing insertion counter.
- Diagram to draw (linear vs circular queue):
- Draw an array of boxes indexed 0..N−1 below each cell.
- For linear queue false overflow: shade indices 0..k−1 as freed (after dequeues), show front at k, rear at N−1, and still “Overflow” on enqueue.
- For circular queue: show front at k, rear at r, and an arrow from index N−1 back to 0 with label “wrap via (i+1) mod N”. Place the next insertion at free index < k to show reuse.
Formulas
- next: wrapped successor index (unitless). index: current index (unitless). N: capacity (unitless). Applies to circular queue increment.
parent(i) = floor((i − 1) / 2)- i: node index (unitless). Applies in 0-based binary heap to map child to parent.
left(i) = 2·i + 1- i: node index (unitless). Gives left child index in 0-based binary heap.
right(i) = 2·i + 2- i: node index (unitless). Gives right child index in 0-based binary heap.
full ⇔ size = N- size: current number of elements (unitless), N: capacity (unitless). Applies to circular queue when storing size.
empty ⇔ size = 0- size: current number of elements (unitless). Applies to any queue implementation.
- Syntax to remember (Python standard library for heaps): For stability and to avoid comparing item values on ties, use a monotonically increasing counter and store triples as (priority, counter, item).
import heapqheapq.heappush(heap, (priority, counter, item))priority, counter, item = heapq.heappop(heap)heap[0]to peek the min element without popping.
Worked examples
Example 1: Circular queue using an array (Python, fixed capacity)
Program:
# Circular queue implementation with command-driven I/O
# Commands:
# ENQ x -> enqueue integer x
# DEQ -> dequeue and print the removed element or 'Empty'
# PEEK -> print the front element or 'Empty'
# PRINT -> print contents from front to rear (space-separated) or 'Empty'
# EXIT -> terminate
import sys
def main():
data = sys.stdin.read().strip().split()
if not data:
return
it = iter(data)
# First token must be capacity
try:
cap = int(next(it))
except StopIteration:
return
arr = [0] * cap
front = 0
rear = 0
size = 0
out_lines = []
def is_full():
return size == cap
def is_empty():
return size == 0
nonlocal_vars = {'front': front, 'rear': rear, 'size': size}
for token in it:
if token == 'ENQ':
try:
x = int(next(it))
except StopIteration:
break
if nonlocal_vars['size'] == cap:
out_lines.append('Full')
else:
arr[nonlocal_vars['rear']] = x
nonlocal_vars['rear'] = (nonlocal_vars['rear'] + 1) % cap
nonlocal_vars['size'] += 1
out_lines.append(f'Enqueued {x}')
elif token == 'DEQ':
if nonlocal_vars['size'] == 0:
out_lines.append('Empty')
else:
x = arr[nonlocal_vars['front']]
nonlocal_vars['front'] = (nonlocal_vars['front'] + 1) % cap
nonlocal_vars['size'] -= 1
out_lines.append(f'Dequeued {x}')
elif token == 'PEEK':
if nonlocal_vars['size'] == 0:
out_lines.append('Empty')
else:
out_lines.append(str(arr[nonlocal_vars['front']]))
elif token == 'PRINT':
if nonlocal_vars['size'] == 0:
out_lines.append('Empty')
else:
s = nonlocal_vars['size']
f = nonlocal_vars['front']
vals = []
for _ in range(s):
vals.append(str(arr[f]))
f = (f + 1) % cap
out_lines.append(' '.join(vals))
elif token == 'EXIT':
break
else:
# Ignore unknown token
pass
sys.stdout.write('\n'.join(out_lines))
if __name__ == '__main__':
main()
Sample input:
4 ENQ 10 ENQ 20 ENQ 30 DEQ ENQ 40 ENQ 50 ENQ 60 PRINT PEEK DEQ DEQ DEQ DEQ PRINT EXIT
Exact output:
Enqueued 10
Enqueued 20
Enqueued 30
Dequeued 10
Enqueued 40
Enqueued 50
Full
20 30 40 50
20
Dequeued 20
Dequeued 30
Dequeued 40
Dequeued 50
Empty
Explanation highlights: Capacity is 4. After three enqueues and one dequeue, front advances. Two more enqueues fill the queue. The next ENQ causes “Full”. PRINT traverses size elements from front wrapping as needed.
Example 2: Priority queue (min-heap) with stable tie-breaking (Python)
Program:
# Priority queue with commands and stable tie-breaking using a counter
# Commands:
# PUSH p x -> insert item x with integer priority p (lower p = higher priority)
# POP -> remove and print the item with smallest p (FIFO for ties) or 'Empty'
# PEEK -> print the item with smallest p without removing or 'Empty'
# PRINT -> print items in heap order as (p,x) tuples (diagnostic)
# EXIT -> terminate
import sys, heapq
def main():
tokens = sys.stdin.read().strip().split()
if not tokens:
return
it = iter(tokens)
heap = []
counter = 0
out_lines = []
for token in it:
if token == 'PUSH':
try:
p = int(next(it)); x = next(it)
except StopIteration:
break
heapq.heappush(heap, (p, counter, x))
counter += 1
out_lines.append(f'Pushed ({p},{x})')
elif token == 'POP':
if not heap:
out_lines.append('Empty')
else:
p, c, x = heapq.heappop(heap)
out_lines.append(f'Popped {x}')
elif token == 'PEEK':
if not heap:
out_lines.append('Empty')
else:
p, c, x = heap[0]
out_lines.append(str(x))
elif token == 'PRINT':
if not heap:
out_lines.append('Empty')
else:
# Show (priority,item) pairs in heap array order (not sorted)
pairs = [f'({p},{x})' for (p, c, x) in heap]
out_lines.append(' '.join(pairs))
elif token == 'EXIT':
break
else:
# Ignore unknown tokens
pass
sys.stdout.write('\n'.join(out_lines))
if __name__ == '__main__':
main()
Sample input:
PUSH 3 A PUSH 1 B PUSH 2 C PEEK POP PEEK PUSH 1 D POP POP POP PRINT EXIT
Exact output:
Pushed (3,A)
Pushed (1,B)
Pushed (2,C)
B
Popped B
C
Pushed (1,D)
Popped D
Popped C
Popped A
Empty
Explanation highlights: Lower priority number is higher priority. B (1) comes before C (2) and A (3). D has the same priority as B (1), but because of stability (counter), B inserted earlier is removed first; later, D with priority 1 is popped before C and A.
Example 3: Model theory answer — Linear vs Circular Queue and the false overflow
Question: Explain why a linear array queue suffers from false overflow and how a circular queue overcomes it. Write algorithms for enqueue and dequeue in a circular queue and illustrate with N = 5 and the sequence ENQ(10), ENQ(20), ENQ(30), DEQ(), ENQ(40), ENQ(50), ENQ(60).
Model answer:
- Definitions:
- A linear array queue keeps two indices front and rear that move rightwards as elements are removed and inserted. If rear reaches N − 1, further enqueues fail even if there are free cells at the left, causing false overflow.
- A circular queue applies modulo N arithmetic when incrementing indices so that the next position after N − 1 is 0. This reuses freed cells and prevents false overflow as long as size < N.
- Algorithms (with size tracked):
- Enqueue(Q, x):
- If size == N, report Overflow and return.
- arr[rear] ← x.
- rear ← (rear + 1) mod N.
- size ← size + 1.
- Dequeue(Q):
- If size == 0, report Underflow and return.
- x ← arr[front].
- front ← (front + 1) mod N.
- size ← size − 1.
- Return x.
- Enqueue(Q, x):
- Illustration for N = 5:
- Start: front = 0, rear = 0, size = 0.
- ENQ(10): arr[0] = 10; rear = 1; size = 1. Queue: [10]
- ENQ(20): arr[1] = 20; rear = 2; size = 2. Queue: [10, 20]
- ENQ(30): arr[2] = 30; rear = 3; size = 3. Queue: [10, 20, 30]
- DEQ(): remove arr[0] = 10; front = 1; size = 2. Queue: [20, 30]
- ENQ(40): arr[3] = 40; rear = 4; size = 3. Queue: [20, 30, 40]
- ENQ(50): arr[4] = 50; rear = 0 (wrap); size = 4. Queue: [20, 30, 40, 50]
- ENQ(60): arr[0] = 60; rear = 1; size = 5. Queue full: [20, 30, 40, 50, 60] with front = 1. No false overflow; last insert used the wrapped cell at index 0.
- Diagram to draw: Array indices 0..4. After ENQ(50), show rear at 0 (wrapped). After ENQ(60), show rear at 1 and front at 1, size = 5. Label arrows showing modulo wrap.
Common mistakes
- Forgetting to apply modulo N when updating indices in circular queues; leads to index-out-of-range or corrupted order.
- Using only front and rear without size and assuming full when front == rear (this actually indicates empty unless you adopt the ‘one empty slot’ rule). If you do not store size, you must define full as (rear + 1) mod N == front and accept effective capacity N − 1.
- Off-by-one errors in heap child/parent formulas (e.g., using 1-based formulas in 0-based arrays). For 0-based arrays: left = 2i + 1, right = 2i + 2.
- Assuming a priority queue is FIFO. It is not; removal depends on priority. FIFO applies to normal queues only.
- Not handling underflow/overflow explicitly in answers or code. Always show checks and the exact message or return.
- Claiming O(1) time for heap delete-min. Correct is O(log n) because heapify-down can traverse the height of the heap.
- Printing the heap array as if it were sorted. The heap array is not sorted; only the root is the minimum (min-heap).
For your exam
- Short notes: False overflow in linear queues; advantages of circular queues; stability in priority queues; array mapping for heaps. Include the key invariant and one small example.
- Algorithms: Enqueue/Dequeue for circular queue; insert/delete-min for min-heap. Give preconditions, postconditions, and time complexity O(1) or O(log n) as appropriate.
- Programs: Implement a circular queue or a priority queue. Full marks need input handling, boundary checks, and correct output. Show sample I/O.
- Diagrams: Array representation showing indices, front, rear, and wrap-around arrows; binary heap tree with array indices. Label parent/child and show one step of heapify.
- Complexity: State O(1) for queue operations, O(log n) for heap insert/delete, O(1) for heap peek, and O(n) space. Do not overclaim.
- Comparison: Linear vs circular queue; queue vs stack (only briefly, refer to “Stacks and their operations”).
Quick check
- In a circular queue of capacity N storing size, what condition means the queue is full and how do you advance the rear after an insertion?
- Give the 0-based array formulas for parent, left child, and right child indices in a binary heap.
- How can you make a min-heap–based priority queue stable when multiple items have equal priorities?
Answers: (1) Full iff size = N; advance rear as rear = (rear + 1) mod N. (2) parent(i) = floor((i − 1)/2), left(i) = 2i + 1, right(i) = 2i + 2. (3) Pair each item with an increasing insertion counter and use (priority, counter, item) as the heap key so equal priorities are ordered by counter.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?