Python Stack Implementation: Lists vs Deques

Stack: LIFO Data Structure

You want to learn about Stacks—one of the most fundamental linear data structures that follows the LIFO (Last-In-First-Out) principle, right? Think of a stack like a pile of books: you add (push) a book to the top, and you can only remove (pop) the topmost book first. Stacks are simple yet powerful, used in countless algorithms, programming language internals, and real-world applications.

I. Core Principles of Stacks

1. Key Properties

LIFO Order: The last element added to the stack is the first one to be removed.
Fixed Operations: Stacks support a small set of core operations (all O(1) time complexity for efficient implementations):
- push(item): Add an item to the top of the stack.
- pop(): Remove and return the item from the top of the stack (raises an error if the stack is empty).
- peek() (or top()): Return the top item without removing it (raises an error if empty).
- isEmpty(): Check if the stack is empty (returns True/False).
- size(): Return the number of items in the stack.

2. Visualization

plaintext

Push(5) → [5]          (Top = 5)
Push(3) → [5, 3]       (Top = 3)
Push(7) → [5, 3, 7]    (Top = 7)
Pop()   → [5, 3]       (Returns 7; Top = 3)
Peek()  → 3            (Top remains 3)
Pop()   → [5]          (Returns 3; Top = 5)
isEmpty() → False
size() → 1

II. Stack Implementations (Python)

In Python, stacks can be implemented in two common ways:

Using Lists: Simple and built-in (but not optimized for very large stacks, as list pop(0) is O(n) — but we use pop() which is O(1)).
Using collections.deque: More efficient for large stacks (designed for fast appends/pops from both ends, O(1) time).

We’ll implement a Stack class with both approaches, plus practical examples.

1. List-Based Implementation (Simple)

python

运行

class StackList:
    def __init__(self):
        self.items = []  # Underlying list to store stack elements

    def push(self, item):
        """Add item to the top of the stack"""
        self.items.append(item)  # Append to end (O(1) time)

    def pop(self):
        """Remove and return top item (raises IndexError if empty)"""
        if self.isEmpty():
            raise IndexError("Pop from empty stack")
        return self.items.pop()  # Pop from end (O(1) time)

    def peek(self):
        """Return top item without removing it (raises IndexError if empty)"""
        if self.isEmpty():
            raise IndexError("Peek from empty stack")
        return self.items[-1]  # Access last element (O(1) time)

    def isEmpty(self):
        """Check if stack is empty"""
        return len(self.items) == 0

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

    def __str__(self):
        """String representation of the stack (top at the end)"""
        return f"Stack: {self.items}"

# Test List-Based Stack
if __name__ == "__main__":
    stack = StackList()
    stack.push(10)
    stack.push(20)
    stack.push(30)
    print(stack)  # Output: Stack: [10, 20, 30]
    print("Top item:", stack.peek())  # Output: 30
    print("Pop:", stack.pop())  # Output: 30
    print(stack)  # Output: Stack: [10, 20]
    print("Is empty?", stack.isEmpty())  # Output: False
    print("Size:", stack.size())  # Output: 2

2. Deque-Based Implementation (Efficient)

collections.deque (double-ended queue) is optimized for fast appends and pops from both ends. It’s preferred for production code, especially with large stacks.

python

运行

from collections import deque

class StackDeque:
    def __init__(self):
        self.items = deque()  # Underlying deque to store elements

    def push(self, item):
        """Add item to the top of the stack"""
        self.items.append(item)  # Append to right (O(1) time)

    def pop(self):
        """Remove and return top item (raises IndexError if empty)"""
        if self.isEmpty():
            raise IndexError("Pop from empty stack")
        return self.items.pop()  # Pop from right (O(1) time)

    def peek(self):
        """Return top item without removing it (raises IndexError if empty)"""
        if self.isEmpty():
            raise IndexError("Peek from empty stack")
        return self.items[-1]  # Access last element (O(1) time)

    def isEmpty(self):
        """Check if stack is empty"""
        return len(self.items) == 0

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

    def __str__(self):
        """String representation (top at the end)"""
        return f"Stack: {list(self.items)}"

# Test Deque-Based Stack
if __name__ == "__main__":
    stack = StackDeque()
    stack.push("A")
    stack.push("B")
    stack.push("C")
    print(stack)  # Output: Stack: ['A', 'B', 'C']
    print("Pop:", stack.pop())  # Output: 'C'
    print("Top item:", stack.peek())  # Output: 'B'
    print("Size:", stack.size())  # Output: 2

III. Common Stack Use Cases & Examples

Stacks are used in a wide range of scenarios where LIFO order is critical. Below are practical examples of key applications:

1. Reverse a String

Use a stack to reverse the order of characters (push all chars, then pop to build reversed string).

python

运行

def reverse_string(s):
    stack = StackDeque()
    # Push all characters to stack
    for char in s:
        stack.push(char)
    # Pop to build reversed string
    reversed_s = ""
    while not stack.isEmpty():
        reversed_s += stack.pop()
    return reversed_s

print("Reversed 'hello':", reverse_string("hello"))  # Output: 'olleh'

2. Check Balanced Parentheses

A classic problem: verify if parentheses (), brackets [], and braces {} are properly nested and closed.

python

运行

def is_balanced_parentheses(s):
    stack = StackDeque()
    # Map closing brackets to their matching opening brackets
    matching_bracket = {')': '(', ']': '[', '}': '{'}
    
    for char in s:
        # If opening bracket, push to stack
        if char in matching_bracket.values():
            stack.push(char)
        # If closing bracket, check match
        elif char in matching_bracket.keys():
            # If stack is empty or top doesn't match, return False
            if stack.isEmpty() or stack.pop() != matching_bracket[char]:
                return False
        # Ignore non-bracket characters (e.g., letters, numbers)
        else:
            continue
    
    # Stack must be empty if all brackets are balanced
    return stack.isEmpty()

print(is_balanced_parentheses("()[]{}"))  # Output: True
print(is_balanced_parentheses("(]"))      # Output: False
print(is_balanced_parentheses("({[]})"))  # Output: True
print(is_balanced_parentheses("({[)]}"))  # Output: False

3. Evaluate Postfix (Reverse Polish Notation)

Postfix notation (e.g., 3 4 + 5 *) is easier for computers to evaluate than infix notation ((3 + 4) * 5). Stacks simplify this by storing operands and applying operators.

python

运行

def evaluate_postfix(expression):
    stack = StackDeque()
    operators = {'+': lambda a, b: a + b,
                 '-': lambda a, b: b - a,  # Note: pop order is b then a
                 '*': lambda a, b: a * b,
                 '/': lambda a, b: b // a}  # Integer division (adjust for floats if needed)
    
    for token in expression.split():
        # If token is a number, push to stack
        if token.isdigit():
            stack.push(int(token))
        # If token is an operator, apply to top two operands
        elif token in operators:
            if stack.size() < 2:
                raise ValueError("Invalid postfix expression")
            a = stack.pop()
            b = stack.pop()
            result = operators[token](a, b)
            stack.push(result)
        else:
            raise ValueError(f"Unknown token: {token}")
    
    # Final result is the only item left in the stack
    if stack.size() != 1:
        raise ValueError("Invalid postfix expression")
    return stack.pop()

print(evaluate_postfix("3 4 + 5 *"))  # Output: (3+4)*5 = 35
print(evaluate_postfix("10 5 / 2 +")) # Output: (10//5)+2 = 4
print(evaluate_postfix("8 2 5 * + 1 3 2 * + /"))  # Output: (8+(2*5))/(1+(3*2)) = 18/7 = 2

4. Function Call Stack (Programming Language Internals)

Every time you call a function in Python (or most languages), the interpreter uses a stack to track the call hierarchy:

Push the current function’s state (variables, return address) when a new function is called.
Pop the state when the function returns, resuming execution of the previous function.

Example of call stack visualization:

python

运行

def func_c():
    print("In func_c (top of stack)")

def func_b():
    print("In func_b")
    func_c()  # Push func_c to stack
    print("Back to func_b (func_c popped)")

def func_a():
    print("In func_a")
    func_b()  # Push func_b to stack
    print("Back to func_a (func_b popped)")

func_a()  # Push func_a to stack

Output (call stack order):

plaintext

In func_a
In func_b
In func_c (top of stack)
Back to func_b (func_c popped)
Back to func_a (func_b popped)

IV. Time & Space Complexity

All core stack operations are O(1) (constant time) because they only modify or access the top of the stack. The space complexity is O(n) (n = number of items in the stack) to store the elements.

Operation	Time Complexity	Space Complexity
`push()`	O(1)	O(1) (amortized)
`pop()`	O(1)	O(1)
`peek()`	O(1)	O(1)
`isEmpty()`	O(1)	O(1)
`size()`	O(1)	O(1)

Why `deque` is Better Than Lists for Large Stacks

Python lists are dynamic arrays. While append() and pop() (from the end) are O(1), lists may need to resize (allocate new memory and copy elements) when full—this is amortized O(1) but can cause occasional delays for very large stacks.
collections.deque is implemented as a doubly linked list, so appends/pops from both ends are always O(1) with no resizing overhead.

V. Stack vs. Queue (Key Differences)

It’s common to confuse stacks with queues—here’s a quick comparison:

Feature	Stack	Queue
Order	LIFO (Last-In-First-Out)	FIFO (First-In-First-Out)
Core Operations	`push()` (top), `pop()` (top)	`enqueue()` (rear), `dequeue()` (front)
Analogy	Pile of books	Line at a grocery store
Use Cases	Parentheses checking, function calls, postfix evaluation	Task scheduling, breadth-first search (BFS), print spooling

VI. Practical Applications of Stacks

Programming Language Internals: Function call stacks, expression evaluation (infix → postfix conversion), and recursion.
Editor/IDE Features: Undo/redo functionality (each action is pushed to a stack; undo pops the last action).
Algorithms: Depth-First Search (DFS), backtracking (e.g., maze solving, Sudoku), and topological sorting.
Compilers/Interpreters: Syntax parsing (checking valid code structure) and symbol tables.
Real-World Tools: Browser history (back button navigates a stack of visited pages), stack memory in CPUs.