Community resourceWorksheet

OCR H446 2.3.1 Stack and queue algorithms

Part 9 of 16 · H446 2.3.1 · Algorithms

Here H446 2.3.1 algorithm work meets the structures from 1.4.2: push, pop, enqueue and dequeue, all of which depend on stated pointer conventions before a trace can be marked. The worksheet is the longest in the series because students both trace circular wrap-around and implement the operations, including the overflow and underflow checks.

Students will:

  • state head, tail, top and count conventions before performing any operation
  • trace a circular queue across a wrap-around, giving the state after each operation
  • explain why a circular dequeue should not shift the remaining items
  • implement array stack push and pop, and circular queue enqueue and dequeue
  • diagnose faulty operation order and the effect of calling a helper twice

Inside: 6 explanation cells, 1 multiple-choice question, 1 fill-in-the-blanks cell, 2 written answers, 2 Python tasks and 1 trace table. 37 marks, about 45 to 70 minutes.

Series: H446 2.3.1 · Algorithms, part 9 of 16.

Shared by Coding PathwayVerified teacher

  • 13 cells
  • About 60 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.

Stack and queue algorithms

This worksheet applies algorithms to the structures from 1.4.2. State pointer conventions before tracing.

By the end, you will be able to

  • read, trace and write push/pop and enqueue/dequeue;
  • preserve LIFO/FIFO behaviour;
  • perform overflow/underflow checks in the correct order;
  • explain why array queue items need not shift.

Reactivate: next-free stack top and circular queue head/tail/count.

Worked model: operation ends and invariants

Stack and queue operation endsStack: LIFOC ← top itemBApush/popQueue: FIFOABCfront / dequeuerear / enqueueBoundary checks occur before changing pointers or returning.

Stack pop with next-free top: check top > 0, decrement, then return. Circular enqueue: check count < capacity, write at tail, advance tail modulo capacity, increment count. Circular dequeue reads head, advances head and decrements count; no shifting is required.

A supplied queue may use a different convention. If rear starts at -1 and is incremented before storage, the first item occupies index 0 and the hundredth item occupies index 99; index 100 is outside a 100-slot array. Follow the supplied helper contract rather than silently replacing its convention.

Multiple choice1 mark

Why should a circular-array dequeue not shift every remaining item?

  • APointers identify the logical front and rear without movement
  • BFIFO requires reverse order
  • CA queue has no capacity
  • DModulo deletes values
Trace table4 marks

Trace wrap-around and count.

Enter a value only when it changes. Record output in 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. data = ["A","B","",""]
  2. head = 0
  3. tail = 2
  4. count = 2
  5. for item in ["C","D"]:
  6. data[tail] = item
  7. tail = (tail+1)%len(data)
  8. count = count+1
  9. print(tail)
  10. print(count)
Trace table with 6 columns
RowdataheadtailcountitemOutput
1
2
3
4
5
6
Written answer7 marks

For a capacity-4 queue with head=3, tail=1, count=2 and logical items X,Y, apply enqueue Z, dequeue, enqueue W. Give state after each operation.

Draw indexes and apply modulo.

Students type their answer here.

Independent transfer

Implement push and pop for an array stack. top is next free. Return updated top from push, or -1 on overflow. pop returns (value,new_top), or (None,top) on underflow.

Coding task8 marks
def push(data, top, value):
    pass

def pop(data, top):
    pass

Independent transfer: write circular queue operations

Use a fixed array with tail pointing to the next free location, head pointing to the next item to remove, and count distinguishing empty from full. enqueue returns (new_tail, new_count, success). dequeue returns (value, new_head, new_count). Check the boundary before reading or writing, and advance a pointer with modulo only after a successful operation.

Coding task10 marks
def enqueue(data, tail, count, value):
    pass

def dequeue(data, head, count):
    pass
Written answer7 marks

Diagnose two errors: pop returns before decrementing top; dequeue removes from the rear because it is 'the latest item'. Then a supplied enqueue helper returns (new_rear, success): explain why calling it once in the IF condition and again to capture the rear is unsafe, and show a single call whose returned values control the decision.

Link each error to the broken invariant, then preserve the supplied helper contract and its returned state.

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 stack removes in completion 1 order; a queue removes in completion 2 order. Attempting to remove from an empty structure is completion 3. Attempting to add to a full fixed array is completion 4.

Review your understanding

Before submitting, check that you can explain the central distinction in your own words, expose the intermediate state that supports your answer and apply the method in an unfamiliar context.