Data Structures: The Stack

8 min readAug 14, 2021

Continuing my series on useful data structures and their implementations, this week I’ll be exploring Stacks. You’ll find these all over the place under the hood in nearly all of the systems that we interact with on a daily basis.

Why use a Stack?

Stacks have several real-world applications, ranging from simple tasks like reversing a string, to more complex ones like backtracking algorithms. The concept is relatively simple, but the usefulness cannot be overstated. Let’s take a look at how a stack works.

Stacks implement a “First in, last out” structure, meaning as elements are stored, you only have access to the most recently added item to the stack.

Here we have an empty stack, and 4 items we would like to store (these items could be anything, I just chose fruits). We would have an add() function that allows us to add each of these fruits to the stack, in order.

stack.add(Banana)
stack.add(Durian)
stack.add(Blueberry)
stack.add(Cheery)

Our items would be added to the stack as such:

Notice, we also keep track of a pointer, that always points to the most recently added item in our stack. This is the key to the function of the stack. We are only able to retrieve the most current item, and none of the items lower on the stack, until the more recent items have been “popped” off the stack. At first this seems limiting, but this functionality is what makes this data structure so efficient. I came across a fine article that goes over the implementation of all the needed functions to implement a stack in JavaScript:

Implementing a Stack in JavaScript

They’re like arrays with more structure and rules

betterprogramming.pub

Using this simple implementation, the more advanced uses of a stack are now unlocked. I’d like to look at a common data structure interview question, and whiteboard out the concept of solving it using a stack to create a backtracking algorithm.

Rat In a Maze

This is a very famous question, and has a number of solutions. Let’s go over the prompt and setup.

A maze is given via a binary matrix of blocks with N*N spaces. ex:

const maze = [
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]

In this maze, the blocks marked “1” are available, and the “0” blocks are blocked off.

2. The source or start position is the upper right corner of the matrix: maze[0][0] and the destination or end point is the bottom right corner: maze[N-1][N-1].

3. A rat starts at the source and must reach the destination. It can only move right or down. We can simplify this later by considering our options to be “Move x” or “Move y”.

Conceptual Solution

Let’s think about all the information we need to solve this problem. Ideally, we’d like a list of moves returned that gets us from the source to the destination, or return false if none exists. Let’s consider (X,Y) coordinates starting at the top leftmost block and use a recursive function to get our rat to the destination. First, whenever the rat moves, we need to check if the rat has reached the destination. If so, then we have our path. So we will need to keep track of four pieces of information as we recurse:

The maze itself
The rats X position
The rats Y position
A solution matrix to keep track of our visited blocks

Our recursive function should do a few things:

Mark the solution matrix matching the rats position as visited, and store the move in our stack.
Check if the rats position is the destination, and return the moves in the stack if so.
Check if the block immediately to the right of the rats position is available and not visited, and if so, move there.
Check if the block immediately down from the rats position is available and not visited, and if so move there.
If the rat cannot move right or down, and is not at the destination, then move back one step (from our stack)

Let’s put our whiteboard into action. We start with the rat in the source position: maze[0][0]

Move #1

// using this recursive function with these arguments:function solveMaze(maze, xPos, yPos, solMatrix) {
   ...
}solveMaze(maze, 0, 0, sol)// maze
[
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]// sol matrix
[
    [1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
]

Mark the sol matrix
Not destination
Move X not available
Move Y

Move #2

solveMaze(maze, 0, 1, sol)// maze
[
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]// sol matrix
[
    [1, 0, 0, 0, 0],
    [1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
]

Mark the sol matrix
Not destination
Move X

Move #3

solveMaze(maze, 1, 1, sol)// maze
[
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]// sol matrix
[
    [1, 0, 0, 0, 0],
    [1, 1, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
]

Move #4

solveMaze(maze, 2, 1, sol)// maze
[
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]// sol matrix
[
    [1, 0, 0, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
]

Move #5

solveMaze(maze, 2, 2, sol)// maze
[
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]// sol matrix
[
    [1, 0, 0, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
]

Move #6

solveMaze(maze, 3, 2, sol)// maze
[
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]// sol matrix
[
    [1, 0, 0, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
]

Move #7

solveMaze(maze, 4, 2, sol)// maze
[
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]// sol matrix
[
    [1, 0, 0, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
]

Finally we’ve reached a point where we need to backtrack. Because we’ve been using a stack to keep track of our moves, we have these 7 moves stored.

stack = [
    solveMaze(maze, 0, 0, sol),
    solveMaze(maze, 0, 1, sol),    
    solveMaze(maze, 1, 1, sol),
    solveMaze(maze, 2, 1, sol),
    solveMaze(maze, 2, 2, sol),
    solveMaze(maze, 3, 2, sol),
    solveMaze(maze, 4, 2, sol)
]

At this stage, we can “pop” the last move off of the stack [the one with the position (4,2)], and try again:

Move #8

solveMaze(maze, 3, 2, sol)// maze
[
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]// sol matrix
[
    [1, 0, 0, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
]

Mark the sol matrix (already done)
Not destination
Move X not available (because it has already been visited)
Move Y not available
Backtrack another step

Move #9

solveMaze(maze, 2, 2, sol)// maze
[
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]// sol matrix
[
    [1, 0, 0, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
]

Mark the sol matrix (already done)
Not destination
Move X not available (because it has already been visited)
Move Y

Now we’ve backtracked far enough to find the fork that took our rat the wrong direction, and our stack has “popped” off the incorrect moves, which are no longer taking up any space in memory.

stack = [
    solveMaze(maze, 0, 0, sol),
    solveMaze(maze, 0, 1, sol),    
    solveMaze(maze, 1, 1, sol),
    solveMaze(maze, 2, 1, sol),
    solveMaze(maze, 2, 2, sol)
]

Let’s continue from here and see what happens:

Move #10

solveMaze(maze, 2, 3, sol)// maze
[
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]// sol matrix
[
    [1, 0, 0, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0]
]

Move #11

solveMaze(maze, 2, 4, sol)// maze
[
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]// sol matrix
[
    [1, 0, 0, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [0, 0, 1, 0, 0],
    [0, 0, 1, 0, 0]
]

Move #12

solveMaze(maze, 3, 4, sol)// maze
[
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]// sol matrix
[
    [1, 0, 0, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [0, 0, 1, 0, 0],
    [0, 0, 1, 1, 0]
]

Move #13

solveMaze(maze, 4, 4, sol)// maze
[
    [1, 0, 1, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1]
]// sol matrix
[
    [1, 0, 0, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 0, 1, 1, 1],
    [0, 0, 1, 0, 0],
    [0, 0, 1, 1, 1]
]

Mark the sol matrix
Destination reached! Return stack.

stack = [
    solveMaze(maze[4][4], 0, 0, sol[4][4]),
    solveMaze(maze[4][4], 0, 1, sol[4][4]),    
    solveMaze(maze[4][4], 1, 1, sol[4][4]),
    solveMaze(maze[4][4], 2, 1, sol[4][4]),
    solveMaze(maze[4][4], 2, 2, sol[4][4]),
    solveMaze(maze[4][4], 2, 3, sol[4][4]),
    solveMaze(maze[4][4], 2, 4, sol[4][4]),
    solveMaze(maze[4][4], 3, 4, sol[4][4]),
    solveMaze(maze[4][4], 4, 4, sol[4][4])
]

And from the stack we can derive the rats path:

(0,0) -> (0,1) -> (1,1) -> (2,1) -> (2,2) -> (2,3) -> (2,4) -> (3,4) -> (4,4)

Conclusion

Keeping track of an array of data in order is sort of like dropping bread crumbs to remember a path you took. It can also be useful for organizing tasks that need to be completed and lays the groundwork for many modern programming languages.

If you’d like to see the implementation of the solution to this question, check out this link, which includes several languages:

Rat in a Maze | Backtracking-2 - GeeksforGeeks

We have discussed Backtracking and Knight's tour problem in Set 1. Let us discuss Rat in a Maze as another example…

www.geeksforgeeks.org

Thank you for following along and happy coding!