B2.2.3 · Data structures
The stack (LIFO)
By the end you can
Trace push, pop, peek, overflow, and underflow on a Last-In, First-Out stack and explain call stack and undo applications.
A is a linear data structure that operates under theLast-In, First-Out (LIFO) principle. Just like a physical stack of plates in a cafeteria, items can only be added or removed from a single access point: the top.
Core stack operations#
- push(item): Adds a new element onto the top of the stack. If the stack is implemented using a fixed-size array and is full, this triggers a stack overflow error.
- pop(): Removes and returns the element currently residing at the top. If the stack contains no elements, attempting to pop triggers a stack underflow error.
- peek() / top(): Inspects the top item without modifying or removing it.
- isEmpty(): Returns
trueif the stack count is zero, preventing underflow exceptions. - isFull(): For static/bounded implementations, returns
truewhen capacity is reached.
Stack initialised with 3 items. Capacity is 6.
Base of Stack (Index 0)
Why stacks matter in computer systems#
The stack is central to low-level computer architecture and software design:
- The Call Stack: When a function executes, the CPU allocates a stack frame storing parameters, return addresses, and local variables. When the function returns, its frame is popped. Excessive nested recursion without reaching a base case exhausts call stack memory, causing the famous “StackOverflowError”.
- Undo Buffers: Every user action (typing a letter, pasting an image) is pushed onto an undo stack. Pressing Ctrl+Z pops the most recent action and reverses it.
- Syntax & Bracket Matching: Compilers push opening brackets
(,[,{onto a stack. When a closing bracket is encountered, the stack is popped; if the brackets do not match or the stack is empty, a syntax error is raised.
Check yourself
Stacks
Quick questions, made fresh every time and marked here. Do a few until they feel easy.
Exam practice
Paper 1-style questions
3 questions · 9 marks
Write your answer as you would in the exam, then show the mark points and tick each one your answer made. These are our own questions in the style of the exam, not past-paper questions.
1.Describe the LIFO principle of a stack and explain the operations push, pop, peek, and isEmpty.
[4]Describe: A detailed account: say what happens, step by step if it is a process.
2.Explain what causes stack overflow and stack underflow errors.
[2]Explain: Give reasons: say what happens AND why, or how one thing causes another.
3.State three practical applications of stacks in computer systems.
[3]State: Give a short answer, no explanation needed.
In a nutshell
- A stack is a linear data structure operating under the Last-In, First-Out (LIFO) principle.
- Core operations include push (insert at top), pop (remove from top), peek (inspect top), and isEmpty.
- Stack overflow occurs when pushing to a full capacity stack; stack underflow occurs when popping an empty stack.
- Stacks power subroutine call stack frames, undo/redo buffers, and bracket matching in compilers.