Stacks and LIFO

The Plate Stack That Explains Everything

Picture a busy restaurant kitchen on a Saturday night. The dishwasher cleans plates and stacks them one by one. The cook grabs plates off the top to serve food. The plate placed on the stack most recently is the first one grabbed. The plate at the very bottom — the first one cleaned — will be the last one used.

This is not an accident. This is the defining rule of a stack: Last In, First Out — or LIFO for short.

You interact with stacks constantly without realizing it. Every time you press Ctrl+Z to undo a mistake, a stack is popping the last action. Every time your browser goes back one page, it is popping the last URL off a stack. When your Python program calls a function that calls another function, the computer uses a stack to remember where to return when each function finishes.

The LIFO Principle — Formal Definition

Stack: An ordered collection of elements where insertions and deletions happen at the same end, called the top. The last element inserted is the first element removed.

This single rule — access only at the top — is what makes a stack both restrictive and incredibly powerful.

Core Operations

Every stack supports four fundamental operations, all running in O(1) time:

Every operation happens at the top. No searching, no indexing, no traversal. That is why everything is constant time.

Implementation 1: Using Python's Built-in List

Python lists already behave like stacks when you use only append() and pop():

stack = []

stack.append(10)    # Push 10 → stack: [10]
stack.append(20)    # Push 20 → stack: [10, 20]
stack.append(30)    # Push 30 → stack: [10, 20, 30]

print(stack[-1])    # Peek → Output: 30  (top element, not removed)
print(stack.pop())  # Pop  → Output: 30  stack: [10, 20]
print(stack.pop())  # Pop  → Output: 20  stack: [10]
print(len(stack) == 0)  # is_empty → False

Output:

30
30
20
False

This works well for most purposes. However, Python lists are backed by dynamic arrays — they can grow or shrink. For a strict stack, a custom class is cleaner and makes intentions explicit.

Implementation 2: Custom Stack Class with Nodes

class Node:
    def __init__(self, data):
        self.data = data    # The value stored in this node
        self.next = None    # Pointer to the node below this one

class Stack:
    def __init__(self):
        self.top = None     # The top of the stack starts empty
        self.size = 0       # Track number of elements

    def push(self, data):
        new_node = Node(data)      # Create a new node
        new_node.next = self.top   # New node points down to current top
        self.top = new_node        # New node becomes the new top
        self.size += 1

    def pop(self):
        if self.is_empty():
            raise IndexError("Pop from empty stack")
        popped_data = self.top.data    # Grab the top value
        self.top = self.top.next       # Move top pointer one level down
        self.size -= 1
        return popped_data

    def peek(self):
        if self.is_empty():
            raise IndexError("Peek at empty stack")
        return self.top.data           # Return top value without removing

    def is_empty(self):
        return self.top is None        # Stack is empty when top points to nothing

    def __len__(self):
        return self.size

Running it:

s = Stack()
s.push("A")
s.push("B")
s.push("C")
print(s.peek())   # C
print(s.pop())    # C
print(s.pop())    # B
print(len(s))     # 1

Output:

C
C
B
1

Classic Interview Problem: Balanced Parentheses

This is one of the most famous stack problems. Given a string of brackets, determine if they are correctly paired and nested.

Why a stack? When you see an opening bracket, you push it. When you see a closing bracket, you check if the top of the stack is its matching opener. If yes, pop it. If no — they are mismatched.

def is_balanced(s):
    stack = []
    pairs = {')': '(', '}': '{', ']': '['}   # Map each closer to its opener

    for char in s:
        if char in '({[':
            stack.append(char)               # Opening bracket — push it
        elif char in ')}]':
            if not stack or stack[-1] != pairs[char]:
                return False                 # No match — unbalanced
            stack.pop()                      # Matched pair — pop the opener

    return len(stack) == 0                   # Balanced only if nothing is left

Test cases:

print(is_balanced("({[]})"))    # True  — perfectly nested
print(is_balanced("{[()]}"))    # True  — all pairs correct
print(is_balanced("(]"))        # False — wrong closer
print(is_balanced("((())"))     # False — one opener never closed
print(is_balanced(""))          # True  — empty string is balanced

Output:

True
True
False
False
True

Real-World Applications of Stacks

Python's Call Stack: Functions Calling Functions

When Python runs a program, it uses an internal stack called the call stack to manage function execution. Each time a function is called, a new stack frame is pushed. When the function returns, that frame is popped and execution resumes in the calling function.

def greet(name):
    return f"Hello, {name}!"

def main():
    message = greet("Alice")   # greet() is pushed onto the call stack
    print(message)             # greet() has returned, popped off the stack

main()

When main() calls greet(), the call stack looks like:

[ greet("Alice") ]   ← top
[ main()         ]

When greet() returns, it is popped, and main() continues.

Stack Overflow: When the Stack Runs Out of Space

A stack overflow occurs when the call stack exceeds its memory limit. This almost always happens due to infinite or deeply recursive function calls:

def infinite():
    return infinite()   # Calls itself forever, pushing frames endlessly

infinite()  # → RecursionError: maximum recursion depth exceeded

Python sets a default recursion limit of 1000 calls. You can check it with sys.getrecursionlimit(). In practice, this means that any recursive function that goes deeper than ~1000 levels will crash. This is why iterative solutions using an explicit stack are sometimes preferred over deep recursion.

Key Takeaway

A stack is one of the simplest data structures — access only at the top, LIFO order — yet it appears everywhere in computer science. Undo systems, browsers, compilers, and the very mechanism that lets functions call each other all rely on stacks. When you see a problem involving "the most recent thing" or "reversing order," think stack first.