​
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

OperationArray StackLinked StackMin StackThread-Safe Stack
PushO(1)*O(1)O(1)O(1)**
PopO(1)O(1)O(1)O(1)**
PeekO(1)O(1)O(1)O(1)**
Get MinN/AN/AO(1)N/A
Is EmptyO(1)O(1)O(1)O(1)**

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

​
Space Complexities

ImplementationSpace ComplexityAdditional Notes
Array StackO(n)Contiguous memory, may have unused space
Linked StackO(n)Extra space for node pointers
Min StackO(n)Additional stack for minimums
Thread-Safe StackO(n)Additional space for synchronization

​
Common Data Structure Patterns

  1. Parentheses Matching

    • Bracket validation
    • Expression balancing
    • Nested structure validation

  2. Expression Evaluation

    • Postfix evaluation
    • Infix to postfix conversion
    • Calculator implementation

  3. Backtracking

    • DFS implementation
    • History tracking
    • Undo operations

  4. Monotonic Stack

    • Next greater element
    • Histogram area
    • Temperature patterns

  5. Stack of Stacks

    • Set of plates
    • Memory management
    • Multi-stack systems

  6. Function Call Stack

    • Recursion management
    • Call history
    • Stack frames

​
Edge Cases to Consider

  1. Empty Stack
def pop(self):
    if self.is_empty():
        raise IndexError("Stack underflow")
    # ... pop implementation
  1. Full Stack (Array Implementation)
def push(self, item):
    if self.is_full():
        # Either resize or raise error
        raise OverflowError("Stack overflow")
    # ... push implementation
  1. Single Element
def pop(self):
    if self.size == 1:
        item = self.top.data
        self.top = None
        self.size = 0
        return item

​
Optimization Techniques

  1. 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
  1. 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

  1. Reference Cleanup
def clear(self):
    while not self.is_empty():
        self.pop()  # Properly remove references
    self.top = None  # Clear remaining reference
  1. 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

  1. 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
  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

  1. 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()
  1. 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
  1. 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
Linked listQueue