Queues

A queue is a first-in, first-out (FIFO) collection: items leave in exactly the order they arrived, like people waiting at a checkout. Where a stack serves the most recent arrival, a queue serves the oldest — which makes it the natural model for fair, in-order processing such as print spooling, buffering and scheduling.

---

Spec Mapping

This lesson addresses the H446 1.4.2 Data Structures content on queues:

• Define a queue as a FIFO abstract data type with two ends — front (where items leave) and rear (where items join) — and state its operations: enqueue, dequeue, front/peek, isEmpty, isFull, size.
• Implement and trace the three queue variants — linear, circular and priority — including the modular (wrap-around) arithmetic of a circular queue.
• Explain why a circular queue is preferred over a naive linear one (space reuse), and how a priority queue departs from strict FIFO.
• Connect queues to real applications: buffering, print spooling, CPU/OS scheduling, breadth-first search and network packet handling.

(Phrasing here paraphrases the specification content; it is not a verbatim quote.)

---

What is a Queue?

A queue is a linear abstract data type obeying the FIFO principle: the first item enqueued is the first dequeued. Activity happens at two ends — items join at the rear and leave from the front — which is the key structural difference from a stack, where everything happens at one end. The analogy is an orderly line of people: you join at the back and are served from the front, so service order matches arrival order.

Like a stack, a well-implemented queue performs its core operations in constant time, $O(1)$O(1), because both ends are tracked by pointers and no searching or shifting is needed. That guarantee, and the reason for it, is a recurring exam point.

As with the stack, "queue" names an abstract data type: it is defined by behaviour (the FIFO contract and the operation set), not by any one implementation. The same queue behaviour can be realised by an array with front/rear indices or by a linked list with head/tail pointers, and code that only calls enqueue, dequeue and peek cannot tell which lies beneath. This separation of interface from implementation is the principle of abstraction, and it is why this lesson can present three different array variants plus a linked-list option that all honour the identical FIFO promise.

The deeper reason queues matter so much in real systems is that they solve the producer–consumer problem: one component generating work (keystrokes, packets, print jobs, ready processes) rarely runs at the same speed as the component handling it. A queue sits between them as a holding area, absorbing bursts from the producer and feeding the consumer in arrival order. Without it, fast bursts would be lost and ordering would be scrambled. Recognising a "something arrives faster than it can be processed, and order must be preserved" scenario as a queue problem is exactly the kind of applied reasoning the exam rewards.

Real-world analogies

• A supermarket checkout line — first to join is first served.
• Print jobs — the first document sent prints first.
• A call centre — callers are answered in the order they called.

---

Queue Operations

Operation	Description	Complexity
enqueue(item)	Add an item to the rear	$O(1)$O(1)
dequeue()	Remove and return the front item	$O(1)$O(1)
front() / peek()	Return the front item without removing it	$O(1)$O(1)
isEmpty()	True if the queue holds no items	$O(1)$O(1)
isFull()	True if a fixed-size (array) queue is full	$O(1)$O(1)
size()	Number of items currently held	$O(1)$O(1)

flowchart LR
    IN["enqueue →"] --> R["rear"]
    R -.-> Q["A | B | C | D"]
    Q -.-> F["front"]
    F --> OUT["→ dequeue"]

The single most common confusion is which end does what: enqueue adds at the rear; dequeue removes from the front. A stack uses one end (LIFO); a queue uses opposite ends (FIFO). Keeping that picture clear prevents most queue errors.

---

Linear Queue (Array-Based)

A linear queue uses an array with a front pointer (index of the item to remove next) and a rear pointer (index of the most recently added item). A count also tracks how many items are present, which simplifies the full/empty tests. Two pointers are needed precisely because a queue works at both ends — contrast the stack, which needed only one (top) because it works at a single end. Each enqueue advances rear and writes; each dequeue reads at front and advances front. The two pointers move independently and only ever forward, which is what produces the wasted-space problem described below.

Pseudocode (OCR-style)

const MAX_SIZE = 5
array queue[MAX_SIZE]
front = 0
rear = -1
count = 0

function enqueue(item)
    if count == MAX_SIZE then
        print("Queue Full")
    else
        rear = rear + 1            // advance rear
        queue[rear] = item         // store at the new rear
        count = count + 1
    endif
endfunction

function dequeue()
    if count == 0 then
        print("Queue Empty")
        return null
    else
        item = queue[front]        // read the front item
        front = front + 1          // advance front past it
        count = count - 1
        return item
    endif
endfunction

Tracing a linear queue

Start empty (front = 0, rear = -1, size 5):

Operation	Array	front	rear	count
enqueue(A)	[A, _, _, _, _]	0	0	1
enqueue(B)	[A, B, _, _, _]	0	1	2
enqueue(C)	[A, B, C, _, _]	0	2	3
dequeue() → A	[_, B, C, _, _]	1	2	2
dequeue() → B	[_, _, C, _, _]	2	2	1

The problem with linear queues

Look at the trace: after two dequeues, indices 0 and 1 are empty, but front has moved past them and the linear logic never goes back. Keep enqueuing and rear will reach MAX_SIZE - 1 and report "Queue Full" — even though two slots stand empty at the start.

Index 0	Index 1	Index 2	Index 3	Index 4
wasted	wasted	C	D	E

Those two leading slots sit before the front pointer and cannot be reused. This wasted space is the linear queue's fatal flaw, and it is exactly what the circular queue fixes. (You could instead shift every element down on each dequeue to keep front at 0, but that makes dequeue $O(n)$O(n) — a cure worse than the disease.)

---

Circular Queue

A circular queue treats the array as a ring: when a pointer would step off the end, it wraps around to index 0, so emptied leading slots are reused. The wrap is achieved with modular arithmetic.

The key formula

$\text{next} = (\text{current} + 1) \bmod \text{MAX\_SIZE}$next=(current+1)modMAX_SIZE

For a queue of size 5, stepping from the last index: $(4 + 1) \bmod 5 = 0$(4+1)mod5=0 — the pointer wraps from index 4 back to index 0 instead of running off the end. This one change is the entire difference from a linear queue.

It helps to picture the array bent into a ring with its two ends joined, so that index 4 sits immediately before index 0. The front and rear pointers then chase each other around this ring: rear advances as items join, front advances as items leave, and both wrap from the last index back to the first. No slot is ever abandoned — once an item is dequeued, its slot becomes available again the next time a pointer comes round to it. The modulo operator is simply the arithmetic that turns a straight line of indices into a circle, and it is the same idea you meet in clock arithmetic (after 12 comes 1) and in hash functions (mapping a large key into a fixed table size). Because the queue still removes items strictly in arrival order, a circular queue is just as FIFO as a linear one — the wrap-around is purely an efficiency device for reusing memory, not a change in behaviour, a distinction examiners like to probe.

Pseudocode (OCR-style)

const MAX_SIZE = 5
array queue[MAX_SIZE]
front = 0
rear = -1
count = 0

function enqueue(item)
    if count == MAX_SIZE then
        print("Queue Full")
    else
        rear = (rear + 1) MOD MAX_SIZE   // wrap instead of overrun
        queue[rear] = item
        count = count + 1
    endif
endfunction

function dequeue()
    if count == 0 then
        print("Queue Empty")
        return null
    else
        item = queue[front]
        front = (front + 1) MOD MAX_SIZE // wrap the front too
        count = count - 1
        return item
    endif
endfunction

Python implementation

class CircularQueue:
    def __init__(self, max_size):
        self.queue = [None] * max_size
        self.max_size = max_size
        self.front = 0
        self.rear = -1
        self.count = 0

    def enqueue(self, item):
        if self.count == self.max_size:
            raise OverflowError("Queue Full")
        self.rear = (self.rear + 1) % self.max_size
        self.queue[self.rear] = item
        self.count += 1

    def dequeue(self):
        if self.count == 0:
            raise IndexError("Queue Empty")
        item = self.queue[self.front]
        self.front = (self.front + 1) % self.max_size
        self.count -= 1
        return item

    def peek(self):
        if self.count == 0:
            return None
        return self.queue[self.front]

    def is_empty(self):
        return self.count == 0

    def is_full(self):
        return self.count == self.max_size

Worked example: circular queue trace

Queue size 4 (indices 0 to 3). Watch the final enqueue(E) wrap the rear to 0.

Operation	Array	front	rear	count
Initial	[_, _, _, _]	0	-1	0
enqueue(A)	[A, _, _, _]	0	0	1
enqueue(B)	[A, B, _, _]	0	1	2
enqueue(C)	[A, B, C, _]	0	2	3
dequeue() → A	[_, B, C, _]	1	2	2
dequeue() → B	[_, _, C, _]	2	2	1
enqueue(D)	[_, _, C, D]	2	3	2
enqueue(E)	[E, _, C, D]	2	0	3

On the last step $(3 + 1) \bmod 4 = 0$(3+1)mod4=0, so E is stored at index 0 — the slot freed earlier by removing A. The circular queue has reused space the linear queue would have wasted.

Exam Tip: Circular-queue trace tables are a favourite OCR task. Always show front, rear and count after each operation, and write out the $\bmod$mod calculation explicitly on the step where a pointer wraps — that working is itself worth marks.

Why count (or a spare slot) is needed

There is a subtlety worth knowing: in a circular queue, the full and empty states can produce the same pointer configuration (front and rear adjacent), so the pointers alone cannot distinguish them. The two standard fixes are to keep an explicit count (used above), or to leave one slot permanently empty so "full" and "empty" never coincide. Keeping a count is the clearer approach for the exam and is why the pseudocode tests count == MAX_SIZE and count == 0 rather than comparing pointers.

Linked-list implementation (the dynamic alternative)

A queue need not use an array at all. Built on a linked list with two pointers — a head for the front and a tail for the rear — both operations are $O(1)$O(1) and there is no fixed capacity to overflow:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedQueue:
    def __init__(self):
        self.head = None       # front: dequeue here
        self.tail = None       # rear: enqueue here

    def enqueue(self, item):
        new_node = Node(item)
        if self.tail is None:           # empty queue
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node   # link new node on at the rear
            self.tail = new_node        # tail now points at it

    def dequeue(self):
        if self.head is None:
            raise IndexError("Queue Empty")
        item = self.head.data
        self.head = self.head.next      # advance the front
        if self.head is None:           # queue just became empty
            self.tail = None
        return item

This is precisely the "tail pointer" trick from the linked-lists lesson: keeping a reference to the last node makes enqueue (insert-at-rear) $O(1)$O(1), while dequeue (remove-from-front) is $O(1)$O(1) as always. The trade-off versus the circular array is the familiar static-vs-dynamic one: the linked queue grows without limit and wastes no space, but spends a pointer per item and is less cache-friendly. Choose the circular array when the maximum size is known and bounded (a buffer of fixed capacity); choose the linked list when the size is unbounded or unpredictable.

---

Priority Queue

A priority queue attaches a priority to each item and dequeues the highest-priority item, regardless of arrival order. It therefore breaks strict FIFO — though ties are usually broken in FIFO order, so it can be seen as FIFO within each priority level.

Feature	Standard queue	Priority queue
Order out	FIFO (oldest first)	Highest priority first
enqueue	add at rear	place by priority
dequeue	remove front	remove highest priority

Implementation approaches and their complexity

Approach	enqueue	dequeue	Note
Sorted list	$O(n)$O(n) — find insertion point	$O(1)$O(1) — take the front	Cost paid on insert
Unsorted list	$O(1)$O(1) — append	$O(n)$O(n) — scan for highest	Cost paid on remove
Binary heap	$O(\log n)$O(logn)	$O(\log n)$O(logn)	Best for large, busy queues

There is no free lunch: a sorted list makes removal cheap but insertion dear; an unsorted list does the reverse; a heap balances both at $O(\log n)$O(logn), which is why real priority queues are usually heap-based. (The heap structure itself is explored further with trees; here you need the trade-off table and the idea, not the heap algorithms.)