Stacks: Implementation and Time Complexity Analysis

Introduction to Stacks

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. This means the last element added to the stack is the first one to be removed. Think of a stack of plates: you add new plates on top, and you also remove plates from the top. You cannot easily access a plate in the middle without first removing the ones above it.

Stacks are one of the most fundamental data structures in computer science. They power function call management in programming languages, expression evaluation, backtracking algorithms, undo mechanisms in editors, and much more. Understanding how to implement and analyze a stack is essential for every developer.

Core Stack Operations

A stack typically supports the following operations:

• push(item) — Add an item to the top of the stack.
• pop() — Remove and return the top item.
• peek() or top() — Return the top item without removing it.
• isEmpty() — Check whether the stack is empty.
• size() — Return the number of items in the stack.

Why Stacks Matter

Stacks matter because they model a natural and extremely common pattern: reversing or unwinding operations in the opposite order they occurred. Here are some real-world use cases:

• Function call stack: Every recursive function call is pushed onto the call stack, and popped when it returns.
• Undo/Redo: Text editors use stacks to track user actions so they can be reversed.
• Expression evaluation: Compilers and calculators use stacks to parse and evaluate arithmetic expressions, especially in postfix notation.
• Backtracking: Algorithms like depth-first search (DFS) and maze solvers rely on stacks to remember paths.
• Browser history: The "back" button uses a stack of visited pages.

Because stacks enforce a strict access pattern, they are simple to implement, efficient, and resistant to misuse. When your problem involves nested structures or reversing order, a stack is often the right tool.

How to Use a Stack

Most programming languages provide a built-in stack or a structure that can be used as one. In Python, a regular list works perfectly as a stack because its append() and pop() methods operate on the end of the list in O(1) time.

# Using a Python list as a stack
stack = []

# Push items
stack.append(10)
stack.append(20)
stack.append(30)

print(stack)  # Output: [10, 20, 30]

# Peek at the top
print(stack[-1])  # Output: 30

# Pop items
print(stack.pop())  # Output: 30
print(stack.pop())  # Output: 20

print(stack)  # Output: [10]

In JavaScript, you can use an array the same way:

// Using a JavaScript array as a stack
const stack = [];

stack.push(10);
stack.push(20);
stack.push(30);

console.log(stack[stack.length - 1]); // 30

console.log(stack.pop()); // 30
console.log(stack.pop()); // 20

While these built-in options are convenient, understanding how to build a stack from scratch gives you insight into memory management, trade-offs, and how the underlying data structures behave.

Implementing a Stack

There are two common ways to implement a stack: using an array or using a linked list. Each has its own advantages and trade-offs.

Array-Based Stack Implementation

An array-based stack stores elements in a contiguous block of memory. The "top" of the stack is simply the last element in the array. This approach offers excellent cache locality and is straightforward to implement.

class Stack:
    def __init__(self):
        self.items = []

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

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self.items.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self.items[-1]

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

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


# Example usage
s = Stack()
s.push("a")
s.push("b")
s.push("c")

print(s.peek())   # Output: c
print(s.pop())    # Output: c
print(s.size())   # Output: 2
print(s.is_empty())  # Output: False

In Python, list.append() and list.pop() are amortized O(1) operations. Occasionally, when the underlying array needs to resize, an append takes O(n) time, but this cost is spread across many operations, so the average remains constant.

Linked-List-Based Stack Implementation

A linked-list-based stack uses nodes where each node points to the next. The "top" of the stack is the head of the linked list. Pushing and popping involve adding or removing the head node, which is always O(1).

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


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

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

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        value = self.top.value
        self.top = self.top.next
        self._size -= 1
        return value

    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self.top.value

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

    def size(self):
        return self._size


# Example usage
stack = LinkedListStack()
stack.push(1)
stack.push(2)
stack.push(3)

print(stack.peek())  # Output: 3
print(stack.pop())   # Output: 3
print(stack.size())  # Output: 2

The linked-list approach avoids resizing costs entirely and can grow dynamically without preallocation. However, each node requires extra memory for the pointer, and cache performance is worse than arrays because nodes are scattered in memory.

Time Complexity Analysis

One of the biggest advantages of a stack is the efficiency of its core operations. Below is the time complexity analysis for each operation, assuming a proper implementation.

Operation-by-Operation Breakdown

• push(item): O(1) — In an array-based stack, appending to the end is amortized O(1). In a linked-list stack, inserting at the head is always O(1).
• pop(): O(1) — Removing the last element of an array or the head of a linked list is constant time.
• peek(): O(1) — Accessing the top element requires no traversal.
• isEmpty(): O(1) — A simple size check or null check.
• size(): O(1) — Maintained as a counter or retrieved via len().

Space Complexity

The space complexity of a stack is O(n), where n is the number of elements stored. This is true for both array-based and linked-list-based implementations. The linked-list version has a slightly higher constant factor due to the storage of pointers in each node.

Amortized vs. Worst-Case

It is important to distinguish between amortized and worst-case time complexity. In an array-based stack, a single push might trigger a resize that copies all elements, taking O(n) time. However, because resizes happen infrequently (typically doubling the capacity each time), the amortized cost per push remains O(1). If your application has strict real-time requirements where no single operation can exceed O(1), a linked-list implementation is safer.

Practical Example: Balanced Parentheses

A classic application of stacks is checking whether a string of parentheses is balanced. Every opening bracket must have a matching closing bracket in the correct order.

def is_balanced(expression):
    stack = []
    matching = {')': '(', ']': '[', '}': '{'}

    for char in expression:
        if char in "([{":
            stack.append(char)
        elif char in ")]}":
            if not stack or stack.pop() != matching[char]:
                return False

    return len(stack) == 0


# Test cases
print(is_balanced("()"))          # True
print(is_balanced("([]){}"))      # True
print(is_balanced("([)]"))        # False
print(is_balanced("((()))"))      # True
print(is_balanced("(()"))         # False

This algorithm runs in O(n) time, where n is the length of the expression, because each character is processed exactly once. The space complexity is O(n) in the worst case, when all characters are opening brackets.

Practical Example: Evaluating Postfix Expressions

Postfix notation (also called Reverse Polish Notation) places operators after their operands, eliminating the need for parentheses. Stacks make evaluating these expressions straightforward.

def evaluate_postfix(expression):
    stack = []
    operators = {'+', '-', '*', '/'}

    for token in expression.split():
        if token not in operators:
            stack.append(float(token))
        else:
            b = stack.pop()
            a = stack.pop()
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            elif token == '/':
                stack.append(a / b)

    return stack[0]


# Example: (3 + 4) * 2 in postfix is "3 4 + 2 *"
print(evaluate_postfix("3 4 + 2 *"))   # Output: 14.0
print(evaluate_postfix("5 1 2 + 4 * + 3 -"))  # Output: 14.0

Each token is processed once, giving O(n) time complexity. The stack holds at most O(n) operands in the worst case.

Best Practices

• Guard against underflow: Always check if the stack is empty before calling pop() or peek(). Raise a clear exception rather than letting the program crash with an obscure error.
• Choose the right implementation: Use an array-based stack when you need cache efficiency and predictable memory layout. Use a linked-list-based stack when you need guaranteed O(1) worst-case operations or when the maximum size is unknown and memory fragmentation is acceptable.
• Avoid random access: If you find yourself indexing into the middle of a stack, you are likely misusing it. Stacks are designed for top-only access. Consider a different data structure like an array or deque if you need random access.
• Prefer built-in structures when available: In Python, collections.deque is an excellent choice for a stack because it provides O(1) append and pop from both ends and is implemented as a doubly linked list of blocks, offering better performance than a plain list for large stacks.
• Document the LIFO contract: When exposing a stack in an API, make the LIFO behavior explicit so consumers do not rely on internal ordering.
• Watch for stack overflow: In recursive algorithms, deep recursion can exhaust the call stack. Consider converting deep recursion into an iterative approach using an explicit stack data structure.

Using collections.deque as a Stack

from collections import deque

stack = deque()

stack.append("first")
stack.append("second")
stack.append("third")

print(stack.pop())   # Output: third
print(stack.pop())   # Output: second
print(stack[-1])     # Output: first

The deque offers thread-safe, O(1) append and pop operations on both ends, making it a robust choice for production code.

Conclusion

Stacks are a deceptively simple yet powerful data structure that every developer should master. Their LIFO nature makes them ideal for problems involving nesting, reversal, and backtracking, and their core operations run in constant time, making them highly efficient. Whether you implement a stack using an array for cache-friendly performance or a linked list for guaranteed worst-case behavior, the key is understanding the trade-offs and choosing the right approach for your use case. By following best practices such as guarding against underflow, avoiding random access, and leveraging built-in structures like Python's deque, you can write clean, efficient, and reliable code. Stacks may be one of the first data structures you learn, but they remain indispensable throughout your career as a software engineer.