Python Chapter 8.5 — linear, linked and circular queues

Exam recall

FIFO; enqueue rear, dequeue front. Write pointer meanings and empty/full rules before code. Test wrap, last removal, refill and display without mutation.

Understand the behaviour before the code priority/high

A queue is first in, first out (FIFO): enqueue adds at the rear; dequeue removes/returns the front; peek reads the front. A queue suits jobs served in arrival order. A stack would serve the newest job first.

Think of orders A, B and C arriving in that order. Serving A leaves B first and C last; a new order D joins behind C. The operations preserve arrival order. How an array or linked nodes store those orders is a separate implementation decision.

Exam-ready definition

A queue is an abstract data type with first-in, first-out behaviour: items are added at the rear and removed from the front.

For a two-part justification, connect the rule to the scenario: “A queue serves the earliest unserved order first, preserving customers’ arrival order. A stack would serve the most recently added order first.”

Why a circular array is useful priority/medium

Implementation	How removal works	Main issue
Shifting array/list	Remove front and move later elements left	Moving many elements costs work.
Non-wrapping linear array	Advance front	Vacated cells before front cannot be reused once rear reaches the end without resetting/moving.
Circular array	Advance indices modulo capacity	Requires consistent full/empty state rules.
Linked queue	Move front to its next node	Extra link memory; handle rear carefully when last node is removed.

Linear array: derive the limitation priority/high

Linear queue cannot reuse a front gap until emptied under its reset-only policy

Contract: capacity is a positive integer; front indexes the next item to remove, rear the last inserted item. Do not wrap or shift. Reclaim the entire array only after the queue becomes empty. Return False for an enqueue that cannot be accommodated; raise IndexError for empty dequeue.

class LinearQueue:
    def __init__(self, capacity):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self.data = [None] * capacity
        self.front = 0
        self.rear = -1
 
    def enqueue(self, item):
        if self.rear == len(self.data) - 1:
            return False
        self.rear += 1
        self.data[self.rear] = item
        return True
 
    def dequeue(self):
        if self.front > self.rear:
            raise IndexError("queue empty")
        item = self.data[self.front]
        self.data[self.front] = None
        self.front += 1
        if self.front > self.rear:
            self.front = 0
            self.rear = -1
        return item

What wrapping around means priority/high

In an array of capacity 4, indices are 0,1,2,3. The next index after 3 is 0, computed by (3 + 1) % 4. This reuses space freed by dequeue; it does not move surviving items or overwrite a full queue.

Physical indices:     0   1   2   3
After A,B,C,D:        [A] [B] [C] [D]  front=0 rear=3 size=4
Dequeue A then B:     [ ] [ ] [C] [D]  front=2 rear=3 size=2
Enqueue E then F:     [E] [F] [C] [D]  front=2 rear=1 size=4
Logical FIFO order:   C → D → E → F

The queue is circular in the way indices are used, not because Python allocates a ring-shaped list. Modulo gives a valid next index for every position:

flowchart LR
    A[Index 0] --> B[Index 1]
    B --> C[Index 2]
    C --> D[Index 3]
    D -->|wrap using modulo 4| A

After E and F are inserted, reading indices 0,1,2,3 would incorrectly report E,F,C,D. Start at front=2 and visit four live positions: 2,3,0,1 → C,D,E,F. Neither moving pointers nor wrapping changes which customer arrived first.

School comparison of linear and circular array queues

Source: Data Structures, PDF p.36. The lower figure shows rear advancing from index 5 to 0; the existing front stays at 2.

Derive the state and operations priority/high

Here front is the next item to remove; rear is the most recently inserted index; size counts live items. Initially front=0, rear=−1, size=0. Empty: size is 0. Full: size equals capacity. This uses all array cells and does not reserve an empty slot.

State	Meaning you must preserve
`front`	Index from which the next successful dequeue reads.
`rear`	Index written by the most recent successful enqueue; initially −1 so its first advance reaches 0.
`size`	Number of live items, from 0 to capacity inclusive.

Enqueue: reject if full → advance rear to the next free position → store the item → increase size. Check first: advancing or writing before rejecting could corrupt a full queue.

Dequeue: reject if empty → save the item at front → advance front → decrease size → return the saved item. Save first: reading after advancing would return the next customer’s order.

Display: use a temporary index or offset to visit exactly size items from front. Do not change front or rear: displaying the queue is not serving customers.

Worked code with purposeful comments

This teaching interface returns a Boolean for enqueue, returns an item for successful dequeue and raises IndexError on empty dequeue. These are interface choices, not universal queue rules. In an exam, use the question’s requested language and failure result.

class CircularQueue:
    def __init__(self, capacity):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self.data = [None] * capacity
        self.front = 0       # Next position to read when nonempty.
        self.rear = -1       # First enqueue advances this to index 0.
        self.size = 0        # Counts live items, not allocated cells.
 
    def enqueue(self, item):
        if self.size == len(self.data):  # Reject before changing state.
            return False
        self.rear = (self.rear + 1) % len(self.data)  # Wrap at the end.
        self.data[self.rear] = item
        self.size += 1
        return True
 
    def dequeue(self):
        if self.size == 0:
            raise IndexError("queue empty")
        item = self.data[self.front]     # Save the value before advancing.
        self.data[self.front] = None     # Clear unused storage for clarity.
        self.front = (self.front + 1) % len(self.data)
        self.size -= 1
        return item
 
    def peek(self):
        if self.size == 0:
            raise IndexError("queue empty")
        return self.data[self.front]     # Read without changing the queue.
 
    def items(self):
        result = []
        for offset in range(self.size):  # Visit live items only.
            index = (self.front + offset) % len(self.data)
            result.append(self.data[index])  # front/rear stay unchanged.
        return result

items() follows logical order without changing state. A loop over the entire physical array would give the wrong order after wrapping and may include unused cells. This interface returns False for a full enqueue and raises on empty dequeue; always match the paper’s requested return convention.

Trace the smallest cases by hand

For capacity=4, the first enqueue writes index 0: front 0, rear 0, size1. Dequeue saves that item, advances front to 1 and makes size 0. The next enqueue advances rear from 0 to 1, so front and rear correctly meet at the newly occupied cell. This count-based design does not need to reset pointers when empty. Its size records emptiness.

For capacity=1, modulo always produces index 0. A first enqueue succeeds, a second is rejected, dequeue empties it, and refill succeeds. This is a useful check that your full/empty logic is based on state rather than assumptions about distinct pointer positions.

Adapt to a different convention priority/high

HCI 2024 Q7 starts with start=end=−1, without the size convention above. For a usual sentinel implementation: empty means start == -1; full means (end+1)%capacity == start; first enqueue sets both to 0; normal enqueue advances end modulo capacity. On dequeue, if start == end, removing that one remaining item resets both to −1; otherwise advance start. Do not mix a size-based empty test with an unmaintained size or forget the sentinel reset. An alternative design reserves an unused cell and uses different tests; derive tests from the provided representation.

Why does the full test work? With no free gap, the next position after the last live item is already occupied by the first live item. Advancing end would overwrite it. With the empty sentinel, −1 is distinguishable from every live array index, so the design can use all cells without a separate count.

Detail	Count-based teaching code	HCI 2024 sentinel convention
Empty test	`size == 0`	`start == -1`
Full test	`size == capacity`	`(end+1) MOD capacity == start`
Last item removed	Decrease size to 0; ordinary pointer advance	Reset both start and end to −1
One live item	`size == 1`; `front == rear`	`start == end` and start is not−1

Matching the paper matters more than remembering one template. HCI 2024 requests pseudocode and False on empty serve; the teaching Python’s exception would not match that specified interface.

Linked queue priority/high

Maintain front and rear node references. Enqueue into empty sets both to new. Otherwise connect rear.next to new and move rear. Dequeue saves front.data, moves front to front.next, and if front becomes None, sets rear to None. Forgetting that last step leaves rear pointing at a removed node. A linked queue has no fixed-array capacity unless one is explicitly imposed, but memory remains finite.

Before: front → [A | next] → [B | None] ← rear
Remove A: front becomes B; rear still refers to B.
Remove B: front becomes None; rear must also become None.
Add C: both front and rear refer to the new C node.

Linked nodes avoid a fixed preallocated array limit, but require extra links and do not offer direct indexed access to the kth queued item. Compare the stated implementations, rather than claiming a linked queue is always better.

Exam focus: analyse before writing

HCI 2024 Q7 tests circular enqueue, dequeue, non-destructive display and FIFO justification. HCI 2025 Q6 tests a linked queue and its state changes. These are concrete reasons to practise both representations.

Before writing an operation, annotate the question with: storage → pointer meanings → empty/full test → required return/output → special transition. Then trace one normal case and the relevant boundary case on paper.

Common mistakes

Using front == rear as an empty test in a convention where it means one item; overwriting before checking full; advancing before saving the removed value; returning instead of printing when output is requested; using dequeue to display and therefore destroying the queue; and forgetting to reset linked rear after the final removal.

Practice

21A — adapted from HCI 2024 Q7. Using the count-based implementation above with capacity 4: enqueue A,B,C,D; dequeue twice; enqueue E,F. Give the two removed values, physical array, logical order, front, rear and size. What happens when enqueue G is attempted?

21B — adapted from HCI 2025 Q6. Using Node from Chapter 19, implement LinkedQueue with enqueue, dequeue and items. Raise IndexError for empty dequeue. Trace enqueue X, dequeue, enqueue Y, stating front/rear after each stage.

21C — adapted from VJC 2025 filename Paper1 Q3, extra practice. priority/low An ordinary queue initially contains jobs [101,102,103,104] front-to-rear. Dequeue twice, then enqueue105 and106. Give the resulting order. Using only a temporary stack and queue operations, reverse the queue’s contents. Explain why moving queue→stack→queue reverses order and why doing it twice restores order.

Hints

21A: array order is not FIFO order after wrapping. 21B: test one-to-empty, then refill. 21C: pop reverses the sequence of pushes.

21D — original paper, HCI 2024 Q7, 14 marks. priority/high Open the complete question, PDF p.4. Attempt all four parts in its original wording. It supplies only orders, start and end; requests pseudocode for order(food), serve() and printQueue(); and specifies the success/failure behaviour. Before solving it, write three differences between its interface and the count-based Python example above. Preserve its capacity of eight and its initial −1 pointers.

21E — original, linear versus circular. Capacity 3: enqueue A,B,C; dequeue A; attempt enqueue D in the illustrated linear queue. Then dequeue B,C and enqueue D again. Give each result and pointer state. Explain what the circular queue would do after the first dequeue.

Revision checklist

Visual revision mindmap

Chapter 21 revision mindmap

Open this mindmap and its text version · All 21 mindmaps

Your mindmap framework

Centre: Python Chapter 8.5 — linear, linked and circular queues. Build the six branches below. For each subbranch, add a short definition, a labelled sample and one exam trap from memory; then check the chapter.

flowchart LR
    C["21 • Revision map"]
    C --> B0["Queue contract"]
    C --> B1["Implementation choices"]
    C --> B2["Count-based circular state"]
    C --> B3["Sentinel and linked state"]
    C --> B4["Derive the operations"]
    C --> B5["Visual checks and mistakes"]

Queue contract
- FIFO.
- Enqueue rear; dequeue/remove front.
- Peek reads; display preserves state.
- Arrival-order justification versus LIFO.
Implementation choices
- Shifting list: move remaining items.
- Linear array: no wrap; stated reset/reclamation policy.
- Circular array: wrap indices to reuse vacancies.
- Linked queue: node links and extra pointer memory.
Count-based circular state
- Front = next read index; rear = last inserted index.
- Initially front 0, rear −1, size 0.
- Empty size 0; full size = capacity.
- Advance modulo capacity; size distinguishes empty/full.
Sentinel and linked state
- HCI sentinel: start/end initially −1.
- Full when next end equals start.
- Sentinel last removal resets both indices.
- Linked last removal sets both front and rear to None.
Derive the operations
- Enqueue: check → advance/link → store → update state.
- Dequeue: check → save → advance/unlink → reset if needed.
- Display: temporary index/reference through live order.
- Queue → stack → queue reverses; check mutation contract.
Visual checks and mistakes
- Draw physical cells above logical FIFO arrows.
- Trace empty → one → full → wrap → empty → refill.
- Test capacity 1 and non-mutating display.
- Avoid: front = rear always empty; mix conventions; forget linked rear reset.

Close the notes and test the map: explain one branch aloud, sketch its sample, then answer a linked practice question. Mark any missing link to revisit.

Source trail

9569 §2.1.1; school Data Structures pp.31–39, ending at circular queue and relevant Tutorial 8C.

HCI 2024 Q7 (circular array); HCI 2025 Q6 (linked queue).

Source guide records provenance and original-paper locations.

Quartz 5

Explorer

21 Python Chapter 8.5 — linear, linked and circular queues

Python Chapter 8.5 — linear, linked and circular queues

Understand the behaviour before the code priority/high

Why a circular array is useful priority/medium

Linear array: derive the limitation priority/high

What wrapping around means priority/high

Derive the state and operations priority/high

Worked code with purposeful comments

Trace the smallest cases by hand

Adapt to a different convention priority/high

Linked queue priority/high

Exam focus: analyse before writing

Practice

Revision checklist

Visual revision mindmap

Your mindmap framework

Source trail

Graph View

Table of Contents

Backlinks