DSA Stacks

A stack is a linear data structure that follows a specific order for inserting and removing elements. That order is called LIFO — Last In, First Out. The last element added to the stack is always the first one to be removed.

Think of a stack of plates in a cafeteria. Plates are added to the top and also removed from the top. The plate placed last is the first one picked up. The stack data structure works exactly the same way.

Core Stack Operations

A stack has two fundamental operations:

  • Push — Add an element to the top of the stack.
  • Pop — Remove the element from the top of the stack.

There are also two common helper operations:

  • Peek (Top) — View the top element without removing it.
  • isEmpty — Check whether the stack has any elements.

Implementing a Stack in Python

Method 1: Using a Python List

Python's built-in list can act as a stack. The append() method pushes to the top, and pop() removes from the top — both are O(1).


stack = []

# Push items onto the stack
stack.append("first")
stack.append("second")
stack.append("third")
print("Stack:", stack)
# Output: Stack: ['first', 'second', 'third']

# Peek at the top
print("Top:", stack[-1])
# Output: Top: third

# Pop the top item
removed = stack.pop()
print("Removed:", removed)
print("Stack after pop:", stack)
# Output: Removed: third
# Output: Stack after pop: ['first', 'second']

Method 2: Using a Custom Stack Class

A custom class provides cleaner, more explicit stack behavior with meaningful method names.


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

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

    def pop(self):
        if self.is_empty():
            return "Stack is empty"
        return self.items.pop()

    def peek(self):
        if self.is_empty():
            return "Stack is empty"
        return self.items[-1]

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

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

# Usage
s = Stack()
s.push(10)
s.push(20)
s.push(30)

print("Peek:", s.peek())    # Output: Peek: 30
print("Pop:", s.pop())      # Output: Pop: 30
print("Size:", s.size())    # Output: Size: 2

Real-World Applications of Stacks

1. Undo Feature in Text Editors

Every action (typing, deleting, formatting) is pushed onto a stack. When "Undo" is pressed, the most recent action is popped and reversed. This is exactly LIFO behavior.

2. Browser Back Button

Each page visited is pushed onto a history stack. Clicking "Back" pops the current page and returns to the previous one.

3. Function Call Stack

When a function calls another function, the current function's state is pushed onto the call stack. Once the inner function completes, it is popped and execution resumes in the outer function.

4. Balanced Parentheses Check

A classic stack problem: check whether brackets in an expression are properly matched and nested.


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

    for char in expression:
        if char in "({[":
            stack.append(char)           # Push opening brackets
        elif char in ")}]":
            if not stack:
                return False
            if stack[-1] != matching[char]:
                return False
            stack.pop()                  # Pop matching opening bracket

    return len(stack) == 0              # Balanced if stack is empty

print(is_balanced("(a + b) * [c - d]"))   # Output: True
print(is_balanced("(a + [b)"))            # Output: False

5. Reversing a String Using a Stack


def reverse_string(text):
    stack = []
    for char in text:
        stack.append(char)

    reversed_text = ""
    while stack:
        reversed_text += stack.pop()

    return reversed_text

print(reverse_string("hello"))   # Output: olleh

Evaluating Expressions with Stacks

Stacks are used to evaluate mathematical expressions, particularly in postfix (Reverse Polish Notation) format, where operators come after their operands.


# Evaluate a postfix expression
# Example: "3 4 + 2 *" means (3 + 4) * 2 = 14

def evaluate_postfix(expression):
    stack = []
    tokens = expression.split()

    for token in tokens:
        if token.isdigit():
            stack.append(int(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]

print(evaluate_postfix("3 4 + 2 *"))   # Output: 14

Big O Summary for Stack Operations

  • Push — O(1)
  • Pop — O(1)
  • Peek — O(1)
  • Search — O(n)
  • Space — O(n)

Key Points

  • A stack follows LIFO — the last element added is the first to be removed.
  • Core operations are push (add to top), pop (remove from top), and peek (view top).
  • Python lists can serve as stacks using append() and pop().
  • Stacks are used in undo functionality, browser history, function call management, and expression evaluation.
  • All fundamental stack operations run in O(1) time.
  • Stacks are simple yet powerful — many algorithm problems are solved more elegantly using a stack.
Previous lessons
Back to courses
Next lessons

Leave a Comment