Community resourceWorksheet

OCR H446 1.4.2 Queues and circular arrays

Part 4 of 14 · H446 1.4.2 · Data structures

A support queue that serves the oldest waiting request first is the entry point to the first in, first out half of H446 1.4.2. This worksheet takes students through head, tail and count state in a circular array, where wraparound and the difference between empty and full are settled by the pointers rather than by what the array still holds.

Students will:

  • enqueue and dequeue using head, tail and count together
  • model wraparound in a circular array and tell an empty queue from a full one
  • explain why shifting every remaining item after a dequeue is inefficient
  • implement an enqueue that rejects a full queue and updates state only on success
  • judge where strict first in, first out is unsuitable, such as emergency-priority requests

Inside: 8 explanation cells, 1 multiple-choice question, 2 fill-in-the-blanks cells, 1 written answer, 2 Python tasks and 1 trace table. 24 marks, about 50 to 60 minutes.

Series: H446 1.4.2 · Data structures, part 4 of 14.

Shared by Coding PathwayVerified teacher

  • 15 cells
  • About 60 minutes
  • CC BY-SA 4.0
  • Shared 31 Aug 2026
  • Updated 1 Oct 2026

Preview

The whole resource, exactly as a class sees it. Answers and marking are held back.

Queues and circular arrays

A queue removes the item that has waited longest. This behaviour is called first in, first out (FIFO). A ticket-support system can use it to serve ordinary requests in arrival order.

By the end, you will be able to

  • enqueue and dequeue using head and tail pointers;
  • use modulo arithmetic to wrap around a circular array;
  • distinguish empty and full states;
  • explain why an efficient queue does not shift every stored item.

Circular state

Circular queue pointersemptyBCDempty01234head = 1tail = 4After index 4, modulo arithmetic returns the next pointer to index 0; items do not shift.

Here head points to the next item to remove and tail points to the next free space. A separate count distinguishes empty from full when head = tail. Increment using (pointer + 1) MOD capacity.

Worked operations

State: B,C,D occupy indexes 1–3; head=1, tail=4, count=3.

  • dequeue returns B, head becomes 2, count becomes 2.
  • enqueue E stores at index 4; tail wraps to 0; count becomes 3.
  • enqueue F stores at index 0; tail becomes 1; count becomes 4.

The stored values remain in their slots; only pointers move.

Multiple choice1 mark

Why is shifting all queue items after each dequeue inefficient?

  • AFIFO requires reversed data
  • BQueues cannot use arrays
  • CThe head must always equal zero
  • DMoving every remaining item adds unnecessary work; pointers can identify the front
Trace table4 marks

Trace enqueue operations and pointer wraparound.

Enter a value only when it changes. Follow pointers and output in execution order.

Use one row for each pass through the loop. Fill in a box only when that value changes on that row, and leave the rest blank.

ProgramPython
  1. queue = ["", "", "", ""]
  2. tail = 3
  3. count = 0
  4. for item in ["X", "Y"]:
  5. queue[tail] = item
  6. tail = (tail + 1) % 4
  7. count = count + 1
  8. print(tail)
  9. print(queue)
Trace table with 5 columns
RowqueuetailcountitemOutput
1
2
3
4
5
6

Guided state table

Start with capacity 4, head=2, tail=0, count=2 and logical queue A, B at indexes 2 and 3. Use modulo 4 when a pointer reaches the end.

Fill in the blanks6 marks
OperationheadtailcountReturnedLogical FIFO order
enqueue(C)2entry 13noneA, B, C
dequeue()entry 212entry 3B, C
enqueue(D)3entry 4entry 5noneentry 6

Independent transfer: implement enqueue

Return (new_tail, new_count, success). Reject when count equals capacity. Mutate the supplied array only on success.

Coding task5 marks
def enqueue(data, tail, count, item):
    if count == len(data):
        return tail, count, False

    data[tail] = item
    # Move tail to the next free position and wrap if needed.
    tail = ...
    count = ...
    return tail, count, True

Apply the opposite operation: implement dequeue

Complete dequeue(data, head, count). Return a three-item tuple containing the removed value, the updated head and the updated count. On underflow, return (None, head, count). Values do not need to be erased from the array because head and count define the logical queue.

Coding task5 marks
def dequeue(data, head, count):
    if count == 0:
        return None, head, count

    value = ...
    head = ...
    count = ...
    return value, head, count
Written answer3 marks

Explain why FIFO suits ordinary support requests but may be unsuitable for emergency-priority requests.

Develop both behaviour and consequence.

Students type their answer here.

Closed-book checkpoint

Complete each sentence from memory. There is no answer bank and correctness is held for teacher review.

Fill in the blanks4 marks
A queue is completion 1. Enqueue adds at the completion 2 and dequeue removes from the completion 3. A circular array uses completion 4 to wrap a pointer, while count distinguishes full from empty when pointers coincide.

Review your work

Check that head, tail and count still describe the queue after every operation.