📚 Stack Basics

Beginner to Intermediate ~20 min read ⭐ Essential

Imagine a stack of plates - you can only add or remove from the top! That's exactly how a Stack works. It's a LIFO (Last In, First Out) data structure where the last element added is the first one removed. Stacks power function calls, undo/redo, browser history, and expression evaluation!

🎯 Why Stacks Matter!

Stacks are EVERYWHERE:

✅ Function calls - Every function call uses a stack!
✅ Undo/Redo - Text editors, Photoshop, browsers
✅ Expression evaluation - Calculators, compilers
✅ Backtracking - Maze solving, Sudoku, DFS
✅ Browser history - Back button navigation

All operations are O(1) - super efficient!

The LIFO Principle

Last In, First Out

Think of a stack of plates:

Push (add) plates:
  [Plate 3] ← Last in (on top)
  [Plate 2]
  [Plate 1] ← First in (at bottom)

Pop (remove) plates:
  Remove Plate 3 first (last in, first out!)
  Then Plate 2
  Finally Plate 1

Key insight: You can only access the TOP element!

See It in Action

Watch LIFO in action:

Stack Operations

Three Core Operations

1. Push - Add to Top

stack.push(10)  # Add 10 to top
stack.push(20)  # Add 20 to top (now top is 20)

Time: O(1), Space: O(1)

2. Pop - Remove from Top

value = stack.pop()  # Remove and return top (20)
# Now top is 10

Time: O(1), Space: O(1)

3. Peek - View Top (without removing)

top = stack.peek()  # View top without removing
# Stack unchanged

Time: O(1), Space: O(1)

Implementation 1: Array-based Stack

Using Dynamic Array

class StackArray:
    def __init__(self):
        self.items = []  # Python list (dynamic array)
    
    def push(self, item):
        self.items.append(item)  # O(1) amortized
    
    def pop(self):
        if self.is_empty():
            return None
        return self.items.pop()  # O(1)
    
    def peek(self):
        if self.is_empty():
            return None
        return self.items[-1]  # O(1)
    
    def is_empty(self):
        return len(self.items) == 0  # O(1)
    
    def size(self):
        return len(self.items)  # O(1)

Pros: Simple, cache-friendly, less memory overhead

Cons: May need resizing (amortized O(1))

Implementation 2: Linked List-based Stack

Using Linked List

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

class StackLinkedList:
    def __init__(self):
        self.top = None
        self._size = 0
    
    def push(self, item):
        new_node = Node(item)
        new_node.next = self.top
        self.top = new_node
        self._size += 1  # O(1)
    
    def pop(self):
        if self.is_empty():
            return None
        item = self.top.data
        self.top = self.top.next
        self._size -= 1
        return item  # O(1)
    
    def peek(self):
        if self.is_empty():
            return None
        return self.top.data  # O(1)
    
    def is_empty(self):
        return self.top is None  # O(1)
    
    def size(self):
        return self._size  # O(1)

Pros: No resizing, truly O(1) push

Cons: More memory (pointers), worse cache performance

The Complete Code

"""
Stack Basics - LIFO (Last In, First Out)
Two implementations: Array-based and Linked List-based
Essential data structure for function calls, undo/redo, expression evaluation!
"""

# ============================================================================
# IMPLEMENTATION 1: Stack with Array (Dynamic)
# ============================================================================

class StackArray:
    """Stack implementation using dynamic array (Python list)"""
    
    def __init__(self, capacity=10):
        self.items = []
        self.capacity = capacity
    
    def push(self, item):
        """
        Push item onto stack - O(1) amortized
        """
        if len(self.items) >= self.capacity:
            print(f"⚠️  Stack at capacity ({self.capacity}), auto-resizing...")
            self.capacity *= 2
        
        self.items.append(item)
        print(f"➕ Pushed {item} onto stack")
    
    def pop(self):
        """
        Pop item from stack - O(1)
        """
        if self.is_empty():
            print("✗ Cannot pop - stack is empty!")
            return None
        
        item = self.items.pop()
        print(f"➖ Popped {item} from stack")
        return item
    
    def peek(self):
        """
        View top item without removing - O(1)
        """
        if self.is_empty():
            print("✗ Cannot peek - stack is empty!")
            return None
        
        return self.items[-1]
    
    def is_empty(self):
        """Check if stack is empty - O(1)"""
        return len(self.items) == 0
    
    def size(self):
        """Get stack size - O(1)"""
        return len(self.items)
    
    def display(self):
        """Display stack contents"""
        if self.is_empty():
            print("Stack: (empty)")
            return
        
        print("\nStack (top to bottom):")
        for i in range(len(self.items) - 1, -1, -1):
            if i == len(self.items) - 1:
                print(f"  TOP  → [{self.items[i]}]")
            else:
                print(f"         [{self.items[i]}]")
        print()

# ============================================================================
# IMPLEMENTATION 2: Stack with Linked List
# ============================================================================

class Node:
    """Node for linked list-based stack"""
    def __init__(self, data):
        self.data = data
        self.next = None

class StackLinkedList:
    """Stack implementation using linked list"""
    
    def __init__(self):
        self.top = None
        self._size = 0
    
    def push(self, item):
        """
        Push item onto stack - O(1)
        Always add at head (top of stack)
        """
        new_node = Node(item)
        new_node.next = self.top
        self.top = new_node
        self._size += 1
        print(f"➕ Pushed {item} onto stack")
    
    def pop(self):
        """
        Pop item from stack - O(1)
        Remove from head (top of stack)
        """
        if self.is_empty():
            print("✗ Cannot pop - stack is empty!")
            return None
        
        item = self.top.data
        self.top = self.top.next
        self._size -= 1
        print(f"➖ Popped {item} from stack")
        return item
    
    def peek(self):
        """
        View top item without removing - O(1)
        """
        if self.is_empty():
            print("✗ Cannot peek - stack is empty!")
            return None
        
        return self.top.data
    
    def is_empty(self):
        """Check if stack is empty - O(1)"""
        return self.top is None
    
    def size(self):
        """Get stack size - O(1)"""
        return self._size
    
    def display(self):
        """Display stack contents"""
        if self.is_empty():
            print("Stack: (empty)")
            return
        
        print("\nStack (top to bottom):")
        current = self.top
        first = True
        while current:
            if first:
                print(f"  TOP  → [{current.data}]")
                first = False
            else:
                print(f"         [{current.data}]")
            current = current.next
        print()

# ============================================================================
# EXAMPLE 1: Array-based Stack
# ============================================================================

print("=" * 70)
print("Example 1: Stack with Array")
print("=" * 70)

stack_arr = StackArray(capacity=5)

print("\nPushing elements:")
for val in [10, 20, 30, 40, 50]:
    stack_arr.push(val)
    stack_arr.display()

print("─" * 70)
print(f"Peek (top element): {stack_arr.peek()}")
print(f"Stack size: {stack_arr.size()}")

print("\n" + "─" * 70)
print("Popping elements:")
for _ in range(3):
    stack_arr.pop()
    stack_arr.display()

print("─" * 70)
print(f"Peek after pops: {stack_arr.peek()}")
print(f"Stack size: {stack_arr.size()}")

# ============================================================================
# EXAMPLE 2: Linked List-based Stack
# ============================================================================

print("\n" + "=" * 70)
print("Example 2: Stack with Linked List")
print("=" * 70)

stack_ll = StackLinkedList()

print("\nPushing elements:")
for val in ['A', 'B', 'C', 'D', 'E']:
    stack_ll.push(val)
    stack_ll.display()

print("─" * 70)
print(f"Peek (top element): {stack_ll.peek()}")
print(f"Stack size: {stack_ll.size()}")

print("\n" + "─" * 70)
print("Popping elements:")
for _ in range(3):
    stack_ll.pop()
    stack_ll.display()

# ============================================================================
# EXAMPLE 3: LIFO Demonstration
# ============================================================================

print("\n" + "=" * 70)
print("Example 3: LIFO (Last In, First Out) Demonstration")
print("=" * 70)

stack = StackArray()

print("\nScenario: Function Call Stack")
print("Simulating nested function calls:\n")

functions = ["main()", "processData()", "validateInput()", "checkFormat()"]

print("Calling functions (push onto stack):")
for func in functions:
    stack.push(func)
    print(f"  → Entered {func}")

stack.display()

print("Returning from functions (pop from stack):")
while not stack.is_empty():
    func = stack.pop()
    print(f"  ← Exited {func}")

print("\nNotice: Last function called is first to return!")
print("This is LIFO in action!")

# ============================================================================
# EXAMPLE 4: Edge Cases
# ============================================================================

print("\n" + "=" * 70)
print("Example 4: Edge Cases")
print("=" * 70)

edge_stack = StackArray()

print("\n1. Pop from empty stack:")
edge_stack.pop()

print("\n2. Peek at empty stack:")
result = edge_stack.peek()
print(f"   Result: {result}")

print("\n3. Check if empty:")
print(f"   Is empty? {edge_stack.is_empty()}")

print("\n4. Push one element:")
edge_stack.push(100)
print(f"   Is empty? {edge_stack.is_empty()}")
print(f"   Size: {edge_stack.size()}")

print("\n5. Pop last element:")
edge_stack.pop()
print(f"   Is empty? {edge_stack.is_empty()}")

# ============================================================================
# COMPARISON: Array vs Linked List
# ============================================================================

print("\n" + "=" * 70)
print("Array vs Linked List Implementation Comparison")
print("=" * 70)

print(f"\n{'Operation':<20} {'Array':<20} {'Linked List':<20} {'Winner':<15}")
print("─" * 70)
print(f"{'Push':<20} {'O(1) amortized':<20} {'O(1)':<20} {'Linked List':<15}")
print(f"{'Pop':<20} {'O(1)':<20} {'O(1)':<20} {'Tie':<15}")
print(f"{'Peek':<20} {'O(1)':<20} {'O(1)':<20} {'Tie':<15}")
print(f"{'Is Empty':<20} {'O(1)':<20} {'O(1)':<20} {'Tie':<15}")
print(f"{'Size':<20} {'O(1)':<20} {'O(1)':<20} {'Tie':<15}")
print(f"{'Memory overhead':<20} {'Less (contiguous)':<20} {'More (pointers)':<20} {'Array':<15}")
print(f"{'Cache performance':<20} {'Better':<20} {'Worse':<20} {'Array':<15}")
print(f"{'Dynamic resizing':<20} {'Needed':<20} {'Not needed':<20} {'Linked List':<15}")

# ============================================================================
# WHEN TO USE EACH
# ============================================================================

print("\n" + "=" * 70)
print("When to Use Each Implementation")
print("=" * 70)

print("\n✅ USE ARRAY-BASED STACK WHEN:")
print("  • Size is predictable")
print("  • Memory efficiency is important")
print("  • Cache performance matters")
print("  • Simple implementation preferred")

print("\n✅ USE LINKED LIST-BASED STACK WHEN:")
print("  • Size is unpredictable")
print("  • No resizing overhead acceptable")
print("  • Memory fragmentation not a concern")
print("  • Already using linked structures")

# ============================================================================
# COMPLEXITY ANALYSIS
# ============================================================================

print("\n" + "=" * 70)
print("Complexity Analysis")
print("=" * 70)

print(f"\n{'Operation':<20} {'Time Complexity':<25} {'Space Complexity':<20}")
print("─" * 70)
print(f"{'Push':<20} {'O(1) amortized':<25} {'O(1)':<20}")
print(f"{'Pop':<20} {'O(1)':<25} {'O(1)':<20}")
print(f"{'Peek':<20} {'O(1)':<25} {'O(1)':<20}")
print(f"{'Is Empty':<20} {'O(1)':<25} {'O(1)':<20}")
print(f"{'Size':<20} {'O(1)':<25} {'O(1)':<20}")

print("\nNote: All operations are O(1) - constant time!")
print("This makes stack extremely efficient!")

# ============================================================================
# REAL-WORLD APPLICATIONS
# ============================================================================

print("\n" + "=" * 70)
print("Real-World Applications of Stacks")
print("=" * 70)

print("\n1. Function Call Stack")
print("   • Every function call pushes onto stack")
print("   • Return pops from stack")
print("   • Enables recursion!")

print("\n2. Undo/Redo Functionality")
print("   • Text editors (Ctrl+Z)")
print("   • Photoshop layers")
print("   • Browser back button")

print("\n3. Expression Evaluation")
print("   • Infix to postfix conversion")
print("   • Calculator implementation")
print("   • Compiler syntax checking")

print("\n4. Backtracking Algorithms")
print("   • Maze solving")
print("   • Sudoku solver")
print("   • Tree/graph traversal (DFS)")

print("\n5. Browser History")
print("   • Back button navigation")
print("   • Forward button (with second stack)")

# ============================================================================
# INTERVIEW TIPS
# ============================================================================

print("\n" + "=" * 70)
print("Interview Tips")
print("=" * 70)

print("\n✅ Always mention LIFO principle!")
print("✅ Know both array and linked list implementations")
print("✅ All operations are O(1) - emphasize this!")
print("✅ Discuss trade-offs: array vs linked list")
print("✅ Common follow-up: Implement Min Stack (O(1) getMin)")
print("✅ Know applications: function calls, undo/redo, expression eval")

# ============================================================================
# KEY TAKEAWAYS
# ============================================================================

print("\n" + "=" * 70)
print("Key Takeaways")
print("=" * 70)

print("\n✓ Stack is LIFO - Last In, First Out")
print("✓ All operations are O(1) - super efficient!")
print("✓ Two implementations: array and linked list")
print("✓ Array: better cache, needs resizing")
print("✓ Linked list: no resizing, more memory overhead")
print("✓ Used everywhere: function calls, undo/redo, expression eval")
print("✓ Foundation for many algorithms!")

Output

Click Run to execute your code

Array vs Linked List Comparison

Aspect	Array	Linked List	Winner
Push	O(1) amortized	O(1) ✓	Linked List
Pop	O(1)	O(1)	Tie
Peek	O(1)	O(1)	Tie
Memory	Less ✓	More (pointers)	Array
Cache	Better ✓	Worse	Array
Resizing	Needed	Not needed ✓	Linked List

Real-World Applications

Where Stacks Are Used

1. Function Call Stack

main() {
    processData();  // Push main
}

processData() {
    validate();     // Push processData
}

validate() {
    return;         // Pop validate
                    // Pop processData
                    // Pop main
}

2. Undo/Redo

Undo stack: Push each action
Ctrl+Z: Pop from undo stack
Redo: Use second stack

3. Expression Evaluation

Infix to postfix conversion
Evaluate postfix expressions
Check balanced parentheses

4. Browser History

Back button: Pop from history stack
Visit new page: Push to stack

Common Mistakes

❌ Mistake #1: Not Checking Empty

# WRONG - crashes if empty!
value = stack.pop()

# RIGHT - check first
if not stack.is_empty():
    value = stack.pop()
else:
    print("Stack is empty!")

❌ Mistake #2: Confusing Peek and Pop

# Peek - view without removing
top = stack.peek()  # Stack unchanged

# Pop - remove and return
top = stack.pop()   # Stack changed!

Interview Tips

💡 How to Ace Stack Questions

✅ Always mention LIFO! Show you understand the principle
✅ All operations are O(1) - emphasize efficiency
✅ Know both implementations - array and linked list
✅ Discuss trade-offs - memory vs cache performance
✅ Check for empty - before pop/peek
✅ Know applications - function calls, undo/redo, expression eval

Summary

Stack Basics Mastery

LIFO Principle: Last In, First Out
Three Operations: Push, Pop, Peek (all O(1))
Two Implementations: Array (cache-friendly) and Linked List (no resizing)
Applications: Function calls, undo/redo, expression evaluation, backtracking
Key Advantage: All operations are O(1) - super efficient!

Interview tip: Stacks are simple but powerful! Always check for empty before pop/peek. Know the difference between array and linked list implementations!

What's Next?

You've mastered stack basics! Next: Stack Applications - expression evaluation, balanced parentheses, and more!

Practice: Implement both array and linked list versions. Try the LIFO demo!

Previous Advanced Linked List

Next Stack Applications

🎯 Why Stacks Matter!

The LIFO Principle

Last In, First Out

See It in Action

Stack Operations

Three Core Operations

1. Push - Add to Top

2. Pop - Remove from Top

3. Peek - View Top (without removing)

Implementation 1: Array-based Stack

Using Dynamic Array

Implementation 2: Linked List-based Stack

Using Linked List

The Complete Code

Array vs Linked List Comparison

Real-World Applications

Where Stacks Are Used

1. Function Call Stack

2. Undo/Redo

3. Expression Evaluation

4. Browser History

Common Mistakes

❌ Mistake #1: Not Checking Empty

❌ Mistake #2: Confusing Peek and Pop

Interview Tips

💡 How to Ace Stack Questions

Summary

Stack Basics Mastery

What's Next?

Enjoying these tutorials?