Understanding Stacks: Implementation Guide

Array-Based Stack Implementation

Using an array (or dynamic array) is the most common way to implement a stack. It's simple and cache-friendly.

# Python implementation using a list
class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        return None

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        return None

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

# Usage
stack = Stack()
stack.push(10)
stack.push(20)
print(stack.peek())  # 20
print(stack.pop())   # 20
print(stack.pop())   # 10

Time Complexity: Push O(1), Pop O(1) (amortized), Peek O(1)
Space Complexity: O(n) where n is the number of elements

Linked List Stack Implementation

For unbounded stacks or when you need guaranteed O(1) operations, use a linked list. Add/remove at the head.

# Python implementation using linked list
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedListStack:
    def __init__(self):
        self.top = None

    def push(self, item):
        new_node = Node(item)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if not self.is_empty():
            data = self.top.data
            self.top = self.top.next
            return data
        return None

    def peek(self):
        if not self.is_empty():
            return self.top.data
        return None

    def is_empty(self):
        return self.top is None

Pros: Guaranteed O(1) for all operations, no resizing overhead
Cons: Extra memory for pointers, less cache-friendly

Core Stack Operations

Valid Parentheses: Classic Stack Problem

The most common stack interview problem is matching parentheses. Here's how it works:

def is_valid(s: str) -> bool:
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in mapping:  # Closing bracket
            if not stack or stack.pop() != mapping[char]:
                return False
        else:  # Opening bracket
            stack.append(char)

    return len(stack) == 0

# Examples
print(is_valid("()"))      # True
print(is_valid("()[]{}"))  # True
print(is_valid("(]"))      # False
print(is_valid("([)]"))    # False

Production Tips

• Use built-in stack classes: Most languages have stack implementations (Python list, Java Stack/Deque, C++ std::stack)
• Consider Deque: For production code, use a double-ended queue if you need stack + queue operations
• Handle overflow: For fixed-size array stacks, check capacity before pushing
• Validate input: Always check if stack is empty before popping in production code
• Memory concerns: Be aware of stack size limits for recursive calls (see Level 3)

Common Pitfalls

• Forgot to check empty: Calling pop() on an empty stack causes errors
• Wrong end of array: Remember to push/pop at the END of the array (index -1), not the beginning
• Confusing stack top: In visual representations, the "top" is usually shown at the top, but in code arrays, it's at the END (highest index)
• Not using built-ins: Don't reinvent the wheel unless you have a specific requirement