icaoberg / Data structures - Stack

Created Sun, 03 May 2026 00:00:00 +0000 Modified Sun, 03 May 2026 09:38:21 -0400

Jupyter Notebook python

Data structures - Stack¶

A stack is a linear data structure that follows the Last-In, First-Out (LIFO) principle: the last element added is the first one removed — just like a stack of plates.

This notebook covers:

What is a Stack?
The Stack class
Core operations: push, pop, peek, is_empty, size
Example: balanced parentheses checker

1. What is a Stack?¶

Operation	Description	Time complexity
`push(item)`	Add an item to the top	O(1)
`pop()`	Remove and return the top item	O(1)
`peek()`	Return the top item without removing it	O(1)
`is_empty()`	Return `True` if the stack has no items	O(1)
`size()`	Return the number of items	O(1)

Python lists support O(1) append and pop from the right end, making them a natural backing structure for a stack.

2. The `Stack` class¶

In [1]:

class Stack:
    """LIFO stack backed by a Python list."""

    def __init__(self):
        self._data = []

    def push(self, item):
        """Add *item* to the top of the stack."""
        self._data.append(item)

    def pop(self):
        """Remove and return the top item. Raises IndexError if empty."""
        if self.is_empty():
            raise IndexError("pop from an empty stack")
        return self._data.pop()

    def peek(self):
        """Return the top item without removing it. Raises IndexError if empty."""
        if self.is_empty():
            raise IndexError("peek at an empty stack")
        return self._data[-1]

    def is_empty(self):
        """Return True if the stack contains no items."""
        return len(self._data) == 0

    def size(self):
        """Return the number of items in the stack."""
        return len(self._data)

    def __repr__(self):
        return f"Stack(top={self._data[-1]!r}, size={len(self._data)})" if self._data else "Stack(empty)"

    def __str__(self):
        return " | ".join(str(i) for i in reversed(self._data)) or "(empty)"

3. Core operations¶

In [2]:

s = Stack()
print("Empty?  ", s.is_empty())
print("Size:   ", s.size())
print("Stack:  ", s)

Empty?   True
Size:    0
Stack:   (empty)

In [3]:

# push three items
for value in [10, 20, 30]:
    s.push(value)
    print(f"push({value})  →  {s}")

push(10)  →  10
push(20)  →  20 | 10
push(30)  →  30 | 20 | 10

In [4]:

print("peek():   ", s.peek())   # top item, stack unchanged
print("size():   ", s.size())
print("Stack:    ", s)

peek():    30
size():    3
Stack:     30 | 20 | 10

In [5]:

# pop all items
while not s.is_empty():
    item = s.pop()
    print(f"pop() → {item}   remaining: {s}")

pop() → 30   remaining: 20 | 10
pop() → 20   remaining: 10
pop() → 10   remaining: (empty)

In [6]:

# pop from empty stack raises IndexError
try:
    s.pop()
except IndexError as e:
    print("Caught:", e)

Caught: pop from an empty stack

4. Example: balanced parentheses checker¶

A classic stack application: verify that every opening bracket ( [ { has a matching closing bracket in the correct order.

In [7]:

MATCHING = {')': '(', ']': '[', '}': '{'}
OPENERS  = set(MATCHING.values())


def is_balanced(expression: str) -> bool:
    """Return True if every bracket in *expression* is properly matched."""
    stack = Stack()
    for ch in expression:
        if ch in OPENERS:
            stack.push(ch)
        elif ch in MATCHING:
            if stack.is_empty() or stack.pop() != MATCHING[ch]:
                return False
    return stack.is_empty()


test_cases = [
    ("()",              True),
    ("()[]{}",          True),
    ("{[()]}",          True),
    ("(]",              False),
    ("([)]",            False),
    ("{[}",             False),
    ("",                True),
    ("(((",             False),
    ("a(b[c{d}e]f)g",   True),
]

print(f"{'Expression':<22}  {'Expected':<10}  {'Got':<10}  {'Pass?'}")
print("-" * 55)
for expr, expected in test_cases:
    result = is_balanced(expr)
    status = "PASS" if result == expected else "FAIL"
    print(f"{expr!r:<22}  {str(expected):<10}  {str(result):<10}  {status}")

Expression              Expected    Got         Pass?
-------------------------------------------------------
'()'                    True        True        PASS
'()[]{}'                True        True        PASS
'{[()]}'                True        True        PASS
'(]'                    False       False       PASS
'([)]'                  False       False       PASS
'{[}'                   False       False       PASS
''                      True        True        PASS
'((('                   False       False       PASS
'a(b[c{d}e]f)g'         True        True        PASS

Licensed under the GNU General Public License v2.0 (GPL-2).
You may redistribute and/or modify this work under the terms of GPL-2.
This work is distributed WITHOUT ANY WARRANTY.
Happy computing.