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.
Stack Last in, first out: items are pushed onto and popped off the same end, and one pointer marks the top.
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
Key terms for this topic — skim now; the Check step will test them.
- 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.
- Queue
A queue is an Abstract Data Type (ADT) that stores a collection of elements, with the principal operations being Enqueue (add to rear) and Dequeue (remove from front). It follows the First-In, First-Out (FIFO) principle.
- LIFO
Last-In, First-Out. The last element added to the data structure is the first one to be removed. This is the defining characteristic of a stack.
- FIFO
First-In, First-Out. The first element added to the data structure is the first one to be removed. This is the defining characteristic of a queue.
- 'push' operation
The operation to add a new element to the top of a stack.
- 'pop' operation
The operation to remove and return the element from the top of a stack.
- 'enqueue' operation
The operation to add a new element to the rear (end) of a queue.
- 'dequeue' operation
The operation to remove and return the element from the front (start) of a queue.
- Stack underflow error
An error that occurs when attempting to 'pop' an element from an empty stack. It's a common runtime error to watch for.
- Queue overflow error
An error that occurs when attempting to 'enqueue' an element into a full queue, especially when the queue is implemented with a fixed-size array.
Name it
Read the meaning, then pick which of this lesson’s terms it describes. Miss one and you see what your choice really means.
Ais an Abstract Data Type (ADT) that stores a collection of elements, with the principal operations being Enqueue (add to rear) and Dequeue (remove from front). It follows the First-In, First-Out (FIFO) principle.
Quick check
Write your answer first, then compare it with the model one — the gap is what you would have lost.
Teach it back
If you can explain it simply, you own it — gaps here are marks you’d lose.
Teach it back
Explain this topic as if teaching a friend. We name the gaps an examiner would still dock.
Revision flashcards
Guess first, then flip — retrieval beats re-reading.
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.
Discuss Stacks, queues and the application of data structures
Ask, share and discuss with other Computer Science HL students