Stacks in Data Structures

Data Structures: Stacks

“Programs must be written for people to read, and only incidentally for machines to execute.” — Harold Abelson. This insight hits harder when you think about how we organise data. In fact, research shows that 70% of performance bottlenecks in software systems come from poor handling of data structures.

One of the simplest yet most powerful structures you’ll encounter is the stack. It follows a Last In, First Out (LIFO) principle. That’s not just a computer science term — it’s a behaviour that shapes how function calls work, how you undo an action in Word, and even how browsers let you move back and forth between pages.

In this lesson, we’ll strip away the complexity and get hands-on with stacks. You’ll see how stack operations work, how to trace them step by step, and why they matter in the real world. We’ll also walk through Python implementations and a practical example: converting infix expressions to postfix.

If you’re an IT student or a developer looking to strengthen your algorithm foundation, this lesson is your roadmap. By the end, you won’t just understand stacks — you’ll know how to use them effectively in coding problems and system design. Let’s dive in!

Learning Outcomes

By the end of this lesson on Data Structures: Stacks, you should be able to:

• Define what a stack is and explain how the LIFO principle works.
• Perform and trace stack operations step by step.
• Identify real-world applications where stacks are applied, from undo features to browser navigation.
• Implement stacks in Python using both arrays and linked lists.
• Apply stacks in expression conversion, particularly turning infix into postfix.

Consider This: As you read, try connecting each learning outcome to something you’ve already experienced in coding or daily computer use. The more you relate it to your world, the easier it sticks.

Core Concepts of Stacks

A. Stack Operations

A stack works with a defined set of operations that make its LIFO (Last In, First Out) behaviour clear:

• push(item) → adds an element on top of the stack
• pop() → removes the element from the top
• peek() → shows the top element without removing it
• isEmpty() → checks if the stack is empty
• isFull() → checks if the stack is at maximum size (for fixed stacks)

Consider This: Why is it important that only the top element can be accessed in a stack?

B. Representations of a Stack

Stacks can be implemented in two common ways:

• Array-based implementation – uses a fixed-size array and a top pointer to track the last element. Simple but limited by size.
• Linked-list implementation – each element is stored in a node pointing to the next, allowing dynamic growth and shrinkage. More flexible but needs extra memory for pointers.

Consider This: Which implementation would you prefer if the stack will grow and shrink frequently?

C. Tracing the Stack

Tracing helps you see how a stack changes step by step as operations are performed. Follow the example below:

Operations:

• push(10)
• push(20)
• push(30)
• pop()
• push(40)

Activity: Trace the stack after performing the following sequence: push(A), push(B), push(C), pop(), push(D). Write down the stack content after each step.

Where Stacks Matter in Real Work

Stacks power real systems you use every day. Short rules. Big impact on performance and reliability.

1) Function Calls and Recursion (Call Stack)

Each function call is pushed onto the call stack with its local variables and return address. When it returns, it’s popped.

• Why it matters: Debugging stack traces, preventing stack overflow, understanding recursion depth.
• Action: Step through a recursive function and watch the stack frames grow and shrink.

2) Undo / Redo Systems

Editors keep actions in stacks. Undo pops from the “done” stack; redo pushes to a “redo” stack.

• Why it matters: Reliable user experience and reversible operations.
• Action: Model two stacks: done and redo. Try sequences: type → undo → redo.

3) Browser Navigation

Navigation uses two stacks: Back and Forward. Clicking a link pushes to Back. Going back pops to Forward.

• Why it matters: Predictable navigation history.
• Action: Simulate with arrays and verify Back/Forward after multiple clicks.

4) Expression Handling (Infix → Postfix)

Compilers and calculators use stacks to reorder operators and evaluate expressions without parentheses.

• Why it matters: Deterministic evaluation and simpler interpreters.
• Action: Convert (A + B) * C to postfix. Evaluate it with a value stack.

5) Parsing and Validation

Use a stack to validate balanced parentheses or nested HTML/XML tags.

• Why it matters: Safe input handling and correct syntax parsing.
• Action: Write a function that returns true only when every ( has a matching ) in order.

6) Backtracking Algorithms

Depth-first search, maze solvers, and puzzle engines push choices onto a stack and pop to backtrack.

• Why it matters: Efficient exploration of state spaces.
• Action: Implement DFS with an explicit stack instead of recursion and compare behavior.

7) Systems and OS Internals

Interrupt handling and context switching use stacks to store CPU state quickly and restore it safely.

• Why it matters: Stable, responsive systems.
• Action: Read a stack trace from a crash log and map frames to source lines.

Consider This: Pick one area above and outline how a data structures: stacks approach improves correctness or performance in your current project.

Converting Infix to Postfix with Stacks

A. What is Infix and Postfix?

In an infix expression, operators are placed between operands. Example: (A + B) * C. In a postfix expression, operators come after operands. Example: AB+C*. Postfix makes evaluation easier because it doesn’t need parentheses or operator precedence rules.

B. Why Convert?

Computers and compilers prefer postfix. It eliminates ambiguity and allows evaluation using a simple stack-based algorithm.

C. Conversion Rules

• Operands → add directly to the output.
• Operators → push onto the stack. Pop higher or equal precedence operators first.
• Left parenthesis ( → push onto the stack.
• Right parenthesis ) → pop from stack until a left parenthesis is found.
• At the end → pop all remaining operators into the output.

D. Example 1 – (A + B) * C

Final Postfix: AB+C*

E. Example 2 – A + B * C

Final Postfix: ABC*+

Activity – Practice Conversion

• Convert (A + B) * (C - D) to postfix.
• Convert A * (B + C) / D to postfix.
• Convert (A + B + C) * D to postfix.

Consider This: What advantage does postfix provide when designing an interpreter or calculator compared to infix?

Python Implementation of Stacks

A. Array-Based Stack (Python List)

Use a Python list to model a fixed-capacity stack. It’s fast and simple for most problems.

# stack_array.py
class Stack:
    def __init__(self, capacity: int):
        self._data = []
        self._cap = capacity

    def push(self, item):
        if len(self._data) >= self._cap:
            raise OverflowError("stack overflow")
        self._data.append(item)

    def pop(self):
        if not self._data:
            raise IndexError("stack underflow")
        return self._data.pop()

    def peek(self):
        return self._data[-1] if self._data else None

    def is_empty(self) -> bool:
        return len(self._data) == 0

    def __repr__(self):
        # top on the right
        return f"Stack({self._data})"


if __name__ == "__main__":
    s = Stack(3)
    s.push(10); s.push(20); s.push(30)
    print(s)           # Stack([10, 20, 30])
    s.pop()
    s.push(40)
    print(s)           # Stack([10, 20, 40])

Activity: Add a size() method and log the stack after each operation. How will you handle capacity growth if you need it?

Consider This: When is a fixed capacity a feature rather than a limitation?

B. Linked-List Stack (Dynamic Size)

Use nodes to avoid a fixed limit. This suits workloads with unknown or variable depth.

# stack_linked.py
class Node:
    __slots__ = ("data", "next")
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

class Stack:
    def __init__(self):
        self._top: Node | None = None
        self._size = 0

    def push(self, item):
        self._top = Node(item, self._top)
        self._size += 1

    def pop(self):
        if self._top is None:
            raise IndexError("stack underflow")
        item = self._top.data
        self._top = self._top.next
        self._size -= 1
        return item

    def peek(self):
        return self._top.data if self._top else None

    def is_empty(self) -> bool:
        return self._top is None

    def size(self) -> int:
        return self._size

    def __repr__(self):
        vals = []
        cur = self._top
        while cur:
            vals.append(cur.data)
            cur = cur.next
        # top first for clarity
        return f"StackTopFirst({vals})"


if __name__ == "__main__":
    s = Stack()
    for x in (10, 20, 30): s.push(x)
    print(s)            # StackTopFirst([30, 20, 10])
    s.pop(); s.push(40)
    print(s)            # StackTopFirst([40, 20, 10])

Activity: Implement clear() and __len__. Compare time and space behavior with the array-based version for 1e6 operations.

Consider This: What trade-offs do you accept when you choose pointers over contiguous arrays?

C. Mini Task — Palindrome Check with a Stack

Push characters onto the stack, then pop to build a reversed string and compare.

# palindrome_stack.py
from typing import Iterable

class Stack:
    def __init__(self): self._d = []
    def push(self, x): self._d.append(x)
    def pop(self): return self._d.pop()
    def is_empty(self): return len(self._d) == 0

def is_palindrome(text: str) -> bool:
    # normalize: alphanumerics, lowercased
    cleaned = "".join(ch.lower() for ch in text if ch.isalnum())
    s = Stack()
    for ch in cleaned:
        s.push(ch)
    reversed_s = []
    while not s.is_empty():
        reversed_s.append(s.pop())
    return cleaned == "".join(reversed_s)

if __name__ == "__main__":
    for sample in ("madam", "racecar", "hello", "A man, a plan, a canal: Panama"):
        print(sample, "=>", is_palindrome(sample))

Activity: Extend the function to return the first index where the comparison fails.

D. Mini Task — Trace Every Operation

Add lightweight tracing to observe LIFO behavior in real time.

# traced_stack.py
class TracedStack:
    def __init__(self):
        self._d = []

    def _show(self, op, val=None):
        tag = f"{op}({val})" if val is not None else op
        print(f"{tag:10} -> {self._d}")

    def push(self, x):
        self._d.append(x)
        self._show("push", x)

    def pop(self):
        if not self._d:
            raise IndexError("underflow")
        v = self._d.pop()
        self._show("pop", v)
        return v

    def peek(self):
        v = self._d[-1] if self._d else None
        print(f"peek({v})  -> {self._d}")
        return v

if __name__ == "__main__":
    s = TracedStack()
    s.push(10); s.push(20); s.push(30)
    s.pop(); s.push(40); s.peek()

Consider This: Where would tracing help you most: debugging recursion, expression handling, or undo/redo logic?

Summary and Assessment

Key Takeaways

• Data Structures: Stacks enforce a clear rule: LIFO—last in, first out.
• Core stack operations are small but decisive: push, pop, peek, and state checks.
• Two solid implementations: array-based (simple, capacity-bound) and linked-list (dynamic, pointer cost).
• Real impact in production: call stacks, undo/redo, browser navigation, parsing, and backtracking.
• Stacks make infix → postfix conversion predictable and easy to evaluate.
• Python gives you both a quick list-based stack and a clean linked-list version for deeper control.

Consider This: Where will a stack replace ad-hoc lists in your current code to make it safer and easier to reason about?

Assessment — Apply What You Learned

push(5), push(8), pop(), push(12), push(15), pop(), push(9)
    

For quick review, revisit the core stack operations, the infix to postfix table, and the Python implementations. These patterns show up across algorithms and production systems—often where correctness matters most.