Study Guide

Stacks

Computer ScienceΒ· 6 min read

1. Stack Structure and Core Propertiesβ˜…β˜…β˜†β˜†β˜†β± 15 min

πŸ“˜ Definition

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.

πŸ“ 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
    1. After push(5): Stack has one item, top = 5. Stack: [5 (top/base)]
  2. 2
    1. After push(12): New item added to top. Stack: [5 (base), 12 (top)]
  3. 3
    1. After pop(): Top item 12 is removed. Stack returns to [5 (top/base)]
  4. 4
    1. After push(7): New top is 7. Stack: [5 (base), 7 (top)]
  5. 5
    1. peek() returns 7, the stack remains unchanged.

2. Stack Implementationsβ˜…β˜…β˜…β˜†β˜†β± 20 min

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.

Methods compared

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
    1. First, define the stack structure: an array stack of size maxSize, and top initialized to -1 (indicates empty stack).
  2. 2
    1. Check if the stack is full before adding the new item:
  3. 3
    top=maxSizeβˆ’1top = maxSize - 1
  4. 4
    1. 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. 5
    1. Final pseudocode:
    PROCEDURE push(value)
  IF top = maxSize - 1 THEN
    PRINT "Overflow Error"
  ELSE
    top = top + 1
    stack[top] = value
  ENDIF
ENDPROCEDURE

3. Common Applications of Stacksβ˜…β˜…β˜…β˜†β˜†β± 20 min

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
    1. Initialize empty stack, process each token left to right.
  2. 2
    1. Token = 3: push 3 β†’ Stack: [3]
  3. 3
    1. Token = 4: push 4 β†’ Stack: [3, 4]
  4. 4
    1. Token = +: pop two values, calculate result, push result. Pop 4, pop 3, 3 + 4 = 7 β†’ Stack: [7]
  5. 5
    1. Token = 2: push 2 β†’ Stack: [7, 2]
  6. 6
    1. Token = *: pop 2, pop 7, 7 * 2 = 14 β†’ Stack: [14]
  7. 7
    1. End of expression: result is the top value = 14

4. Exam Expectationsβ˜…β˜…β˜†β˜†β˜†β± 10 min

βœ“ Quick check

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

    Reveal answer
    1 β€”

    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

    Reveal answer
    1 β€”

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

5. Common Pitfalls

Wrong move:

Pop operands in the wrong order when evaluating postfix expressions

Why:

Candidates often pop the first operand first, leading to wrong results for subtraction and division

Correct move:

Always pop the second operand first, then the first operand: result = firstOperand op secondOperand

Wrong move:

Initialize the top pointer to 0 for an empty array-based stack

Why:

This leaves the first array slot unused and causes incorrect overflow checking

Correct move:

Initialize top = -1 for an empty stack, increment after checking for overflow

Wrong move:

Claim linked-list stacks never run out of memory

Why:

While they have no fixed capacity, they still fail if all system memory is exhausted

Correct move:

State linked-list stacks are dynamically sized and avoid fixed-capacity overflow, but can still run out of memory

Wrong move:

Add or remove items from the base of the stack

Why:

Candidates often confuse stacks with queues and modify the wrong end of the structure

Correct move:

All insertions and deletions must only happen at the top of the stack

Wrong move:

Forget to handle overflow/underflow in implementation questions

Why:

Examiners expect error checking for edge cases, which is frequently missed

Correct move:

Always include overflow checks on push and underflow checks on pop

6. Quick Reference 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)

C

o

m

m

o

n

E

r

r

o

r

s

W

r

o

n

g

t

o

p

i

n

i

t

i

a

l

i

z

a

t

i

o

n

,

o

v

e

r

f

l

o

w

U

n

d

e

r

f

l

o

w

,

l

o

s

t

t

o

p

p

o

i

n

t

e

r

When this came up on past exams

AI-estimated based on syllabus patterns β€” cross-check with official past papers for accuracy. Use only as revision-focus signals.

  • 2022 Β· 12

    Stack implementation and core operations

  • 2023 Β· 13

    Postfix expression evaluation with stacks

  • 2024 Β· 11

    Stack implementation comparison

Going deeper

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.