Learning Objectives
By the end of this topic you will be able to:
Describe a stack and its LIFO behaviour, with push, pop and peek operations
Describe a queue and its FIFO behaviour, with enqueue and dequeue operations
Explain real-world applications of stacks and queues
Describe a circular queue and explain its advantage over a linear queue
Stack Applications
Real Uses of Stacks
Call stack: when a function is called, the return address and local variables are pushed onto the call stack. When the function returns, they are popped. This is how the computer knows where to resume execution.
Undo functionality: each action is pushed onto a stack. Pressing Ctrl+Z pops the most recent action and reverses it. This is a direct application of LIFO.
Expression evaluation: stacks are used to evaluate reverse Polish notation (RPN) expressions and to check that brackets/parentheses are balanced in code.
Back/Forward navigation: web browsers maintain a back stack and a forward stack for the history of visited pages.
Queues
The Queue — FIFO
A queue is a linear data structure following First In, First Out (FIFO). Items are added at the rear (enqueue) and removed from the front (dequeue). Like a real-world queue — first person in line is served first.
Queue Operations
Enqueue(x): add x to rear
Dequeue(): remove and return front item
Peek(): return front without removing
isEmpty(): True if queue is empty
Queue Applications
• Print spooler (jobs wait in order)
• CPU scheduling (processes wait)
• Keyboard input buffer
• Breadth-first graph traversal
• Network packet queuing
Circular Queue
Circular Queue
In a linear queue, once the rear reaches the end of the array, no more items can be added even if spaces have been freed at the front — wasted memory. A circular queue treats the array as a circle: the rear pointer wraps around to the beginning of the array when it reaches the end.
Front and rear pointers both move forward. When they reach the array limit, they wrap to index 0. The queue is full when (rear + 1) mod size = front; empty when front = rear.
Circular queues are more memory-efficient and are used in operating systems (CPU scheduling) and network buffers where continuous reuse of fixed memory is essential.
Exam Practice
OCR H446 Style · 4 marks
A stack is initially empty. The following operations are performed: PUSH 5, PUSH 3, PUSH 8, POP, PUSH 2, POP, POP. Show the state of the stack after each operation and give the values returned by each POP.
[4 marks]
1
PUSH 5: [5] · PUSH 3: [5,3] · PUSH 8: [5,3,8]
1
POP → returns 8; stack: [5,3]
1
PUSH 2: [5,3,2] · POP → returns 2; stack: [5,3]
1
POP → returns 3; stack: [5]
Common Mistakes
Don't Lose Marks
!
Saying stacks are FIFO — stacks are LIFO (Last In, First Out). Queues are FIFO. These are the defining properties. Mixing them up is one of the most common errors and will lose marks in any question about either structure.
!
Describing the operation for removing from a queue as Pop — the correct term for a queue is Dequeue. Pop is specific to stacks. OCR mark schemes use precise terminology: push/pop for stacks, enqueue/dequeue for queues.
!
Not explaining why a circular queue is better — just saying "it wraps around" is not enough. You must explain that a linear queue wastes space at the front when items are dequeued, and the circular queue reuses that space by wrapping the rear pointer.