Stacks

Introduction

Stacks are one of the most fundamental data structures in computer science, following the Last-In-First-Out (LIFO) principle. From validating parentheses to implementing undo functionality, stacks power countless algorithms and applications.

In this guide, we’ll explore classic stack problems with clean, production-ready solutions in both C# and Python.

What is a Stack?

A stack is a linear data structure that follows the LIFO principle:

• Push: Add an element to the top
• Pop: Remove the top element
• Peek/Top: View the top element without removing it

Think of it like a stack of plates—you can only add or remove from the top.

Common Use Cases

• Expression evaluation and syntax parsing
• Backtracking algorithms (maze solving, game states)
• Function call management (call stack)
• Undo/Redo functionality
• Browser history navigation

Problem 1: Valid Parentheses

Difficulty: Easy
Tags: Stack, String

Problem Statement

Given a string containing only the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets
2. Open brackets must be closed in the correct order

Examples

Input: s = "()"
Output: true

Input: s = "()[]{}"
Output: true

Input: s = "(]"
Output: false

Input: s = "([)]"
Output: false

Approach

Use a stack to track opening brackets. When encountering a closing bracket, check if it matches the most recent opening bracket (top of stack). If the stack is empty at the end, all brackets were properly matched.

C# Solution

public class Solution 
{
    public bool IsValid(string s) 
    {
        Stack<char> stack = new Stack<char>();
        Dictionary<char, char> pairs = new Dictionary<char, char>
        {
            {'(', ')'},
            {'[', ']'},
            {'{', '}'}
        };
        
        foreach (char ch in s) 
        {
            // If it's an opening bracket, push it
            if (pairs.ContainsKey(ch)) 
            {
                stack.Push(ch);
            } 
            // If it's a closing bracket
            else 
            {
                // Check if stack is empty or top doesn't match
                if (stack.Count == 0 || pairs[stack.Pop()] != ch) 
                {
                    return false;
                }
            }
        }
        
        return stack.Count == 0;
    }
}

Python Solution

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        pairs = {'(': ')', '[': ']', '{': '}'}
        
        for ch in s:
            # If opening bracket, push to stack
            if ch in pairs:
                stack.append(ch)
            # If closing bracket
            else:
                # Check if stack is empty or doesn't match
                if not stack or pairs[stack.pop()] != ch:
                    return False
        
        return len(stack) == 0

Time Complexity: O(n) where n is the length of the string
Space Complexity: O(n) for the stack in worst case

Key Insights

• Only opening brackets go onto the stack
• Every closing bracket must match the most recent opening bracket
• An empty stack at the end means all brackets were matched
• Return false immediately if a mismatch is found

Problem 2: Reverse Linked List

Difficulty: Easy
Tags: Linked List, Two Pointers, Recursion

Problem Statement

Given the head of a singly linked list, reverse the list and return the reversed list.

Example

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Approach 1: Iterative Solution

Use three pointers to reverse the direction of each link:

1. Store the next node before breaking the link
2. Reverse the current node’s pointer
3. Move all pointers one step forward

C# Iterative Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */

public class Solution 
{
    public ListNode ReverseList(ListNode head) 
    {
        ListNode prev = null;
        ListNode current = head;
        
        while (current != null) 
        {
            ListNode next = current.next;  // Store next node
            current.next = prev;            // Reverse the link
            prev = current;                 // Move prev forward
            current = next;                 // Move current forward
        }
        
        return prev;
    }
}

Python Iterative Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        current = head
        
        while current:
            next_node = current.next  # Store next node
            current.next = prev        # Reverse the link
            prev = current             # Move prev forward
            current = next_node        # Move current forward
        
        return prev

Time Complexity: O(n)
Space Complexity: O(1)

Approach 2: Recursive Solution

The recursive approach reverses the list by processing nodes from the end back to the beginning.

C# Recursive Solution

public class Solution 
{
    public ListNode ReverseList(ListNode head) 
    {
        return ReverseListRecursive(head, null);
    }
    
    private ListNode ReverseListRecursive(ListNode current, ListNode prev) 
    {
        if (current == null) 
            return prev;
        
        ListNode next = current.next;
        current.next = prev;
        
        return ReverseListRecursive(next, current);
    }
}

Python Recursive Solution

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        return self._reverse_recursive(head, None)
    
    def _reverse_recursive(self, current: Optional[ListNode], 
                          prev: Optional[ListNode]) -> Optional[ListNode]:
        if not current:
            return prev
        
        next_node = current.next
        current.next = prev
        
        return self._reverse_recursive(next_node, current)

Time Complexity: O(n)
Space Complexity: O(n) due to recursion call stack

Visual Walkthrough

Original: 1 -> 2 -> 3 -> 4 -> 5 -> null

Step 1:   null <- 1    2 -> 3 -> 4 -> 5 -> null
Step 2:   null <- 1 <- 2    3 -> 4 -> 5 -> null
Step 3:   null <- 1 <- 2 <- 3    4 -> 5 -> null
Step 4:   null <- 1 <- 2 <- 3 <- 4    5 -> null
Step 5:   null <- 1 <- 2 <- 3 <- 4 <- 5

Result:   5 -> 4 -> 3 -> 2 -> 1 -> null

Key Takeaways

Stack Patterns

1. Matching/Validation: Use stack to track opening elements (parentheses, tags)
2. Reverse Order Processing: Stack naturally reverses the order of elements
3. State Management: Track previous states for backtracking

Linked List Reversal Patterns

1. Three-Pointer Technique: prev, current, next for iterative reversal
2. Recursive Approach: Process from tail to head
3. In-place Modification: Reverse without extra space (iterative method)

Best Practices

• Check for empty stack before Pop() or Peek()
• Use Count property in C# (faster than other methods)
• Handle edge cases: empty input, single element
• Choose iterative over recursive for better space complexity
• Name variables descriptively (prev, current, next)

When to Use Stacks

Perfect for:

• Problems involving nested structures
• Order reversal requirements
• Backtracking algorithms
• Expression parsing and evaluation

Not ideal for:

• Random access requirements
• Searching through elements
• When you need to access middle elements

Practice Problems

Ready to level up? Try these related problems:

1. Min Stack – Design a stack with O(1) min operation
2. Evaluate Reverse Polish Notation – Calculator with stack
3. Daily Temperatures – Monotonic stack pattern
4. Valid Parentheses Extensions – Handle more complex cases
5. Implement Queue using Stacks – Data structure design

Conclusion

Stacks are deceptively simple yet incredibly powerful. Understanding when and how to use stacks effectively is crucial for solving a wide range of algorithmic problems. The LIFO principle makes stacks perfect for tracking state, managing nested structures, and reversing order.

What’s Next? In our next article, we’ll explore queues and deques, completing our journey through linear data structures.

Happy coding! 🚀

Have questions or suggestions? Drop a comment below!