How to Use the Stack Data Structure to Solve Coding Challenges

As a full-stack developer, you will undoubtedly encounter the stack data structure on a regular basis, whether you realize it or not. Many common coding constructs utilize a stack behind the scenes, and questions involving stacks are extremely prevalent in technical job interviews at major tech companies like Google, Amazon, and Microsoft.

In this in-depth guide, we‘ll cover everything you need to know about stacks to crush your coding interviews and optimize your real-world applications. Let‘s start with the fundamentals and then dive into hands-on practice with the most common categories of stack-based interview questions. By the end, you‘ll be a stack master!

What is a Stack?

A stack is an abstract data type that allows elements to be added and removed according to the Last-In-First-Out (LIFO) principle. In other words, the last item added (pushed) to the stack will be the first one removed (popped).

Imagine a literal stack of cafeteria trays. You can only add a new tray to the top of the stack, and you can only remove the top tray at any given time. This analogy perfectly illustrates the two primary operations of a stack:

1. Push – adds a new element to the top of the stack
2. Pop – removes the top element from the stack

Some additional methods a stack may have include:

3. Peek – returns the top element without removing it
4. isEmpty – returns true if the stack is empty, false otherwise
5. Size – returns the number of elements currently in the stack

Most programming languages don‘t have a built-in stack type, but it‘s quite simple to implement one using an array or linked list. Here‘s a bare-bones example of a stack class in Python:

class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)

Why Use a Stack?

Stacks provide an intuitive and efficient way to solve certain types of problems. In particular, a stack is an ideal data structure to use when you need to process nested or recursive structures, reverse the order of elements, or keep track of state as you traverse some data.

The LIFO ordering of a stack lends itself naturally to backtracking scenarios. For example, if you need to find all valid combinations of parentheses, you can use a stack to keep track of opening brackets as you generate combinations, popping them off when you add a matching closing bracket.

Stacks also make it easy to evaluate mathematical expressions in postfix notation. As you iterate through the expression, you simply push operands onto the stack, and when you hit an operator, you pop the required number of operands and push the result back onto the stack.

We‘ll look at more specific examples shortly, but in general, here are some signs that a stack might be a good fit:

• You need to reverse the order of elements
• You need access to the most recently added element
• You need to backtrack or undo operations
• You‘re dealing with nested structures like parentheses or tags
• You‘re evaluating an expression with a predictable order of operations

Practice Makes Perfect

Now that we‘ve covered the basics of stacks, it‘s time to get our hands dirty and apply this knowledge to real coding challenges! We‘ll solve incrementally harder problems in each of the following categories to build our stack problem-solving skills:

1. Parentheses/Brackets/Braces
2. Infix, Prefix, and Postfix Expressions
3. Backtracking and Depth-First Search
4. Monotonic Stack Problems

For each example, I‘ll provide the problem statement, talk through the intuition of how to approach it with a stack, and walk through the code line by line. Let‘s get started!

Valid Parentheses

Problem statement:
Given a string s containing just 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.

Example 1:
Input: s = "()"
Output: true

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

Example 3:
Input: s = "(]"
Output: false

Intuition:
The crux of this problem is making sure that every opening bracket is eventually closed by a matching closing bracket in the correct order. A stack is perfect for this because it will allow us to keep track of the most recently seen unclosed bracket.

Whenever we see an opening bracket, we‘ll push it onto the stack. Whenever we see a closing bracket, we‘ll check if it matches the bracket on the top of the stack (if there is one). If they match, we‘ll pop the opening bracket, since it has now been closed. If they don‘t match or the stack is empty, we know the string is invalid.

If we make it to the end of the string and the stack is empty, that means every opening bracket was properly closed, so the string is valid. Let‘s see this logic in code:

Solution:

def isValid(self, s: str) -> bool:
    stack = []
    brackets = {")":"(", "]":"[", "}":"{"}

    for char in s:
        if char in brackets.values():
            stack.append(char)
        elif char in brackets.keys():
            if stack == [] or stack.pop() != brackets[char]:
                return False

    return stack == []

We use a dictionary brackets to map each closing bracket to its corresponding opening bracket. This will make it easy to check for a match.

We iterate through each character in the string. If it‘s an opening bracket, we push it onto the stack. If it‘s a closing bracket, there are two possible cases where the string is invalid:

1. The stack is empty (meaning there‘s no unclosed opening bracket to match the current closing bracket)
2. The bracket on top of the stack is not the corresponding opening bracket for the current closing bracket

If either of those cases are true, we return false. Outside of the loop, we return the result of checking if the stack is empty. If we made it this far and the stack isn‘t empty, there were some unclosed brackets, so the string is invalid.

This solution has a time complexity of O(n) since we iterate through the string once, and a space complexity of O(n) in the worst case where every character is an opening bracket that gets added to the stack.

Basic Calculator

Problem statement:
Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:
Input: s = "1 + 1"
Output: 2

Example 2:
Input: s = " 2-1 + 2 "
Output: 3

Example 3:
Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

Intuition:
This problem might seem daunting at first, but with the help of a stack, we can solve it methodically. The key insight is realizing that whenever we see a closing parenthesis, we can evaluate the expression inside the matching pair of parentheses.

As we iterate through the string, we‘ll keep a stack of numbers. Whenever we see a digit, we‘ll build it up into a multi-digit number if necessary. Whenever we see an operator, we‘ll save it for the next number. And whenever we see an opening parenthesis, we‘ll push the current number and operator onto the stack.

When we see a closing parenthesis, that means we‘ve reached the end of a sub-expression. We can evaluate it by popping numbers off the stack until we hit an opening parenthesis (which will also be popped). The result of the sub-expression becomes the new current number.

Solution:

def calculate(self, s: str) -> int:
    stack = []
    num = 0
    sign = 1
    result = 0

    for char in s:
        if char.isdigit():
            num = num*10 + int(char)
        elif char == ‘+‘:
            result += sign * num
            num = 0
            sign = 1
        elif char == ‘-‘:
            result += sign * num
            num = 0
            sign = -1
        elif char == ‘(‘:
            stack.append(result)
            stack.append(sign)
            sign = 1
            result = 0
        elif char == ‘)‘:
            result += sign * num
            result *= stack.pop()
            result += stack.pop()
            num = 0

    return result + sign * num

We keep track of the current number num, the operator sign to be applied to the next number, and the overall result.

When we see a digit, we build it up into num. When we see + or -, we apply the current num to result using the saved sign, reset num to 0, and update sign for the next number.

When we see (, we push the current result and sign onto the stack. This effectively "saves" the state outside the parentheses to be restored later. We set sign to 1 and result to 0 for the sub-expression inside the parentheses.

When we see ), we apply the current num to result like normal. Then we pop the saved sign from the stack and multiply result by it. Finally, we pop the saved result from before the parentheses and add it to the current result.

After iterating through the string, there may be one last number that hasn‘t been added to result. We return result + sign * num to account for this.

Like the previous problem, this solution is O(n) time and O(n) space. The space is needed for the stack, which can grow up to roughly half the size of the input string in the worst case (e.g. "(((((1)))))" would have a stack of size 5 at its peak).

Wrapping Up

I hope this deep dive into using stacks to solve coding challenges has been illuminating! We‘ve covered the fundamentals of what a stack is and when it‘s applicable, and worked through several examples of classic stack problems.

The key takeaways are:

• Stacks are useful for processing nested structures, reversing elements, and keeping track of state during a traversal.
• Valid parentheses and evaluating mathematical expressions are two of the most common types of stack problems.
• Pushing elements onto a stack is like "saving" them for later, while popping them is like "restoring" a previous state.
• Most stack solutions require iterating through the input and pushing/popping elements in a single pass, leading to O(n) time and space complexity.

Of course, there are many other applications of stacks beyond coding challenges. Compilers and text editors use stacks to parse nested code blocks and provide undo/redo functionality. Graph algorithms like depth-first search use a stack to remember which nodes to visit next. And the call stack in a multi-threaded program keeps track of which functions have been called but not yet returned.

Anytime you need the "last in, first out" ordering that stacks provide, you have a potential use case on your hands. Add the stack to your data structure toolbelt and wield it wisely in your future coding endeavors!