# Stacks

> Computer Science · CIE A-Level 9618
> Source: https://www.owlsprep.com/study/cie-9618-u10-stacks/

This module covers the structure, properties and operations of the stack abstract data type. You will learn about common implementations and practical applications of stacks, including expression processing for CIE 9618 exams.

**Prerequisites:** [Arrays](https://www.owlsprep.com/study/cie-9618-u10-arrays/); [Linked Lists](https://www.owlsprep.com/study/cie-9618-u10-linked-lists/); [Abstract Data Types](https://www.owlsprep.com/study/cie-9618-u10-abstract-data-types/)

## Learning objectives

- Describe the structure and core properties of a stack data structure
- Implement push, pop and peek operations for array and linked-list stacks
- Recognise and handle stack overflow and underflow errors
- Apply stacks to common problems including postfix expression evaluation

## Stack Structure and Core Properties

**Stack** — A linear abstract data type (ADT) where all insertions (push) and deletions (pop) are performed at the same end, called the *top of the stack*. The opposite fixed end is called the base.

*Example:* A real-world analogy is a stack of plates: you can only add or remove the top plate

The defining rule for stacks is **Last-In-First-Out (LIFO)** order. This means the last item added to the stack is always the first item that can be removed. This property makes stacks ideal for tasks that require reversing order or undoing recent operations.

> **mnemonic**
>
> LIFO = Last In First Out: the last item you put in is the first item you take out, just like a stack of cafeteria plates.

**Worked example:** A stack is initially empty. Show the state of the stack after each operation: `push(5)`, `push(12)`, `pop()`, `push(7)`, `peek()`

1. 1. After `push(5)`: Stack has one item, top = 5. Stack: `[5 (top/base)]`
2. 2. After `push(12)`: New item added to top. Stack: `[5 (base), 12 (top)]`
3. 3. After `pop()`: Top item 12 is removed. Stack returns to `[5 (top/base)]`
4. 4. After `push(7)`: New top is 7. Stack: `[5 (base), 7 (top)]`
5. 5. `peek()` returns 7, the stack remains unchanged.

## Stack Implementations

Stacks can be implemented using two common approaches: fixed-size arrays or dynamic linked lists. Each has different trade-offs for performance, memory usage, and error conditions.

**Comparing methods**

Key differences between the two implementations:

- **Array-based Stack** — Uses a contiguous array to store stack items, with an integer `top` pointer tracking the index of the current top. Fixed maximum capacity defined at initialization.
  - Pros: Constant O(1) time for all operations; Low memory overhead
  - Cons: Risk of overflow if stack exceeds capacity; Potential wasted memory for small stacks

- **Linked-list Stack** — Each node stores a stack item and a pointer to the next node below the current top. The `top` pointer points to the first node in the list.
  - Pros: Dynamic size, grows/shrinks as needed; No fixed capacity limit
  - Cons: Higher memory overhead for node pointers; Slightly slower access than arrays

**Worked example:** Write pseudocode for the push operation on a fixed-size array-based stack, including error handling.

1. 1. First, define the stack structure: an array `stack` of size `maxSize`, and `top` initialized to -1 (indicates empty stack).
2. 2. Check if the stack is full before adding the new item:
3. $$top = maxSize - 1$$
4. 3. If full, output an overflow error and exit. If not, increment the top pointer, then assign the new value to the array at the new top index.
5. 4. Final pseudocode:
```
PROCEDURE push(value)
  IF top = maxSize - 1 THEN
    PRINT "Overflow Error"
  ELSE
    top = top + 1
    stack[top] = value
  ENDIF
ENDPROCEDURE
```

## Common Applications of Stacks

The LIFO property of stacks makes them useful for many core computer science tasks, including:

- Function call stacks: store return addresses, local variables and parameters for nested function calls
- Backtracking: undo recent operations when exploring paths (e.g. maze solving, puzzle games)
- Expression evaluation and conversion: process infix, prefix and postfix mathematical expressions
- Undo functionality: store edits to reverse when the user presses undo in text editors

**Worked example:** Evaluate the postfix expression `3 4 + 2 *` using a stack, show the stack after each step.

1. 1. Initialize empty stack, process each token left to right.
2. 2. Token = 3: push 3 → Stack: [3]
3. 3. Token = 4: push 4 → Stack: [3, 4]
4. 4. Token = +: pop two values, calculate result, push result. Pop 4, pop 3, 3 + 4 = 7 → Stack: [7]
5. 5. Token = 2: push 2 → Stack: [7, 2]
6. 6. Token = *: pop 2, pop 7, 7 * 2 = 14 → Stack: [14]
7. 7. End of expression: result is the top value = 14

## Exam Expectations

**Exam command terms**

Common command terms for stack questions in CIE 9618 have these specific expectations:

- **Describe** — Explain structure and properties, always reference LIFO order *(Describe why a stack is suitable for function calls)*

- **Implement** — Write pseudocode for operations, including error handling for overflow/underflow *(Implement a pop operation for a linked-list stack)*

- **Evaluate** — Show stack state after each step to get the final result *(Evaluate the postfix expression 5 3 - 2 *)*

**Check your understanding**

Test your understanding of core stack concepts:

1. Which order do stacks follow?

   - First In First Out
   - Last In First Out
   - Random Access
   - Sorted Order

   *Answer:* Last In First Out

   *Why:* Correct! FIFO is the order for queues, not stacks.

2. What error occurs when popping from an empty stack?

   - Overflow
   - Underflow
   - Null Pointer
   - Index Out of Bounds

   *Answer:* Underflow

   *Why:* Correct! Overflow occurs when pushing to a full stack, underflow for empty stacks.

## Common pitfalls

- **Wrong:** Pop operands in the wrong order when evaluating postfix expressions
  - Why it fails: Candidates often pop the first operand first, leading to wrong results for subtraction and division
  - Correct: Always pop the second operand first, then the first operand: `result = firstOperand op secondOperand`
- **Wrong:** Initialize the top pointer to 0 for an empty array-based stack
  - Why it fails: This leaves the first array slot unused and causes incorrect overflow checking
  - Correct: Initialize `top = -1` for an empty stack, increment after checking for overflow
- **Wrong:** Claim linked-list stacks never run out of memory
  - Why it fails: While they have no fixed capacity, they still fail if all system memory is exhausted
  - Correct: State linked-list stacks are dynamically sized and avoid fixed-capacity overflow, but can still run out of memory
- **Wrong:** Add or remove items from the base of the stack
  - Why it fails: Candidates often confuse stacks with queues and modify the wrong end of the structure
  - Correct: All insertions and deletions must only happen at the top of the stack
- **Wrong:** Forget to handle overflow/underflow in implementation questions
  - Why it fails: Examiners expect error checking for edge cases, which is frequently missed
  - Correct: Always include overflow checks on push and underflow checks on pop

## Cheatsheet

| Property | Array-based Stack | Linked-list Stack |
| --- | --- | --- |
| Ordering | LIFO | LIFO |
| Push/Pop Time | O(1) | O(1) |
| Capacity | Fixed maximum | Dynamic |
| Overflow Risk | Yes (fixed size) | Only if no memory left |
| Memory Overhead | Low | High (per-node pointers) |

## What's next

Stacks are one of the most fundamental abstract data types, and you will encounter them repeatedly in advanced topics from recursion to operating systems memory management. Mastering stack properties and operations is critical for answering both theory and programming questions in CIE 9618. Next, you will explore queues, another linear data structure that follows a different FIFO ordering rule, before moving on to more complex non-linear structures like trees and graphs. Stacks also underpin recursion, so a solid understanding will make learning that topic much easier.

- [Queues](https://www.owlsprep.com/study/cie-9618-u10-queues/)
- [Linked Lists](https://www.owlsprep.com/study/cie-9618-u10-linked-lists/)
- [Trees](https://www.owlsprep.com/study/cie-9618-u10-trees/)

---

From [OwlsPrep](https://www.owlsprep.com) — free study guides for A-Level, IB, AP and IGCSE, written against the official syllabus. Canonical page: https://www.owlsprep.com/study/cie-9618-u10-stacks/