CAIE 9618 · Paper 4 · Topic 4.3.1

Stacks &
Queues

ADT Concepts · LIFO Stack · FIFO Queue · Push/Pop/Peek · Enqueue/Dequeue · Array Implementation

CSZone Cambridge International AS & A Level Computer Science 9618

Stack — LIFO

Last In, First Out

OPERATIONS

Push(item) — add item to the TOP; increment TopPointer

Pop() — remove and return TOP item; decrement TopPointer

Peek() / Top() — return TOP item WITHOUT removing it

IsEmpty() — TRUE if TopPointer = 0 (or -1)

IsFull() — TRUE if TopPointer = MaxSize

Stack overflow — Push onto full stack

Stack underflow — Pop from empty stack

REAL USES

Call stack (function calls), undo/redo, browser back button, expression evaluation (RPN), syntax checking (matching brackets)

After Push(10), Push(20), Push(30):

TOP →

30

20

10

BOTTOM

Pop() returns 30 (LIFO)

ARRAY IMPLEMENTATION

Array Stack[1..MaxSize] + TopPointer integer.
Push: TopPointer ← TopPointer + 1; Stack[TopPointer] ← item
Pop: item ← Stack[TopPointer]; TopPointer ← TopPointer - 1

Queue — FIFO

First In, First Out

OPERATIONS

Enqueue(item) — add item to the REAR; increment RearPointer

Dequeue() — remove and return FRONT item; increment FrontPointer

IsEmpty() — TRUE if FrontPointer > RearPointer

IsFull() — TRUE if RearPointer = MaxSize

CIRCULAR QUEUE

Standard queue wastes space when FrontPointer advances. Circular queue wraps around: RearPointer = (RearPointer MOD MaxSize) + 1. Reuses freed slots at the front. Better memory utilisation.

After Enqueue(A), Enqueue(B), Enqueue(C):

FRONT →

A

B

C

...

← REAR

Dequeue() returns A (FIFO)

REAL USES

CPU job scheduling (ready queue), printer spooler, network packet buffers, BFS graph traversal, message queues (Kafka, RabbitMQ)

Exam Practice

Cambridge-style questions

Question 1

A stack initially contains [5, 12, 8] where 8 is at the top. Trace the following operations and state the final state of the stack:
Pop(); Push(3); Push(7); Pop(); Peek(). [4]

1

Pop() removes 8 → stack is [5, 12], returns 8. Top is now 12.

1

Push(3) → stack is [5, 12, 3]. Push(7) → stack is [5, 12, 3, 7]. Top is now 7.

1

Pop() removes 7 → stack is [5, 12, 3], returns 7.

1

Peek() returns 3 (the current top element) WITHOUT removing it. Final stack: [5, 12, 3] with 3 at top.

Common Mistakes

Don't lose easy marks

1

Confusing the order — LIFO (stack): the LAST item pushed is the FIRST to be popped. FIFO (queue): the FIRST item enqueued is the FIRST to be dequeued. In trace questions, always check which end you're adding/removing from.

2

Saying Peek() removes the item — Peek() (sometimes called Top()) returns the top item WITHOUT removing it. Pop() removes it. The distinction matters in trace questions and implementation questions.

3

Not checking for overflow/underflow before push/pop — in pseudocode, always check IsFull() before Push and IsEmpty() before Pop/Dequeue. CAIE mark schemes look for this defensive check in implementation questions.

Topic Summary — 4.3.1

What You Need to Know

STACK (LIFO)

Push (add top), Pop (remove top), Peek (read top). TopPointer tracks top. Overflow = push full stack. Underflow = pop empty stack. Uses: call stack, undo, bracket checking.

QUEUE (FIFO)

Enqueue (add rear), Dequeue (remove front). FrontPointer + RearPointer. Circular queue reuses space. Uses: CPU scheduling, printer spooler, BFS.

IMPLEMENTATION

Both can be implemented with arrays + pointer variable(s). Linked list alternative avoids fixed-size limit. Always check full/empty before operations.

CSZone

Next Video

4.3.2

Linked Lists

Nodes · Pointers · Insert · Delete · Traversal

Head to CSZone.co.uk for the complete worksheet, quiz, and interactive tools