How to Use Stacks in Ruby to Solve Problems

If you don’t have a CS (Computer Science) degree you might feel like you are missing out on something…

Or you may feel like CS is too abstract to be useful…

Or that Ruby already does all the hard work for you…

Either way…

It’s helpful to understand the basics of data structures like hashes, stacks & queues.

In this post:

You’ll discover how to use stacks in Ruby.

A practical computer science concept that you can start putting into practice right now!

Understanding Stacks in Ruby

What is a stack in Ruby?

A stack is a data structure which you can use as a “to-do” list. You keep taking elements from the stack & processing them until the stack is empty.

Here’s is a visual representation.

Push 5 into an empty stack:

5

Push 3 into the stack:

3
5

Push 9 into the stack:

9
3
5

Take one item from the stack:

3
5

The big thing to notice here is that new items are added to the top of the stack. In a “Last-In First-Out” (LIFO) fashion. Meaning that when you take (pop) an item from the stack, it will be the last item that was pushed into it.

Another way to visualize how this works is by thinking about a stack of plates. If you put one plate on top of another you can’t take out the bottom plate without taking out the top plate first.

That’s all you are doing with a stack, pushing things to the top or poping things out. There is no indexing.

Let’s see some code examples on how this can be used.

How to Flatten an Array Using a Stack

A classic example of stacks is to use them to flatten an array. In other words, convert a multi-dimensional array into a one-dimensional array.

Here’s an example:

arr = [1,2,3,[4,5],6]

arr.flatten

In Ruby we have the flatten method which does this for you. But what if you didn’t have this method? And how does this method work?

This is where the stack comes in!

Ruby implements the push & pop methods, so we can treat an array like a stack.

Note: Both push & << are the same method. I will be using << in my code examples.

The idea is to go over every element and check if it’s an array or something else. If it’s an array then we will push the elements inside this array back into the stack.

What happens is that we keep removing array layers (like an onion) until there are none left. This will leave us with a flattened array.

Here’s is the code:

arr  = [1,2,3,[4,5],6]
flat = []

arr.each do |thing|
  if thing.is_a? Array
    thing.each { |i| arr << i }
  else
    flat << thing
  end
end

p flat
# [1, 2, 3, 6, 4, 5]

You will notice there is no pop method call in this code.

This is because I'm letting each do the hard work of taking the items from the stack & feeding them to my algorithm. Also notice how the order of the elements is not maintained when doing things this way.

Another version using until & empty?:

until arr.empty?
  thing = arr.pop

  if thing.is_a? Array
    thing.each { |i| arr << i }
  else
    flat << thing
  end
end

p flat
# [6, 5, 4, 3, 2, 1]

Since we are using pop now, instead of letting each do its thing, we are getting the flattened array in the correct order... But in reverse.

This reveals an interesting property of stacks:

Whatever list of things you put in, it will come back in the same order but in reverse.

Tip: The Array#flatten method takes an argument, which lets you define how many layers of nesting you would like to remove (by default all of them).

Solving the Balanced Parenthesis Problem

Here is another example & there is no equivalent Ruby method to do this for you!

It's also another classic problem in computer science...

The name is:

Matching balanced parenthesis.

The idea is that you are given a string & you need to validate if the parenthesis are valid.

For example, let's say you are writing a math evaluation program. You want to make sure the input is valid before processing it.

Example (Valid Input):

input = "1 + (4 + 6) * 2"

Example (Invalid Input):

input = "1 + (4 + 6 * 2"

You can use a stack to keep track of any parenthesis you have found in the input & then when you find a new parenthesis you check the top of the stack to make sure it matches the closing parenthesis.

If there is no match that means that you have invalid input.

Example:

PARENS = {
  "(" => ")",
  "{" => "}",
  "[" => "]"
}

OPENING_PARENS = PARENS.keys
CLOSING_PARENS = PARENS.values

def valid_parentheses(string)
  stack  = []

  string.each_char do |ch|
    if OPENING_PARENS.include?(ch)
      stack << ch
    elsif CLOSING_PARENS.include?(ch)
      ch == PARENS[stack.last] ? stack.pop : (return false)
    end
  end

  stack.empty?
end

p valid_parentheses("(){}[]") # true
p valid_parentheses("[(])")   # false

Another thing you will notice is that I ended this valid_parentheses method with a stack.empty?. That's to make sure we don't end with unclosed parenthesis.

If all the parenthesis are correctly closed then the stack should be empty 🙂

Example 3 (directions)

One more example to make sure you understand how to apply this.

In this case we are given a set of directions & we are told that we need to optimize it to save our traveler some time.

Here is an example set:

["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]

You will notice that if you go north then south you will end up in the same place (assuming it's the same distance both directions). That's what we need to optimize & we can do that using a stack.

Example:

input      = ["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]
directions = []

opposites = {
  "NORTH" => "SOUTH",
  "SOUTH" => "NORTH",
  "EAST"  => "WEST",
  "WEST"  => "EAST"
}

input.each do |dir|
  opposites[dir] == directions.last ? directions.pop : directions << dir
end

p directions

Conclusion

I hope you learned something new & that you start looking for ways to use stacks to solve programming challenges.

Don't forget to share this post so more people can read this!