Stack - CodeHQ

Core Implementation

Array-based Stack

class ArrayStack:
    def __init__(self, capacity=10):
        self.capacity = capacity
        self.stack = [None] * capacity
        self.top = -1
    
    def push(self, item):
        if self.is_full():
            self._resize(2 * self.capacity)
        self.top += 1
        self.stack[self.top] = item
    
    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        item = self.stack[self.top]
        self.stack[self.top] = None  # Help garbage collection
        self.top -= 1
        return item
    
    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.stack[self.top]
    
    def is_empty(self):
        return self.top == -1
    
    def is_full(self):
        return self.top == self.capacity - 1
    
    def _resize(self, new_capacity):
        new_stack = [None] * new_capacity
        for i in range(self.top + 1):
            new_stack[i] = self.stack[i]
        self.stack = new_stack
        self.capacity = new_capacity

Linked List-based Stack

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

class LinkedStack:
    def __init__(self):
        self.head = None
        self.size = 0
    
    def push(self, item):
        new_node = Node(item)
        new_node.next = self.head
        self.head = new_node
        self.size += 1
    
    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        item = self.head.data
        self.head = self.head.next
        self.size -= 1
        return item
    
    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.head.data
    
    def is_empty(self):
        return self.head is None

Implementation Variations

1. Min Stack (with O(1) min operations)

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []
    
    def push(self, item):
        self.stack.append(item)
        if not self.min_stack or item <= self.min_stack[-1]:
            self.min_stack.append(item)
    
    def pop(self):
        if not self.stack:
            raise IndexError("Stack is empty")
        item = self.stack.pop()
        if item == self.min_stack[-1]:
            self.min_stack.pop()
        return item
    
    def get_min(self):
        if not self.min_stack:
            raise IndexError("Stack is empty")
        return self.min_stack[-1]

2. Thread-Safe Stack

from threading import Lock

class ThreadSafeStack:
    def __init__(self):
        self.stack = []
        self.lock = Lock()
    
    def push(self, item):
        with self.lock:
            self.stack.append(item)
    
    def pop(self):
        with self.lock:
            if not self.stack:
                raise IndexError("Stack is empty")
            return self.stack.pop()

Time Complexities

Operation	Array Stack	Linked Stack	Min Stack	Thread-Safe Stack
Push	O(1)*	O(1)	O(1)	O(1)**
Pop	O(1)	O(1)	O(1)	O(1)**
Peek	O(1)	O(1)	O(1)	O(1)**
Get Min	N/A	N/A	O(1)	N/A
Is Empty	O(1)	O(1)	O(1)	O(1)**

* Amortized for dynamic arrays ** Not counting lock acquisition time

Space Complexities

Implementation	Space Complexity	Additional Notes
Array Stack	O(n)	Contiguous memory, may have unused space
Linked Stack	O(n)	Extra space for node pointers
Min Stack	O(n)	Additional stack for minimums
Thread-Safe Stack	O(n)	Additional space for synchronization

Common Data Structure Patterns

Parentheses Matching
- Bracket validation
- Expression balancing
- Nested structure validation
Expression Evaluation
- Postfix evaluation
- Infix to postfix conversion
- Calculator implementation
Backtracking
- DFS implementation
- History tracking
- Undo operations
Monotonic Stack
- Next greater element
- Histogram area
- Temperature patterns
Stack of Stacks
- Set of plates
- Memory management
- Multi-stack systems
Function Call Stack
- Recursion management
- Call history
- Stack frames

Edge Cases to Consider

Empty Stack

def pop(self):
    if self.is_empty():
        raise IndexError("Stack underflow")
    # ... pop implementation

Full Stack (Array Implementation)

def push(self, item):
    if self.is_full():
        # Either resize or raise error
        raise OverflowError("Stack overflow")
    # ... push implementation

Single Element

def pop(self):
    if self.size == 1:
        item = self.top.data
        self.top = None
        self.size = 0
        return item

Optimization Techniques

Capacity Management

class OptimizedArrayStack:
    def __init__(self):
        self.min_capacity = 8
        self.stack = [None] * self.min_capacity
        self.size = 0
    
    def _resize(self, new_capacity):
        if new_capacity < self.min_capacity:
            new_capacity = self.min_capacity
        new_stack = [None] * new_capacity
        for i in range(self.size):
            new_stack[i] = self.stack[i]
        self.stack = new_stack
    
    def push(self, item):
        if self.size == len(self.stack):
            self._resize(2 * len(self.stack))
        self.stack[self.size] = item
        self.size += 1
    
    def pop(self):
        if self.size == 0:
            raise IndexError("Stack is empty")
        self.size -= 1
        item = self.stack[self.size]
        self.stack[self.size] = None
        if self.size < len(self.stack) // 4:
            self._resize(len(self.stack) // 2)
        return item

Memory Pool for Linked Stack

class NodePool:
    def __init__(self, pool_size=1000):
        self.pool = [Node(None) for _ in range(pool_size)]
        self.available = list(range(pool_size))
    
    def get_node(self, data):
        if self.available:
            node = self.pool[self.available.pop()]
            node.data = data
            return node
        return Node(data)
    
    def return_node(self, node):
        if len(self.available) < len(self.pool):
            node.next = None
            node.data = None
            self.available.append(node)

Memory Management

Reference Cleanup

def clear(self):
    while not self.is_empty():
        self.pop()  # Properly remove references
    self.top = None  # Clear remaining reference

Stack Shrinking

def shrink_to_fit(self):
    if self.size < self.capacity:
        new_stack = [None] * self.size
        for i in range(self.size):
            new_stack[i] = self.stack[i]
        self.stack = new_stack
        self.capacity = self.size

Performance Considerations

Batch Operations

def push_many(self, items):
    required_capacity = self.size + len(items)
    if required_capacity > self.capacity:
        self._resize(max(required_capacity, 2 * self.capacity))
    for item in items:
        self.stack[self.size] = item
        self.size += 1

Cache-Friendly Implementation

class CacheFriendlyStack:
    def __init__(self):
        self.block_size = 64  # Cache line size
        self.stack = bytearray(self.block_size * 16)  # Aligned memory
        self.size = 0

Common Pitfalls

Pop from Empty Stack

# Wrong
def pop(self):
    return self.stack.pop()  # Can raise IndexError

# Correct
def pop(self):
    if self.is_empty():
        raise IndexError("Stack is empty")
    return self.stack.pop()

Memory Leak in Object Stack

# Memory leak
def pop(self):
    return self.stack[self.top--]

# Correct
def pop(self):
    item = self.stack[self.top]
    self.stack[self.top] = None  # Clear reference
    self.top -= 1
    return item

Incorrect Size Management

# Wrong
def push(self, item):
    self.top += 1
    self.stack[self.top] = item
    # Missing size increment

# Correct
def push(self, item):
    self.top += 1
    self.stack[self.top] = item
    self.size += 1

On this page

Core Implementation
Array-based Stack
Linked List-based Stack
Implementation Variations
1. Min Stack (with O(1) min operations)
2. Thread-Safe Stack
Time Complexities
Space Complexities
Common Data Structure Patterns
Edge Cases to Consider
Optimization Techniques
Memory Management
Performance Considerations
Common Pitfalls

Core Implementation

Array-based Stack

class ArrayStack:
    def __init__(self, capacity=10):
        self.capacity = capacity
        self.stack = [None] * capacity
        self.top = -1
    
    def push(self, item):
        if self.is_full():
            self._resize(2 * self.capacity)
        self.top += 1
        self.stack[self.top] = item
    
    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        item = self.stack[self.top]
        self.stack[self.top] = None  # Help garbage collection
        self.top -= 1
        return item
    
    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.stack[self.top]
    
    def is_empty(self):
        return self.top == -1
    
    def is_full(self):
        return self.top == self.capacity - 1
    
    def _resize(self, new_capacity):
        new_stack = [None] * new_capacity
        for i in range(self.top + 1):
            new_stack[i] = self.stack[i]
        self.stack = new_stack
        self.capacity = new_capacity

Linked List-based Stack

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

class LinkedStack:
    def __init__(self):
        self.head = None
        self.size = 0
    
    def push(self, item):
        new_node = Node(item)
        new_node.next = self.head
        self.head = new_node
        self.size += 1
    
    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        item = self.head.data
        self.head = self.head.next
        self.size -= 1
        return item
    
    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.head.data
    
    def is_empty(self):
        return self.head is None

Implementation Variations

1. Min Stack (with O(1) min operations)

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []
    
    def push(self, item):
        self.stack.append(item)
        if not self.min_stack or item <= self.min_stack[-1]:
            self.min_stack.append(item)
    
    def pop(self):
        if not self.stack:
            raise IndexError("Stack is empty")
        item = self.stack.pop()
        if item == self.min_stack[-1]:
            self.min_stack.pop()
        return item
    
    def get_min(self):
        if not self.min_stack:
            raise IndexError("Stack is empty")
        return self.min_stack[-1]

2. Thread-Safe Stack

from threading import Lock

class ThreadSafeStack:
    def __init__(self):
        self.stack = []
        self.lock = Lock()
    
    def push(self, item):
        with self.lock:
            self.stack.append(item)
    
    def pop(self):
        with self.lock:
            if not self.stack:
                raise IndexError("Stack is empty")
            return self.stack.pop()

Time Complexities

Operation	Array Stack	Linked Stack	Min Stack	Thread-Safe Stack
Push	O(1)*	O(1)	O(1)	O(1)**
Pop	O(1)	O(1)	O(1)	O(1)**
Peek	O(1)	O(1)	O(1)	O(1)**
Get Min	N/A	N/A	O(1)	N/A
Is Empty	O(1)	O(1)	O(1)	O(1)**

* Amortized for dynamic arrays ** Not counting lock acquisition time

Space Complexities

Implementation	Space Complexity	Additional Notes
Array Stack	O(n)	Contiguous memory, may have unused space
Linked Stack	O(n)	Extra space for node pointers
Min Stack	O(n)	Additional stack for minimums
Thread-Safe Stack	O(n)	Additional space for synchronization

Common Data Structure Patterns

Parentheses Matching
- Bracket validation
- Expression balancing
- Nested structure validation
Expression Evaluation
- Postfix evaluation
- Infix to postfix conversion
- Calculator implementation
Backtracking
- DFS implementation
- History tracking
- Undo operations
Monotonic Stack
- Next greater element
- Histogram area
- Temperature patterns
Stack of Stacks
- Set of plates
- Memory management
- Multi-stack systems
Function Call Stack
- Recursion management
- Call history
- Stack frames

Edge Cases to Consider

Empty Stack

def pop(self):
    if self.is_empty():
        raise IndexError("Stack underflow")
    # ... pop implementation

Full Stack (Array Implementation)

def push(self, item):
    if self.is_full():
        # Either resize or raise error
        raise OverflowError("Stack overflow")
    # ... push implementation

Single Element

def pop(self):
    if self.size == 1:
        item = self.top.data
        self.top = None
        self.size = 0
        return item

Optimization Techniques

Capacity Management

class OptimizedArrayStack:
    def __init__(self):
        self.min_capacity = 8
        self.stack = [None] * self.min_capacity
        self.size = 0
    
    def _resize(self, new_capacity):
        if new_capacity < self.min_capacity:
            new_capacity = self.min_capacity
        new_stack = [None] * new_capacity
        for i in range(self.size):
            new_stack[i] = self.stack[i]
        self.stack = new_stack
    
    def push(self, item):
        if self.size == len(self.stack):
            self._resize(2 * len(self.stack))
        self.stack[self.size] = item
        self.size += 1
    
    def pop(self):
        if self.size == 0:
            raise IndexError("Stack is empty")
        self.size -= 1
        item = self.stack[self.size]
        self.stack[self.size] = None
        if self.size < len(self.stack) // 4:
            self._resize(len(self.stack) // 2)
        return item

Memory Pool for Linked Stack

class NodePool:
    def __init__(self, pool_size=1000):
        self.pool = [Node(None) for _ in range(pool_size)]
        self.available = list(range(pool_size))
    
    def get_node(self, data):
        if self.available:
            node = self.pool[self.available.pop()]
            node.data = data
            return node
        return Node(data)
    
    def return_node(self, node):
        if len(self.available) < len(self.pool):
            node.next = None
            node.data = None
            self.available.append(node)

Memory Management

Reference Cleanup

def clear(self):
    while not self.is_empty():
        self.pop()  # Properly remove references
    self.top = None  # Clear remaining reference

Stack Shrinking

def shrink_to_fit(self):
    if self.size < self.capacity:
        new_stack = [None] * self.size
        for i in range(self.size):
            new_stack[i] = self.stack[i]
        self.stack = new_stack
        self.capacity = self.size

Performance Considerations

Batch Operations

def push_many(self, items):
    required_capacity = self.size + len(items)
    if required_capacity > self.capacity:
        self._resize(max(required_capacity, 2 * self.capacity))
    for item in items:
        self.stack[self.size] = item
        self.size += 1

Cache-Friendly Implementation

class CacheFriendlyStack:
    def __init__(self):
        self.block_size = 64  # Cache line size
        self.stack = bytearray(self.block_size * 16)  # Aligned memory
        self.size = 0

Common Pitfalls

Pop from Empty Stack

# Wrong
def pop(self):
    return self.stack.pop()  # Can raise IndexError

# Correct
def pop(self):
    if self.is_empty():
        raise IndexError("Stack is empty")
    return self.stack.pop()

Memory Leak in Object Stack

# Memory leak
def pop(self):
    return self.stack[self.top--]

# Correct
def pop(self):
    item = self.stack[self.top]
    self.stack[self.top] = None  # Clear reference
    self.top -= 1
    return item

Incorrect Size Management

# Wrong
def push(self, item):
    self.top += 1
    self.stack[self.top] = item
    # Missing size increment

# Correct
def push(self, item):
    self.top += 1
    self.stack[self.top] = item
    self.size += 1

On this page

Core Implementation
Array-based Stack
Linked List-based Stack
Implementation Variations
1. Min Stack (with O(1) min operations)
2. Thread-Safe Stack
Time Complexities
Space Complexities
Common Data Structure Patterns
Edge Cases to Consider
Optimization Techniques
Memory Management
Performance Considerations
Common Pitfalls

​Core Implementation

​Array-based Stack

​Linked List-based Stack

​Implementation Variations

​1. Min Stack (with O(1) min operations)

​2. Thread-Safe Stack

​Time Complexities

​Space Complexities

​Common Data Structure Patterns

​Edge Cases to Consider

​Optimization Techniques

​Memory Management

​Performance Considerations

​Common Pitfalls

Behavioral

​Core Implementation

​Array-based Stack

​Linked List-based Stack

​Implementation Variations

​1. Min Stack (with O(1) min operations)

​2. Thread-Safe Stack

​Time Complexities

​Space Complexities

​Common Data Structure Patterns

​Edge Cases to Consider

​Optimization Techniques

​Memory Management

​Performance Considerations

​Common Pitfalls

Core Implementation

Array-based Stack

Linked List-based Stack

Implementation Variations

1. Min Stack (with O(1) min operations)

2. Thread-Safe Stack

Time Complexities

Space Complexities

Common Data Structure Patterns

Edge Cases to Consider

Optimization Techniques

Memory Management

Performance Considerations

Common Pitfalls

Core Implementation

Array-based Stack

Linked List-based Stack

Implementation Variations

1. Min Stack (with O(1) min operations)

2. Thread-Safe Stack

Time Complexities

Space Complexities

Common Data Structure Patterns

Edge Cases to Consider

Optimization Techniques

Memory Management

Performance Considerations

Common Pitfalls