Queues

This lesson covers the queue — a fundamental abstract data type that obeys the First-In, First-Out (FIFO) rule. Queues model any situation where items are served in arrival order: print spooling, process scheduling, keyboard buffers, and the breadth-first traversal of graphs. The lesson covers the three variants you must know — linear, circular, and priority queues — and the examiner's staple task: tracing the front, rear, and count pointers through a circular queue.

Spec Mapping

This lesson addresses AQA A-Level Computer Science (7517), section 4.2.3 (Queues). It covers the FIFO model, the operations enqueue, dequeue, front/peek, isEmpty, isFull, and size, the linear array implementation and its wasted-space flaw, the circular queue with modular-arithmetic pointers, and the priority queue. It connects to breadth-first search and to the static/dynamic implementation choice (§4.2.1). Wording below is original and does not reproduce AQA specification text.

---

What is a Queue?

A queue is an ordered collection of elements in which:

• Items are added (enqueued) at the rear (back) of the queue.
• Items are removed (dequeued) from the front.
• The first item added is the first to be removed — FIFO.

The everyday analogy is a queue at a shop checkout: the first person to join is the first to be served, and new arrivals join the back. A queue therefore exposes two ends (front for removal, rear for insertion), in contrast to a stack's single top.

flowchart LR
    F["FRONT (dequeue)"] --> A["10"] --> B["20"] --> C["30"] --> D["40"] --> R["REAR (enqueue)"]

---

Queue Operations

Operation	Description	Time 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()	Read the front item without removing it	$O(1)$O(1)
isEmpty()	Test whether the queue is empty	$O(1)$O(1)
isFull()	Test whether the queue is full (array-based only)	$O(1)$O(1)
size()	Return the number of items	$O(1)$O(1)

As with a stack, all core operations are $O(1)$O(1) because they act only at the front or rear — there is never any traversal of the interior.

---

Linear Queue (Array-Based)

A linear queue uses an array with a front pointer (index of the item to dequeue next) and a rear pointer (index of the most recently enqueued item).

The Problem with Linear Queues

As items are dequeued, the front pointer advances. The slots it leaves behind at the start of the array become dead space — empty but unusable, because the rear pointer only ever moves forward. Eventually rear reaches the last index and the queue appears full even though earlier slots are free.

Initial state — front = 0, rear = 3:

Index 0	Index 1	Index 2	Index 3	Index 4
10	20	30	40	empty

After two dequeues — front = 2, rear = 3 (indices 0 and 1 are now wasted):

Index 0	Index 1	Index 2	Index 3	Index 4
wasted	wasted	30	40	empty

After one more enqueue, rear hits index 4 and the queue reports "full" — yet two slots sit idle at the front. This inefficiency is exactly what the circular queue fixes.

Traced Example: The Linear Queue's "False Full" (MAX_SIZE = 5)

Starting empty, perform: enqueue 10, 20, 30, 40, 50; dequeue (×2); enqueue 60. Watch the linear queue fail:

Operation	front	rear	Slots [0..4]	Note
enqueue 10..50	0	4	[10, 20, 30, 40, 50]	array full
dequeue → 10	1	4	[_, 20, 30, 40, 50]	slot 0 freed
dequeue → 20	2	4	[_, _, 30, 40, 50]	slot 1 freed
enqueue 60	2	4	rejected — rear already at last index	false full

There are two empty slots (0 and 1), yet the linear queue rejects 60 because rear cannot advance past index 4. A circular queue would compute $(4 + 1) \bmod 5 = 0$(4+1)mod5=0 and place 60 in slot 0, reusing the freed space. This side-by-side failure is the strongest justification for the circular design and is worth quoting in an evaluation answer.

---

Circular Queue

A circular queue treats the array as if its end joins back to its beginning — a logical ring. When a pointer reaches the last index, the next move wraps around to index 0, reusing the freed slots. The reused-space behaviour is achieved with modular arithmetic:

$\text{next position} = (\text{current position} + 1) \bmod \text{arraySize}$next position=(current position+1)modarraySize

A separate count of items distinguishes "empty" from "full", because front and rear can coincide in both situations. Concretely, imagine a 5-slot ring where, after a sequence of enqueues and dequeues, front and rear both index slot 2. Has the queue wrapped all the way round to become full, or has it been emptied so that the two pointers met in the middle? The pointer positions alone cannot tell you — only count (0 means empty, max_size means full) resolves the ambiguity. An alternative convention some implementations use is to sacrifice one slot (treat the queue as full when (rear + 1) % max_size == front), trading one wasted slot for not needing a count variable. Either way, the full-versus-empty ambiguity is the central subtlety of the circular queue.

flowchart LR
    S0["[0]"] --> S1["[1]"] --> S2["[2]"] --> S3["[3]"] --> S4["[4]"]
    S4 -- "wraps to" --> S0

Pseudocode

CONSTANT MAX_SIZE = 5
DECLARE queue : ARRAY[0..MAX_SIZE-1] OF INTEGER
DECLARE front : INTEGER = 0
DECLARE rear  : INTEGER = -1
DECLARE count : INTEGER = 0

PROCEDURE enqueue(item : INTEGER)
    IF count = MAX_SIZE THEN
        OUTPUT "Queue is full"
    ELSE
        rear = (rear + 1) MOD MAX_SIZE     // wrap if past the end
        queue[rear] = item
        count = count + 1
    ENDIF
ENDPROCEDURE

FUNCTION dequeue() RETURNS INTEGER
    IF count = 0 THEN
        OUTPUT "Queue is empty"
        RETURN -1
    ELSE
        item = queue[front]
        front = (front + 1) MOD MAX_SIZE   // wrap if past the end
        count = count - 1
        RETURN item
    ENDIF
ENDFUNCTION

Python Implementation

class CircularQueue:
    def __init__(self, max_size: int = 5):
        self.__queue = [None] * max_size
        self.__front = 0
        self.__rear = -1
        self.__count = 0
        self.__max_size = max_size

    def enqueue(self, item):
        if self.__count == self.__max_size:
            raise OverflowError("Queue is full")
        self.__rear = (self.__rear + 1) % self.__max_size   # wrap-around
        self.__queue[self.__rear] = item
        self.__count += 1

    def dequeue(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        item = self.__queue[self.__front]
        self.__front = (self.__front + 1) % self.__max_size # wrap-around
        self.__count -= 1
        return item

    def peek(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.__queue[self.__front]

    def is_empty(self) -> bool:
        return self.__count == 0

    def is_full(self) -> bool:
        return self.__count == self.__max_size

    def size(self) -> int:
        return self.__count

Traced Example: Wrapping Around (MAX_SIZE = 5)

Start empty (front = 0, rear = -1, count = 0) and perform: enqueue A, B, C, D; dequeue (×2); enqueue E, F. Watch rear wrap from 4 back to 0.

Operation	front	rear	count	Slots [0..4]
enqueue A	0	0	1	[A, _, _, _, _]
enqueue B	0	1	2	[A, B, _, _, _]
enqueue C	0	2	3	[A, B, C, _, _]
enqueue D	0	3	4	[A, B, C, D, _]
dequeue → A	1	3	3	[_, B, C, D, _]
dequeue → B	2	3	2	[_, _, C, D, _]
enqueue E	2	4	3	[_, _, C, D, E]
enqueue F	2	0	4	[F, _, C, D, E]

The final enqueue F is the key step: rear was 4 (the last index), so $(4 + 1) \bmod 5 = 0$(4+1)mod5=0 wraps it to index 0, reusing the slot freed by dequeuing A. A linear queue would have reported "full" here; the circular queue still has room (count = 4 < 5).

Exam Tip: Circular queues are a favourite exam topic. The wrap-around formula is (pointer + 1) % max_size. Trace front, rear, and count after every operation — count is what lets you tell a full queue from an empty one when the two pointers meet.

---

Priority Queue

A priority queue assigns each element a priority. Elements are dequeued in priority order — highest priority first — regardless of arrival time; elements of equal priority are served FIFO. (By a common convention, a lower numeric value means a higher priority, e.g. priority 1 outranks priority 5.)

Implementation Approaches

Approach	Enqueue	Dequeue
Unsorted array/list	$O(1)$O(1) — append	$O(n)$O(n) — scan for highest priority
Sorted array/list	$O(n)$O(n) — insert in order	$O(1)$O(1) — best is at one end
Heap (binary heap)	$O(\log n)$O(logn)	$O(\log n)$O(logn)

The unsorted and sorted options simply move the cost between enqueue and dequeue; a binary heap balances both at $O(\log n)$O(logn), which is why real priority queues (and the priority scheduler in an operating system) use heaps.

Python Example

class PriorityQueue:
    def __init__(self):
        self.__items = []   # list of (priority, data); lower number = higher priority

    def enqueue(self, item, priority: int):
        # insert so the list stays sorted by ascending priority value
        inserted = False
        for i in range(len(self.__items)):
            if priority < self.__items[i][0]:
                self.__items.insert(i, (priority, item))
                inserted = True
                break
        if not inserted:
            self.__items.append((priority, item))   # lowest priority -> the end

    def dequeue(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.__items.pop(0)[1]               # front holds the best priority

    def is_empty(self) -> bool:
        return len(self.__items) == 0

Traced Example: A Hospital Triage Priority Queue

Patients arrive with a severity priority (1 = most urgent). Using a sorted priority queue, enqueue in this order: Alice (priority 3), Bob (1), Carol (2), then dequeue twice. Each enqueue inserts the patient so the list stays in ascending-priority order:

Operation	Queue contents (front → rear), shown as (priority, name)
enqueue Alice (3)	(3, Alice)
enqueue Bob (1)	(1, Bob), (3, Alice)
enqueue Carol (2)	(1, Bob), (2, Carol), (3, Alice)
dequeue → Bob	(2, Carol), (3, Alice)
dequeue → Carol	(3, Alice)

Bob is treated first despite arriving second, because priority — not arrival order — governs dequeue. Note that Alice, the first to arrive, is treated last, which would be impossible in an ordinary FIFO queue. If two patients shared a priority, the one enqueued earlier would come out first, preserving FIFO within a priority level. This is exactly how an Accident and Emergency department triages, and how an operating system's priority scheduler chooses the next process to run.

---

Linked Implementation of a Queue

Just as a stack can be array- or linked-based, so can a queue. A linked queue keeps two external pointers — front (where items leave) and rear (where items join) — so that both enqueue and dequeue are $O(1)$O(1) with no fixed capacity and no need for the circular-buffer trick.

class LinkedQueue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue(self, data):        # O(1)
        node = Node(data)           # assume a Node class with data and next
        if self.rear is None:       # empty queue
            self.front = self.rear = node
        else:
            self.rear.next = node   # link old rear to new node
            self.rear = node        # advance rear

    def dequeue(self):              # O(1)
        if self.front is None:
            raise IndexError("Queue is empty")
        data = self.front.data
        self.front = self.front.next
        if self.front is None:      # queue is now empty
            self.rear = None
        return data

The linked queue grows until system memory is exhausted, removing the array queue's fixed-capacity overflow entirely; the cost is one pointer per node and poorer cache locality. This is the now-familiar static-vs-dynamic trade-off applied to the queue ADT, and a good answer to "how would you implement a queue with no size limit?".

---

Applications of Queues

Application	Queue type	Description
Print spooling	Linear / circular	Print jobs are serviced in submission order.
CPU / process scheduling	Priority	Higher-priority processes run first.
Breadth-first search (BFS)	Linear	Graph/tree nodes are explored level by level using a queue.
Buffering / streaming	Circular	Data is held in a fixed-size circular buffer (e.g. media playback).
Keyboard input buffer	Linear / circular	Keystrokes are processed in the order pressed.
Hospital A&E (triage)	Priority	Patients are treated by severity, not arrival time.

---

Queues and Breadth-First Search