Loading…
Free A-Level Computer Science guide
Move from collection methods to the array implementation. Learn what each pointer means before tracing operations, especially when the queue reaches the end of its storage.
Content owner: Michael Print · Written for A-Level learners · Checked against official specifications
A fixed stack uses top as the index of its latest item. Here top starts at −1, so an empty stack has top −1 and a full stack of capacity C has top C−1. Push checks space then increments top; pop checks for an item then removes at top and decrements it.
This circular queue uses front for the next removal, rear for the next insertion and count for the number of stored items. Advance either pointer with (pointer + 1) % capacity. Count separates empty from full because front and rear can be equal in both states.
OCR H446 · 1.4.2(b–c), 2.3.1(e): array-based stack and queue operations
Useful foundations
By the end, you should be able to
Use one convention consistently. Some books make rear the last occupied slot; here it is the next insertion slot. Changing convention changes the update rules.
Indexes are zero-based. A queue starts with front=rear=count=0; a three-slot array uses indexes 0,1,2.
A stack’s active segment is 0…top. Snapshot shows it bottom to top; its last value will be popped next. Cleared None slots help inspection, but top or count determines membership.
Constructors require positive integer capacity. Zero has no usable slot and makes modulo undefined. All slots are allocated at creation; push and enqueue do not grow capacity.
Check before changing state. Full-stack push raises OverflowError before top moves. Empty-stack pop raises IndexError before an array read. Another agreed status contract is possible; overwriting active data or returning arbitrary values is not.
Enqueue checks count==capacity, writes at rear, advances rear and increments count. Dequeue checks count==0, reads/clears front, advances front and decrements count.
Use (pointer + 1) % capacity to advance either queue pointer. Valid updates keep pointers inside the array and count within 0…capacity.
Circular queues reuse freed slots without shifting surviving items. Physical array order can therefore differ from FIFO order.
Traverse count positions from front with (front + offset) % capacity. Starting at physical index zero gives storage order; stopping only at rear fails when a full queue has equal pointers.
Snapshot leaves items and state unchanged. It takes O(k) for k active items; push, pop, enqueue and dequeue each take O(1) in this fixed-array model. Both structures reserve O(C) storage even when empty.
Fill A, B, C
Physical [A,B,C]; front=0, rear=0, count=3. Equal pointers mean full here.
Remove A
Slot 0 is free. front=1, rear=0, count=2.
Add D
Write at slot 0: physical [D,B,C]; front=1, rear=1, count=3.
Read FIFO order
Follow indexes 1,2,0 to see B,C,D. Count distinguishes this full state from empty.
Worked example
| Line | Output |
|---|---|
| 1 | 7 [4] |
| 2 | A |
| 3 | ['B', 'C', 'D'] |
| 4 | 1 1 3 |
| 5 | ['B', 'C', 'D'] |
| 6 | 1 1 0 |
class FixedStack:
def __init__(self, capacity):
if capacity < 1:
raise ValueError("positive capacity required")
self.data = [None] * capacity
self.top = -1
def push(self, value):
if self.top == len(self.data) - 1:
raise OverflowError("stack full")
self.top += 1
self.data[self.top] = value
def pop(self):
if self.top == -1:
raise IndexError("stack empty")
value = self.data[self.top]
self.data[self.top] = None
self.top -= 1
return value
def snapshot(self):
return self.data[:self.top + 1]
class CircularQueue:
def __init__(self, capacity):
if capacity < 1:
raise ValueError("positive capacity required")
self.data = [None] * capacity
self.front = self.rear = self.count = 0
def enqueue(self, value):
if self.count == len(self.data):
raise OverflowError("queue full")
self.data[self.rear] = value
self.rear = (self.rear + 1) % len(self.data)
self.count += 1
def dequeue(self):
if self.count == 0:
raise IndexError("queue empty")
value = self.data[self.front]
self.data[self.front] = None
self.front = (self.front + 1) % len(self.data)
self.count -= 1
return value
def snapshot(self):
return [self.data[(self.front + i) % len(self.data)]
for i in range(self.count)]
stack = FixedStack(2)
stack.push(4)
stack.push(7)
print(stack.pop(), stack.snapshot())
queue = CircularQueue(3)
for value in ["A", "B", "C"]:
queue.enqueue(value)
print(queue.dequeue())
queue.enqueue("D")
print(queue.snapshot())
print(queue.front, queue.rear, queue.count)
print([queue.dequeue() for _ in range(3)])
print(queue.front, queue.rear, queue.count)Worked example
5 original questions total 23 marks. Attempt each before opening the independently written indicative marking guidance.
A capacity-three stack starts empty. Trace push(8), push(2), pop(), push(5). Give both the popped value and the final top and bottom-to-top snapshot.
Indicative answer
A capacity-four queue starts empty. Enqueue P, Q, R; dequeue twice; enqueue S, T, U. Give the final FIFO order, front, rear and count.
Indicative answer
Explain why front == rear cannot distinguish full from empty in this queue. State the correct two tests.
Indicative answer
The physical queue storage is [M, None, J, K], front = 2, rear = 1 and count = 3. Give the snapshot and the state after one dequeue.
Indicative answer
A full capacity-one queue contains X. Explain the required behaviour of enqueue(Y), then dequeue(), then another dequeue(), including whether the failed operations change state.
Indicative answer
This guide addresses OCR H446 1.4.2(b–c), 2.3.1(e): array-based stack and queue operations. Check your examination year and the complete specification for the assessment scope.
These are independently written explanations and practice questions. CompSciTutoring.co.uk is not affiliated with or endorsed by an examination board. The marking guidance is indicative; always check the syllabus for your examination year.
Found an error? Email a correction.
Use the free examples first, then explore one-to-one tuition if guided practice would help.