In simple terms
A friendly intro before the formal notes — no formulas yet.
Orderly Piles and Patient Lines
Stacks and queues are simple but powerful ways to organise data. A stack is like a pile of plates where you can only take the top one, while a queue is like a line at a shop where the first person to arrive is the first to be served.
Imagine you're at a cafeteria. The stack of clean trays is a perfect example of a stack. You take the top tray, which was the last one placed on the pile (Last-In, First-Out). Now, think about the line for the food. You join at the back and wait your turn. The person at the front of the line, who arrived first, gets served first (First-In, First-Out). This is a queue. In computing, we use these same principles to manage tasks, data, and processes in an orderly fashion.
- 1
First, let's look at a stack. We'll use the 'push' operation to add items, which pile up on top of each other.
- 2
Now, we'll use the 'pop' operation. Notice how the last item we pushed is the first one to be removed. This is the LIFO principle.
- 3
Next, consider a queue. We'll 'enqueue' items, which join the back of the line.
- 4
When we 'dequeue', the item at the front of the line is removed. This demonstrates the FIFO principle, essential for fairness in processing tasks.
Explore the concept
Use the live diagram and synced steps — play it or tap a step card to walk through.
Full topic notes
Formal explanation with the rigour you need for the exam.
Stacks: The LIFO Principle
A stack is a data collection that operates on a Last-In, First-Out (LIFO) basis. Think of it as a vertical pile. You can only add items to the top and you can only remove items from the top. This makes stacks useful for situations where you need to reverse order or handle nested operations, like function calls.
Principle: Last-In, First-Out (LIFO).
Primary Operations:
- push(item): Adds an item to the top of the stack.
- pop(): Removes and returns the item from the top of the stack.
Auxiliary Operations:
- peek() or top(): Returns the top item without removing it.
- isEmpty(): Returns true if the stack has no elements.
- isFull(): Returns true if the stack is at maximum capacity (for static implementations).
Common Applications: Managing function calls (the call stack), undo/redo features, expression evaluation and conversion (e.g., infix to postfix).
Queues: The FIFO Principle
A queue models a real-world waiting line. It operates on a First-In, First-Out (FIFO) basis. New items are added to one end (the rear) and items are removed from the other end (the front). This ensures fairness and is ideal for managing resources or tasks in the order they are received.
Principle: First-In, First-Out (FIFO).
Primary Operations:
- enqueue(item): Adds an item to the rear of the queue.
- dequeue(): Removes and returns the item from the front of the queue.
Auxiliary Operations:
- peek() or front(): Returns the front item without removing it.
- isEmpty(): Returns true if the queue has no elements.
Implementation: Often uses two pointers, front and rear, to keep track of the ends of the queue, especially in an array-based implementation.
Common Applications: Print job scheduling, CPU task scheduling, handling requests on a web server, breadth-first search algorithms in graphs.
Implementation Considerations
While stacks and queues are ADTs, they must be implemented using concrete data structures. The two most common choices are arrays (static) and linked lists (dynamic). An array implementation is simple but has a fixed size, leading to potential overflow. A linked list implementation can grow and shrink as needed, avoiding overflow, but requires more memory to store pointers and can be slightly more complex to code. For queues in arrays, a 'circular queue' is often used to efficiently reuse empty space at the beginning of the array.
Worked examples
See the formulas applied — reveal one step at a time, like the exam.
A stack, with a maximum size of 4, is initially empty. The following operations are performed in sequence: PUSH(17), PUSH(22), POP(), PUSH(5), PUSH(99). Trace the contents of the stack after each operation and state the value returned by the POP operation.
- 1
Initial State: [] (empty)
A queue is implemented using a static array of size 5, indexed 0 to 4. Initially, the queue is empty, with and . Trace the state of the array and the pointers after the following operations: ENQUEUE('X'), ENQUEUE('Y'), DEQUEUE(), ENQUEUE('Z').
- 1
Initial State:
How it all connects
The big idea sits in the middle — tap a linked idea to explore the link.
Tap a linked idea to see how it connects back to the main topic — that connection is what examiners reward.
Glossary
Try to recall each definition before you reveal it.
Quick check
Answer in your head first — then tap to check. No pressure.
Revision flashcards
Flip the card. Test yourself before the exam.
What is a stack?
A stack is an Abstract Data Type (ADT) that stores a collection of elements, with the principal operations being Push (add to top) and Pop (remove from top). It follows the Last-In, First-Out (LIFO) principle.
Key takeaways
Review these before you close the topic — retrieval beats re-reading.
- ✓
Principle: Last-In, First-Out (LIFO).
- ✓
Primary Operations:
- ✓
- push(item): Adds an item to the top of the stack.
- ✓
- pop(): Removes and returns the item from the top of the stack.
- ✓
Auxiliary Operations:
- ✓
- peek() or top(): Returns the top item without removing it.
- ✓
- isEmpty(): Returns true if the stack has no elements.
- ✓
- isFull(): Returns true if the stack is at maximum capacity (for static implementations).
- ✓
Common Applications: Managing function calls (the call stack), undo/redo features, expression evaluation and conversion (e.g., infix to postfix).
Practice — then mark it
The whole point: a real Cambridge question, marked mark-by-mark.
Test Your Knowledge on Stacks & Queues
Test Your Knowledge on Stacks & Queues
Extra simulations & links
PhET, GeoGebra and other curated tools — open in a new tab.
Frequently asked
Checkpoint
One marked question is worth ten re-reads — close the loop before you move on.
Reading it isn’t knowing it — prove it.
Before you move on: do Test Your Knowledge on Stacks & Queues on paper, snap a photo, and get examiner-style feedback on exactly where you win and lose marks.