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: 7 explanation cells, 1 multiple-choice question, 1 fill-in-the-blanks cell, 2 written answers, 1 Python task and 1 trace table. 19 marks, about 45 to 55 minutes.

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

Shared by Coding PathwayVerified teacher

  • 13 cells
  • About 45 minutes
  • CC BY-SA 4.0
  • Shared 31 Aug 2026
  • Updated 3 Sept 2026

Preview

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

Queues and circular arrays

A ticket-support queue serves the oldest waiting request first. A queue is FIFO: First In, First Out.

By the end, you will be able to

  • enqueue and dequeue using head/tail pointers;
  • model circular wraparound;
  • distinguish empty and full states;
  • explain why efficient queues do not shift all items.

Reactivate: modulo returns a remainder and can wrap an index.

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
  • CMoving every remaining item adds unnecessary work; pointers can identify the front
  • DThe head must always equal zero
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

Track head, tail, count and returned value after dequeue, enqueue E, enqueue F. Never infer empty/full from stale array contents; pointer/count state controls logical membership.

Written answer6 marks

Starting with capacity 4, head=2, tail=0, count=2 and logical queue [A,B] at indexes 2,3, apply enqueue(C), dequeue(), enqueue(D). Give final head, tail, count and FIFO order.

Wrap pointers with modulo 4.

Students type their answer here.

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):
    pass
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 responses

Check every response against its command word and the supplied constraints. Strengthen unsupported answers with accurate method, mechanism, state or contextual consequence before submitting.