Skip to content

Stack

A stack is a Last-In-First-Out (LIFO) data structure where elements are added and removed from the same end (called the top). It follows the principle that the last element added is the first one to be removed.

Features

  • LIFO ordering - Last In, First Out access pattern
  • Efficient operations - O(1) push, pop, and peek operations
  • Dynamic size - automatically grows and shrinks as needed
  • Memory efficient - uses singly linked list for optimal memory usage
  • Type safe - generic implementation with type checking
  • Iterator support - can iterate from top to bottom
  • Utility operations - search, count, reverse, and copy functionality

Time Complexities

Operation Time Complexity Description
Push O(1) Add element to top
Pop O(1) Remove element from top
Peek/Top O(1) View top element
Search O(n) Find element position
Count O(n) Count occurrences
Clear O(1) Remove all elements
Copy O(n) Create shallow copy
Reverse O(n) Reverse stack order
Size/Length O(1) Get number of elements

Space Complexity: O(n) where n is the number of elements

Basic Usage

Creating and Initializing

from algo.data_structs.stacks_queues.stack import Stack

# Create empty stack
stack = Stack()

# Check if empty
print(stack.is_empty())    # True
print(len(stack))          # 0
print(stack.size())        # 0

# Stack is generic - can specify type
int_stack = Stack[int]()
str_stack = Stack[str]()

Adding Elements (Push)

# Push individual elements
stack.push(1)
stack.push(2)
stack.push(3)

print(len(stack))          # 3
print(stack.peek())        # 3 (top element)
print(stack.top())         # 3 (alias for peek)

# Push multiple elements using extend
stack.extend([4, 5, 6])
print(stack.peek())        # 6 (last element added becomes top)
print(len(stack))          # 6

# Extend with different iterables
stack.extend((7, 8))       # Tuple
stack.extend([9, 10])      # List
print(stack.to_list())     # [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] (top to bottom)

Viewing Elements

# Peek at top element without removing
top_element = stack.peek()
print(top_element)         # 10
print(len(stack))          # Still same size

# Using top() alias
top_element = stack.top()
print(top_element)         # 10

# Check if stack contains element
print(5 in stack)          # True
print(99 in stack)         # False

# Convert to list (top to bottom order)
elements = stack.to_list()
print(elements)            # [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

Removing Elements (Pop)

# Pop elements one by one (LIFO order)
popped = stack.pop()
print(popped)              # 10 (most recently added)
print(len(stack))          # 9

# Pop multiple elements
results = []
for _ in range(3):
    results.append(stack.pop())
print(results)             # [9, 8, 7]

# Pop until empty
while not stack.is_empty():
    element = stack.pop()
    print(f"Popped: {element}")

print(stack.is_empty())    # True

Clearing the Stack

# Add some elements
stack.extend([1, 2, 3, 4, 5])
print(len(stack))          # 5

# Clear all elements
stack.clear()
print(len(stack))          # 0
print(stack.is_empty())    # True

Search and Count Operations

Finding Elements

stack = Stack()
stack.extend([1, 2, 3, 2, 4, 2])  # [2, 4, 2, 3, 2, 1] (top to bottom)

# Search returns distance from top (0-based)
print(stack.search(2))     # 0 (top element)
print(stack.search(4))     # 1 (second from top)
print(stack.search(3))     # 3 (fourth from top)
print(stack.search(1))     # 5 (bottom element)
print(stack.search(99))    # -1 (not found)

# Check membership
print(2 in stack)          # True
print(99 in stack)         # False

Counting Elements

# Count occurrences of elements
print(stack.count(2))      # 3 (appears 3 times)
print(stack.count(1))      # 1 (appears once)
print(stack.count(99))     # 0 (not present)

# Count all elements
total_elements = len(stack)
print(total_elements)      # 6

Iteration and Traversal

stack = Stack()
stack.extend(['apple', 'banana', 'cherry', 'date'])

# Iterate from top to bottom
print("Stack contents (top to bottom):")
for item in stack:
    print(item)  # date, cherry, banana, apple

# Convert to list for processing
items = list(stack)
print(items)               # ['date', 'cherry', 'banana', 'apple']

# Enumerate with position
for i, item in enumerate(stack):
    print(f"Position {i}: {item}")

Working with Different Types

String Elements

words = Stack()
words.push("hello")
words.push("world")
words.push("python")

print(words.peek())        # "python"
print("world" in words)    # True
print(words.count("hello")) # 1

Numeric Elements

numbers = Stack()
numbers.extend([1, 2, 3, 4, 5])
numbers.push(3.14)
numbers.push(42)

print(numbers.peek())      # 42
print(3.14 in numbers)     # True
print(len(numbers))        # 7

Mixed Types

mixed = Stack()
mixed.push("string")
mixed.push(42)
mixed.push([1, 2, 3])      # Lists can be stored
mixed.push(True)

print(mixed.peek())        # True
print(42 in mixed)         # True
print(len(mixed))          # 4

Custom Objects

class Task:
    def __init__(self, name: str, priority: int):
        self.name = name
        self.priority = priority

    def __eq__(self, other):
        return isinstance(other, Task) and self.name == other.name

    def __str__(self):
        return f"Task({self.name}, priority={self.priority})"

tasks = Stack()
task1 = Task("Write code", 1)
task2 = Task("Test code", 2)
task3 = Task("Deploy", 3)

tasks.push(task1)
tasks.push(task2)
tasks.push(task3)

print(tasks.peek())        # Task(Deploy, priority=3)
print(task1 in tasks)      # True
print(len(tasks))          # 3

Stack Manipulation

Copying Stacks

original = Stack()
original.extend([1, 2, 3, 4, 5])

# Create a copy
copy_stack = original.copy()

# Verify they have same contents
print(copy_stack.to_list() == original.to_list())  # True
print(len(copy_stack) == len(original))             # True

# Verify they're independent
original.push(6)
print(len(original))       # 6
print(len(copy_stack))     # 5 (unchanged)

copy_stack.push(99)
print(99 in original)      # False
print(99 in copy_stack)    # True

Reversing Stacks

stack = Stack()
stack.extend([1, 2, 3, 4, 5])
print(stack.to_list())     # [5, 4, 3, 2, 1] (top to bottom)

# Reverse the stack
stack.reverse()
print(stack.to_list())     # [1, 2, 3, 4, 5] (top to bottom)
print(stack.peek())        # 1 (was bottom, now top)

String Representation

# Empty stack
empty_stack = Stack()
print(str(empty_stack))    # Stack([])

# Non-empty stack
stack = Stack()
stack.extend([1, 2, 3])
print(str(stack))          # Stack([3 <- 2 <- 1] <- top)

# Detailed representation for debugging
print(repr(stack))         # Stack(size=3, top=3)

Error Handling

stack = Stack()

# Safe operations on empty stack
print(stack.is_empty())    # True
print(len(stack))          # 0
print(stack.search(42))    # -1
print(stack.count(42))     # 0
print(42 in stack)         # False

# Operations that raise errors on empty stack
try:
    stack.pop()
except IndexError as e:
    print(f"Error: {e}")   # Error: Cannot pop from empty stack

try:
    stack.peek()
except IndexError as e:
    print(f"Error: {e}")   # Error: Cannot peek empty stack

try:
    stack.top()
except IndexError as e:
    print(f"Error: {e}")   # Error: Cannot peek empty stack

Common Patterns

Building from Iterables

# From list
stack = Stack()
stack.extend([1, 2, 3, 4, 5])

# From tuple
stack2 = Stack()
stack2.extend((1, 2, 3))

# From range
stack3 = Stack()
stack3.extend(range(10))

# From another stack
stack4 = Stack()
stack4.extend(stack)  # Copy elements from stack

LIFO Processing

# Process items in reverse order
items = ["first", "second", "third", "fourth"]
stack = Stack()

# Load items
for item in items:
    stack.push(item)

# Process in LIFO order
processed = []
while not stack.is_empty():
    item = stack.pop()
    processed.append(f"Processed: {item}")

print(processed)
# ['Processed: fourth', 'Processed: third', 'Processed: second', 'Processed: first']

Undo/Redo Operations

class SimpleEditor:
    def __init__(self):
        self.content = ""
        self.undo_stack = Stack()
        self.redo_stack = Stack()

    def add_text(self, text: str):
        # Save current state for undo
        self.undo_stack.push(self.content)
        self.redo_stack.clear()  # Clear redo history
        self.content += text

    def delete_chars(self, count: int):
        # Save current state for undo
        self.undo_stack.push(self.content)
        self.redo_stack.clear()  # Clear redo history
        self.content = self.content[:-count]

    def undo(self):
        if not self.undo_stack.is_empty():
            # Save current state for redo
            self.redo_stack.push(self.content)
            self.content = self.undo_stack.pop()

    def redo(self):
        if not self.redo_stack.is_empty():
            # Save current state for undo
            self.undo_stack.push(self.content)
            self.content = self.redo_stack.pop()

# Usage
editor = SimpleEditor()
editor.add_text("Hello")
editor.add_text(" World")
print(editor.content)      # "Hello World"

editor.undo()
print(editor.content)      # "Hello"

editor.redo()
print(editor.content)      # "Hello World"

Function Call Stack Simulation

def function_call_trace():
    call_stack = Stack()

    def trace_call(func_name: str, args: str = ""):
        call_info = f"{func_name}({args})"
        call_stack.push(call_info)
        print(f"Entering: {call_info}")
        print(f"Call stack depth: {len(call_stack)}")

    def trace_return(func_name: str):
        if not call_stack.is_empty():
            returned_func = call_stack.pop()
            print(f"Returning from: {returned_func}")
            print(f"Call stack depth: {len(call_stack)}")

    # Simulate function calls
    trace_call("main")
    trace_call("process_data", "data.txt")
    trace_call("validate_input", "user_input")
    trace_call("parse_config", "config.json")

    # Show current call stack
    print("\nCurrent call stack (top to bottom):")
    for i, call in enumerate(call_stack):
        print(f"  {i}: {call}")

    # Simulate returns
    trace_return("parse_config")
    trace_return("validate_input")
    trace_return("process_data")
    trace_return("main")

function_call_trace()

Backtracking Algorithms

def find_path_in_maze(maze, start, end):
    """Find path using stack-based backtracking."""
    path_stack = Stack()
    visited = set()

    def is_valid(x, y):
        return (0 <= x < len(maze) and 
                0 <= y < len(maze[0]) and 
                maze[x][y] == 0 and  # 0 = open, 1 = wall
                (x, y) not in visited)

    # Start the search
    path_stack.push(start)
    visited.add(start)

    while not path_stack.is_empty():
        current = path_stack.peek()

        if current == end:
            # Found the end, return path
            return path_stack.to_list()

        # Try all four directions
        x, y = current
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        moved = False

        for dx, dy in directions:
            new_x, new_y = x + dx, y + dy

            if is_valid(new_x, new_y):
                path_stack.push((new_x, new_y))
                visited.add((new_x, new_y))
                moved = True
                break

        if not moved:
            # Dead end, backtrack
            path_stack.pop()

    return None  # No path found

# Example maze (0 = open, 1 = wall)
maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [1, 1, 0, 0, 0],
    [0, 0, 0, 1, 0]
]

path = find_path_in_maze(maze, (0, 0), (4, 4))
if path:
    print(f"Path found: {path}")
else:
    print("No path found")

Practical Applications

Expression Evaluation (Parentheses Matching)

def is_balanced_parentheses(expression: str) -> bool:
    """Check if parentheses are balanced using a stack."""
    stack = Stack()
    pairs = {'(': ')', '[': ']', '{': '}'}

    for char in expression:
        if char in pairs:  # Opening bracket
            stack.push(char)
        elif char in pairs.values():  # Closing bracket
            if stack.is_empty():
                return False
            if pairs[stack.pop()] != char:
                return False

    return stack.is_empty()

# Test expressions
expressions = [
    "()",           # True
    "()[]{}", 
    "((()))",       # True
    "{[()]}",       # True
    "([)]",         # False
    "((())",        # False
    ")("            # False
]

for expr in expressions:
    result = "balanced" if is_balanced_parentheses(expr) else "unbalanced"
    print(f"'{expr}': {result}")

Browser History Management

class BrowserHistory:
    def __init__(self):
        self.history = Stack()
        self.forward_stack = Stack()
        self.current_page = None

    def visit(self, url: str):
        """Visit a new page."""
        if self.current_page:
            self.history.push(self.current_page)
        self.current_page = url
        self.forward_stack.clear()  # Clear forward history
        print(f"Visited: {url}")

    def back(self):
        """Go back to previous page."""
        if not self.history.is_empty():
            self.forward_stack.push(self.current_page)
            self.current_page = self.history.pop()
            print(f"Back to: {self.current_page}")
        else:
            print("No previous page")

    def forward(self):
        """Go forward to next page."""
        if not self.forward_stack.is_empty():
            self.history.push(self.current_page)
            self.current_page = self.forward_stack.pop()
            print(f"Forward to: {self.current_page}")
        else:
            print("No next page")

    def show_history(self):
        """Show browsing history."""
        print(f"Current: {self.current_page}")
        if not self.history.is_empty():
            print("History (most recent first):")
            for i, page in enumerate(self.history):
                print(f"  {i+1}: {page}")

# Usage
browser = BrowserHistory()
browser.visit("google.com")
browser.visit("github.com")
browser.visit("stackoverflow.com")
browser.show_history()

browser.back()
browser.back()
browser.forward()
browser.show_history()

Syntax Analysis

def evaluate_postfix(expression: str) -> float:
    """Evaluate postfix expression using stack."""
    stack = Stack()
    operators = {'+', '-', '*', '/', '//', '%', '**'}

    tokens = expression.split()

    for token in tokens:
        if token in operators:
            if len(stack) < 2:
                raise ValueError("Invalid expression")

            b = stack.pop()
            a = stack.pop()

            if token == '+':
                result = a + b
            elif token == '-':
                result = a - b
            elif token == '*':
                result = a * b
            elif token == '/':
                result = a / b
            elif token == '//':
                result = a // b
            elif token == '%':
                result = a % b
            elif token == '**':
                result = a ** b

            stack.push(result)
        else:
            # Operand
            try:
                number = float(token)
                stack.push(number)
            except ValueError:
                raise ValueError(f"Invalid token: {token}")

    if len(stack) != 1:
        raise ValueError("Invalid expression")

    return stack.pop()

# Test postfix expressions
expressions = [
    "3 4 +",           # 3 + 4 = 7
    "3 4 + 2 *",       # (3 + 4) * 2 = 14
    "15 7 1 1 + - / 3 *",  # 15 / (7 - (1 + 1)) * 3 = 9
]

for expr in expressions:
    try:
        result = evaluate_postfix(expr)
        print(f"'{expr}' = {result}")
    except ValueError as e:
        print(f"'{expr}' - Error: {e}")

Memory Management Simulation

class MemoryManager:
    """Simulate memory allocation using stack for free blocks."""

    def __init__(self, total_size: int):
        self.total_size = total_size
        self.allocated = {}  # address -> size
        self.free_blocks = Stack()

        # Initially, entire memory is one free block
        self.free_blocks.push((0, total_size))

    def allocate(self, size: int) -> int:
        """Allocate memory block of given size."""
        # Find suitable free block
        temp_stack = Stack()
        allocated_address = None

        while not self.free_blocks.is_empty():
            address, block_size = self.free_blocks.pop()

            if block_size >= size:
                # Use this block
                allocated_address = address
                self.allocated[address] = size

                # Return remaining space to free blocks
                if block_size > size:
                    remaining_address = address + size
                    remaining_size = block_size - size
                    temp_stack.push((remaining_address, remaining_size))

                break
            else:
                # Block too small, keep for later
                temp_stack.push((address, block_size))

        # Restore free blocks
        while not temp_stack.is_empty():
            self.free_blocks.push(temp_stack.pop())

        if allocated_address is not None:
            print(f"Allocated {size} bytes at address {allocated_address}")
            return allocated_address
        else:
            print(f"Failed to allocate {size} bytes - insufficient memory")
            return -1

    def deallocate(self, address: int):
        """Deallocate memory block at given address."""
        if address in self.allocated:
            size = self.allocated[address]
            del self.allocated[address]

            # Return block to free blocks
            self.free_blocks.push((address, size))
            print(f"Deallocated {size} bytes at address {address}")
        else:
            print(f"Invalid address {address}")

    def show_status(self):
        """Show memory status."""
        print("\nMemory Status:")
        print(f"Total size: {self.total_size}")
        print(f"Allocated blocks: {len(self.allocated)}")
        print(f"Free blocks: {len(self.free_blocks)}")

        allocated_size = sum(self.allocated.values())
        print(f"Allocated memory: {allocated_size}")
        print(f"Free memory: {self.total_size - allocated_size}")

# Usage
memory = MemoryManager(1000)
memory.show_status()

addr1 = memory.allocate(100)
addr2 = memory.allocate(200)
addr3 = memory.allocate(150)
memory.show_status()

memory.deallocate(addr2)
memory.show_status()

addr4 = memory.allocate(50)  # Should reuse freed space
memory.show_status()

Use Cases

When to Use Stacks

Good for:

  • Function call management
  • Expression evaluation and parsing
  • Undo/redo operations
  • Backtracking algorithms
  • Syntax analysis
  • Memory management
  • Browser history
  • Depth-first search traversals

Examples: 

# Function call stack
call_stack = Stack()
call_stack.push("main()")
call_stack.push("process_data()")
call_stack.push("validate_input()")

# Undo operations
undo_stack = Stack()
undo_stack.push("typed 'hello'")
undo_stack.push("deleted 2 chars")
undo_stack.push("typed 'world'")

# Navigation history
history = Stack()
history.push("/home")
history.push("/profile")
history.push("/settings")

When NOT to Use Stacks

Avoid for:

  • Random access to elements (use arrays/lists)
  • FIFO processing (use queues)
  • Searching sorted data (use trees/sorted arrays)
  • Frequent middle insertions/deletions

Better alternatives: 

# For random access, use list
random_access = [1, 2, 3, 4, 5]
print(random_access[2])  # Direct access to index 2

# For FIFO, use queue
from collections import deque
fifo_queue = deque()
fifo_queue.append(1)
fifo_queue.popleft()  # FIFO behavior

# For sorted operations, use sorted list or heap
import heapq
sorted_data = []
heapq.heappush(sorted_data, 3)
heapq.heappush(sorted_data, 1)

Performance Characteristics

Time Complexity Analysis

  • Push/Pop operations: O(1) - constant time
  • Peek/Top operations: O(1) - constant time
  • Search operations: O(n) - linear time
  • Memory allocation: O(1) per element (linked list)
  • Space overhead: Minimal (only node pointers)

Memory Efficiency

# Stack uses singly linked list internally
# Memory per element: data + one pointer
# No pre-allocation of fixed arrays
# Memory grows/shrinks dynamically

stack = Stack()
print(f"Empty stack memory efficient: {stack.is_empty()}")

# Memory usage scales linearly with elements
for i in range(1000):
    stack.push(i)
# Only allocates memory for actual elements

Comparison with Other Data Structures

Operation Stack List Deque Queue
Push/Add Top O(1) O(1) O(1) N/A
Pop/Remove Top O(1) O(1) O(1) N/A
Add Bottom N/A O(1) O(1) O(1)
Remove Bottom N/A O(n) O(1) O(1)
Random Access O(n) O(1) O(n) O(n)
Memory Overhead Low Medium Low Low
Use Case LIFO Random Access Both Ends FIFO

API Reference

Stack Implementation

A stack is a Last-In-First-Out (LIFO) data structure where elements are added and removed from the same end (called the top). It follows the principle that the last element added is the first one to be removed.

Key Features:

  • LIFO (Last In, First Out) ordering
  • Push operation adds element to top
  • Pop operation removes element from top
  • Peek operation views top element without removing it
  • Dynamic size allocation

Common Use Cases:

  • Function call management (call stack)
  • Expression evaluation and syntax parsing
  • Undo operations in applications
  • Backtracking algorithms
  • Browser history navigation

Time Complexities:

  • Push: O(1)
  • Pop: O(1)
  • Peek/Top: O(1)
  • Size: O(1)
  • Search: O(n)

Space Complexity: O(n)

Stack()

Bases: Generic[T]

A stack implementation using a singly linked list as the underlying data structure.

This implementation provides efficient O(1) push and pop operations by using the head of the linked list as the top of the stack.

Initialize an empty stack.

__contains__(value)

Check if a value exists in the stack.

__iter__()

Return an iterator over the stack elements.

Note: Iteration goes from top to bottom (most recent to oldest).

__len__()

Return the number of elements in the stack.

__repr__()

Return detailed string representation for debugging.

__str__()

Return string representation of the stack.

clear()

Remove all elements from the stack.

Time Complexity: O(1)

copy()

Create a shallow copy of the stack.

Time Complexity: O(n)

Returns:

Type Description
Stack[T]

A new Stack with the same elements

count(item)

Count the number of occurrences of an item in the stack.

Time Complexity: O(n)

Parameters:

Name Type Description Default
item T

Item to count

 required

Returns:

Type Description
int

Number of occurrences

extend(iterable)

Push all elements from an iterable onto the stack.

Time Complexity: O(k) where k is the number of elements

Parameters:

Name Type Description Default
iterable Any

Iterable containing elements to push

 required
Note

Elements are pushed in order, so the last element in the iterable will be at the top of the stack.

is_empty()

Check if the stack is empty.

Time Complexity: O(1)

Returns:

Type Description
bool

True if the stack is empty, False otherwise

peek()

Return the top element without removing it.

Time Complexity: O(1)

Returns:

Type Description
T

The top element of the stack

Raises:

Type Description
IndexError

If the stack is empty

pop()

Remove and return the top element from the stack.

Time Complexity: O(1)

Returns:

Type Description
T

The top element of the stack

Raises:

Type Description
IndexError

If the stack is empty

push(item)

Add an element to the top of the stack.

Time Complexity: O(1)

Parameters:

Name Type Description Default
item T

Element to add to the stack

 required

reverse()

Reverse the stack in place.

Time Complexity: O(n)

Note

After reversal, the bottom element becomes the top element.

search(item)

Search for an item in the stack and return its distance from the top.

Time Complexity: O(n)

Parameters:

Name Type Description Default
item T

Item to search for

 required

Returns:

Type Description
int

Distance from top (0-based), or -1 if not found
Note

Top element has distance 0, second element has distance 1, etc.

size()

Get the number of elements in the stack.

Time Complexity: O(1)

Returns:

Type Description
int

The number of elements in the stack

to_list()

Convert the stack to a Python list.

Time Complexity: O(n)

Returns:

Type Description
list[T]

A Python list with elements from top to bottom

top()

Alias for peek() - return the top element without removing it.

Time Complexity: O(1)

Returns:

Type Description
T

The top element of the stack

Raises:

Type Description
IndexError

If the stack is empty