StacksLesson 3

Stack Applications

Bracket matching, undo systems, expression evaluation, and the function call stack — real problems solved with stacks.

What Is It?

A stack isn't just something you learn about — it's something you use. The LIFO property makes it the perfect tool for problems involving matching, nesting, reversal, or backtracking.

In this lesson we look at three classic applications:

  1. Bracket matching — checking that (, {, and [ are properly opened and closed.
  2. Reversing a string — using the stack's natural reversal property.
  3. The function call stack — understanding how your program actually runs.

Analogy

Think of a stack as a helper who remembers things in reverse order:

  • Bracket matching: You hand your helper each opening bracket as you see it. When you hit a closing bracket, you ask: "What was the last opening bracket you got?" If it matches, great — throw it away. If not, something's wrong.
  • String reversal: You say a word letter by letter. Your helper repeats it back starting from the last letter — spelling it backward.
  • Call stack: Your helper tracks what you were doing before each interruption. When you finish a side task, they remind you: "You were right in the middle of THIS" — always the most recent unfinished thing first.

How It Works

Application 1: Bracket Matching

Given a string with brackets — (, ), {, }, [, ] — check if every opening bracket has a matching closing bracket in the right order.

Valid: (), ({[]}), [()]{}

Invalid: ([)], (((, }{

#### The Algorithm

  1. Create an empty stack.
  2. Read the string left to right, one character at a time.
  3. If you see an opening bracket ((, {, [), push it.
  4. If you see a closing bracket (), }, ]):
  • If the stack is empty, return invalid — there's nothing to match.
  • Pop the top of the stack.
  • If it doesn't match the closing bracket, return invalid.
  1. After reading the whole string, if the stack is still not empty, return invalid — some openers were never closed.
  2. Otherwise, return valid.

#### Full Pseudocode

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function isValidBrackets(str):
    stack = new Stack()
​
    for each char in str:
        if char is '(' or '{' or '[':
            stack.push(char)
        else if char is ')' or '}' or ']':
            if stack.isEmpty():
                return false    // closing bracket with no opener
            top = stack.pop()
            if not isMatchingPair(top, char):
                return false    // wrong type of bracket
​
    return stack.isEmpty()      // true only if all openers were closed
​
function isMatchingPair(open, close):
    return (open is '(' and close is ')')
        or (open is '{' and close is '}')
        or (open is '[' and close is ']')

#### Trace 1: Valid String ({[]})

Bracket Matching: ({[]})— Stack grows with openers, shrinks with matching closers
1 / 6
( — push
(
[0]

#### Trace 2: Invalid String ([)]

pseudocode
1
2
3
4
5
6
7
8
Char    Action              Stack (top on right)
----    ------              --------------------
(       push '('            [ ( ]
[       push '['            [ (, [ ]
)       pop '[', does NOT   MISMATCH!
        match ')'
​
Return false -> INVALID

The ) expects ( on top but finds [. The brackets are crossed, not nested.

#### Trace 3: Invalid String (()

pseudocode
1
2
3
4
5
6
7
Char    Action              Stack (top on right)
----    ------              --------------------
(       push '('            [ ( ]
(       push '('            [ (, ( ]
)       pop '(', matches    [ ( ]
​
End: stack is NOT empty -> INVALID (one '(' was never closed)

Application 2: Reverse a String Using a Stack

Because a stack returns things in reverse order, reversing a string is almost trivial.

#### Algorithm

  1. Push every character of the string onto the stack.
  2. Pop all characters — they come out in reverse order.
  3. Build the reversed string from the popped characters.

#### Pseudocode

pseudocode
1
2
3
4
5
6
7
8
9
10
11
function reverseString(str):
    stack = new Stack()
​
    for each char in str:
        stack.push(char)
​
    result = ""
    while not stack.isEmpty():
        result = result + stack.pop()
​
    return result

#### Trace on "hello"

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Push phase:
  push 'h'  ->  [h]
  push 'e'  ->  [h, e]
  push 'l'  ->  [h, e, l]
  push 'l'  ->  [h, e, l, l]
  push 'o'  ->  [h, e, l, l, o]
​
Pop phase:
  pop -> 'o'   result = "o"
  pop -> 'l'   result = "ol"
  pop -> 'l'   result = "oll"
  pop -> 'e'   result = "olle"
  pop -> 'h'   result = "olleh"
​
Return "olleh"

Time: O(n). Space: O(n) for the stack.

Application 3: The Function Call Stack

Every program has a call stack managed automatically by your language and operating system. You've been using it every time you write a function — you just haven't seen it.

#### How It Works

When your code calls a function:

  1. That function gets pushed onto the call stack.
  2. The stack holds the function's local variables and where to return to when it finishes.

When the function returns:

  1. It gets popped off the stack.
  2. Execution resumes where it left off in the function that called it.

#### Example: Recursive Factorial

pseudocode
1
2
3
4
5
6
function factorial(n):
    if n equals 0:
        return 1
    return n * factorial(n - 1)
​
// Call: factorial(4)

The call stack grows as each recursive call is made:

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Call factorial(4)
   +---------------------+
   | factorial(4), n=4   | <-- running
   +---------------------+
​
Call factorial(3)
   +---------------------+
   | factorial(3), n=3   | <-- running
   +---------------------+
   | factorial(4), n=4   | <-- waiting
   +---------------------+
​
... and so on until ...
​
   +---------------------+
   | factorial(0), n=0   | <-- base case! returns 1
   +---------------------+
   | factorial(1), n=1   |
   +---------------------+
   | factorial(2), n=2   |
   +---------------------+
   | factorial(3), n=3   |
   +---------------------+
   | factorial(4), n=4   |
   +---------------------+

Then the stack unwinds — each function returns its value to the one below it:

factorial(0)
1
factorial(1)
1
factorial(2)
2
factorial(3)
6
factorial(4)
24

The last function called (factorial(0)) is the first to return. Pure LIFO.

#### Stack Overflow

If there's no base case, the recursion never stops pushing frames onto the call stack:

pseudocode
1
2
3
4
function infinite(n):
    return infinite(n + 1)   // never stops!
​
// Call stack fills up -> STACK OVERFLOW error

That's literally where the term "stack overflow" comes from.

Why All Three Use Stacks

All three applications share one pattern: the most recent thing must be handled first.

  • Bracket matching: the most recently opened bracket must be closed first.
  • String reversal: the last character pushed comes out first.
  • Call stack: the most recently called function returns first.

Whenever you see "most recent first" in a problem, reach for a stack.

Examples

Example: Bracket Matching on a Real Expression

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input: "{[a + b] * (c - d)}"
​
Ignore letters and operators — only look at brackets:
​
Char    Action              Stack
----    ------              -----
{       push                [ { ]
[       push                [ {, [ ]
]       pop [, matches ]    [ { ]
(       push                [ {, ( ]
)       pop (, matches )    [ { ]
}       pop {, matches }    [ ]
​
Stack empty -> VALID

Example: Replacing Recursion with a Stack

Any recursive function can be rewritten using an explicit stack — because recursion uses the call stack under the hood anyway.

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Recursive version:
function printReverse(arr, index):
    if index equals length(arr):
        return
    printReverse(arr, index + 1)
    print(arr[index])
​
// Same thing, but with an explicit stack:
function printReverse(arr):
    stack = new Stack()
    for each element in arr:
        stack.push(element)
    while not stack.isEmpty():
        print(stack.pop())

Common Mistakes

1. Forgetting to check if the stack is empty at the end of bracket matching. The string ((( has valid-looking opening brackets, but since they're never closed, the result must be invalid. Always check stack.isEmpty() at the very end.

2. Not handling a closing bracket when the stack is empty. The string ) has no opener. If you try to pop from an empty stack, your program crashes. Check isEmpty before popping.

3. Thinking the call stack is unlimited. It's not. Most systems give it between 1 MB and 8 MB. Very deep recursion (tens of thousands of calls) can overflow it. If you hit this, convert to an iterative approach with an explicit stack.

4. Getting the order wrong in string reversal. You push left-to-right and pop to build the result. If you accidentally prepend instead of append the popped characters, you end up back with the original string.

5. Not recognizing stack problems. Nesting (HTML tags, file paths), reversal, and backtracking (maze solving, undo) are all stack problems in disguise.

Best Practices

Use bracket matching as your go-to stack example. It's clean, easy to explain, and shows the core idea perfectly. Great for interviews.

Trace by hand before coding. For bracket matching, write out the stack state after every character. For recursion, draw the call frames. This builds intuition faster than just reading code.

Know when NOT to use a stack. If you need to process things in the order they arrived (first come, first served), use a queue — not a stack. Stacks reverse order; queues preserve it.

Practice converting recursion to iteration. Replace the call stack with an explicit stack. It's a great exercise and a common interview question.

Implementing a StackHow Queues Work