Loading…
Free A-Level Computer Science guide
Choose the correct end for each operation, trace the remaining values, and explain what happens when a structure is empty or full.
Content owner: Michael Print · Written for A-Level learners · Checked against official specifications
A stack follows last in, first out (LIFO): the most recently added item is removed first. A queue follows first in, first out (FIFO): the earliest item still waiting is removed first.
Push and pop both use a stack's top. Enqueue adds at a queue's rear; dequeue removes from its front. Peek reads the next item to be removed without removing it.
You will identify each operation, trace mixed additions and removals, and distinguish an empty structure from a full one. The Python example assumes you can read a list, an if statement and a function with a return value.
These are foundations for the next A-Level workshop. Work through the diagrams before the code, then try the questions without looking at their solutions.
A, then B, then C arrive. Each diagram shows the state before any removal.
| Operation | Effect | Check first |
|---|---|---|
| Push | Add at the stack top | Not full, if capacity is fixed |
| Pop | Remove and return the stack top | Not empty |
| Stack peek | Read the top; leave it in place | Not empty |
| Enqueue | Add at the queue rear | Not full, if capacity is fixed |
| Dequeue | Remove and return the queue front | Not empty |
| Queue peek | Read the front; leave it in place | Not empty |
An undo history is a useful stack model: undo the latest saved action first. A simple print queue is a FIFO model: process jobs in arrival order. A system that chooses by priority uses a different ordering rule.
Worked example
Both structures start empty. In the table, the stack is written bottom → top; the queue is written front → rear. A dash means no returned value.
| Step | Stack operation | Stack after | Stack return | Queue operation | Queue after | Queue return |
|---|---|---|---|---|---|---|
| 1 | push(A) | [A] | — | enqueue(A) | [A] | — |
| 2 | push(B) | [A, B] | — | enqueue(B) | [A, B] | — |
| 3 | push(C) | [A, B, C] | — | enqueue(C) | [A, B, C] | — |
| 4 | peek() | [A, B, C] | C | peek() | [A, B, C] | A |
| 5 | pop() | [A, B] | C | dequeue() | [B, C] | A |
| 6 | push(D) | [A, B, D] | — | enqueue(D) | [B, C, D] | — |
| 7 | pop() | [A, B] | D | dequeue() | [C, D] | B |
Step 4 changes neither structure. At step 7, the stack returns the new arrival D; the queue returns B, which has waited longest among its remaining items.
This program follows the trace. It uses a Python list as the stack and collections.deque as the queue. Each reading or removal function checks for an empty container before accessing it.
from collections import deque
def pop_stack(stack):
if not stack:
raise IndexError("Cannot pop an empty stack")
return stack.pop()
def peek_stack(stack):
if not stack:
raise IndexError("Cannot peek at an empty stack")
return stack[-1]
def dequeue(queue):
if not queue:
raise IndexError("Cannot dequeue an empty queue")
return queue.popleft()
def peek_queue(queue):
if not queue:
raise IndexError("Cannot peek at an empty queue")
return queue[0]
stack = []
queue = deque()
for item in ["A", "B", "C"]:
stack.append(item) # Push at the top.
queue.append(item) # Enqueue at the rear.
print("Peek:", peek_stack(stack), peek_queue(queue))
print("Remove:", pop_stack(stack), dequeue(queue))
stack.append("D")
queue.append("D")
print("Remove:", pop_stack(stack), dequeue(queue))
print("Remaining:", stack, list(queue))
while stack:
pop_stack(stack)
try:
pop_stack(stack)
except IndexError as error:
print(error)Peek: C A
Remove: C A
Remove: D B
Remaining: ['A', 'B'] ['C', 'D']
Cannot pop an empty stackFor the stack, append pushes and pop() removes the last item; [-1] reads it. For the queue, append enqueues and popleft() dequeues; [0] reads the front. The final loop empties the stack so the error handler can demonstrate an attempted pop with no items left.
Empty means no items are available. Removing or peeking must fail or report that condition. Full means a fixed capacity has been reached. An addition must then be rejected rather than overwriting an item. These are often called underflow and overflow respectively.
The program above has no chosen maximum size. Its list and deque can grow as memory permits, so it has no exam-style full test. A question using a fixed array needs explicit capacity checks and pointer updates.
Suppose the array indices are 0, 1 and 2. Here top means the index of the last occupied position and starts at -1.
top == -1. Do not read the array at that index.top == capacity - 1, which is 2 here.top, then store the new value at that index.top, then decrease top and return the saved value.top without changing it.Some questions define top as the next free position instead. Use the question's convention before choosing a test or update order. In a circular queue that tracks an item count, empty is count == 0 and full is count == capacity; front and rear indices wrap around to reuse positions.
Setting deque(maxlen=3) does not automatically model a queue that rejects overflow: appending when it is full discards an item from the opposite end. A fixed-capacity exercise must enforce its required behaviour explicitly. See Python's deque documentation.
These four original practice questions are worth 16 marks in total. State which end your written sequence starts from. Suggested marking is indicative.
An empty stack receives push(4), push(8), pop(), push(9) and peek(). State the two returned values, explain the effect of peek, and give the final stack from bottom to top.
Indicative answer: The first pop returns 8 (1). After pushing 9, peek returns 9 (1) without removing it (1). The final stack is [4, 9], bottom → top (1).
An empty queue receives enqueue("Red"), enqueue("Blue"), dequeue(), enqueue("Green"), peek() and dequeue(). State all three returned values in order and the final queue from front to rear.
Indicative answer: The first dequeue returns Red (1). Peek then returns Blue (1). The next dequeue also returns Blue (1), leaving [Green], front → rear (1).
Choose a stack or a queue for each requirement and justify your choice: undo saved edits in reverse order; process waiting tasks strictly in their arrival order.
Indicative answer: Use a stack for undo (1), because the latest saved action should be undone first, following LIFO (1). Use a queue for the tasks (1), because the earliest waiting task must be processed first, following FIFO (1).
An initially empty fixed stack has capacity 5. Its top is the last occupied index and begins at -1. State top after five pushes, explain what should happen on a sixth push, and give the guard and response needed for a pop from an empty stack.
Indicative answer: After five pushes, top is 4 (1). A sixth push must be rejected because top == capacity - 1 (1). Before popping, check top != -1 (1); when it is -1, report underflow without accessing or changing the stack (1).
Source check: . OCR AS H046 explicitly covers stack and queue properties in 1.4.2(b) and their representation, addition and removal in 2.3.1(e). Check your qualification's specification for the required implementation detail.
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.