DSA Stacks

A stack is a Last-In-First-Out (LIFO) collection where the only element you can add or remove is the one on top.

What Is a Stack?

A stack restricts access to a single end, called the top. You can push a new element onto the top, or pop the top element off, but you cannot touch anything underneath without first removing what's above it. This Last-In-First-Out ordering means the most recently added item is always the first one to leave.

The Call Stack Analogy

Every running program uses a stack to keep track of function calls. When function A calls function B, a new frame for B is pushed on top of A's frame, holding B's local variables and the address to return to. When B finishes, its frame is popped off, and execution resumes exactly where A left off. Deeply nested or infinite recursion pushes frame after frame until the call stack runs out of space, producing a stack overflow.

  • push(value): add value to the top of the stack — O(1).
  • pop(): remove and return the top value — O(1).
  • peek() / top(): look at the top value without removing it — O(1).
  • is_empty(): check whether the stack has any elements — O(1).
  • size(): report how many elements are currently on the stack — O(1).

Example

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

    def push(self, value):
        self._items.append(value)

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

    def peek(self):
        if self.is_empty():
            raise IndexError("peek at an empty stack")
        return self._items[-1]

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

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


stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())   # 3
print(stack.peek())  # 2
print(stack.size())  # 2

Example

def is_balanced(expression):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []

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

    return len(stack) == 0


print(is_balanced("(a[b]{c})"))  # True
print(is_balanced("(a[b)c]"))    # False
print(is_balanced("((("))         # False
Note: Python's built-in list is already an efficient stack: append() pushes and pop() with no argument pops from the end in O(1) amortized time, so you rarely need a custom Stack class in practice.

Stacks vs. Other Structures

StructureAccess OrderTypical Use
StackLast-In-First-Out (LIFO)Undo history, call stack, expression parsing
QueueFirst-In-First-Out (FIFO)Task scheduling, breadth-first search
Array (by index)Any orderRandom access to elements

Example

def reverse_string(text):
    stack = list(text)
    reversed_text = ""
    while stack:
        reversed_text += stack.pop()
    return reversed_text


print(reverse_string("stacks"))   # skcats
print(reverse_string("racecar"))  # racecar
Note: Calling pop() or peek() on an empty stack is a common bug. Always check is_empty() first, or be ready to catch the IndexError that Python's list.pop() raises when there's nothing left to remove.

Exercise: DSA Stacks

What ordering principle does a stack follow?

Keep Going

Data Structures Interview QuestionsPractice real questions asked for Data StructuresSoftware Engineer SalarySee what Software Engineer roles pay in the marketAuto Apply for JobsApply to open roles related to Data Structures and tweak your resume