RubyGuides
Share this post!

Practical Computer Science in Ruby: Using Stacks 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…

In this post I want to show you one practical computer science concept that you can start putting into practice right now!

The Stack

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.

Example 1 (flatten)

One classic example is to flatten an array. In other words, convert a multi-dimensional array into a one-dimensional array.

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:

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 mantained when doing things this way.

Another version using until & empty?:

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).

Example 2 (balanced parenthesis)

Here is another example, where there is no equivalent Ruby method to do everything for you. And it’s also another classic problem in computer science: matching balanced parenthesis.

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

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):

Example (Invalid Input):

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:

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:

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). So that’s what we need to optimize & we can do that using a stack.

Example:

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!

12 comments
Bennie says 7 months ago

Very nice! Thanks!

    Jesus Castello says 7 months ago

    Thanks for reading Ben! 🙂

Snehit Gajjar says 7 months ago

Informative. I think there is a typo if you can fix.

in Array#flatten example should be

    Jesus Castello says 7 months ago

    Thanks for your comment Snehit. I think it should be arr, because I’m using arr as the stack & what I’m doing is pushing the array items on top of the stack. Sorry if I wasn’t clear enough in the post!

      Snehit says 6 months ago

      If that is the case when you pop out 1,2,3, [4,5] you have 6 at the top of the stack. Then [4,5] is being an Array, you push those elements back on the stack then arr should be like [5, 4, 6]. And flat array should be [ 1, 2, 3, 5, 4, 6]. Let me know if I am missing anything.

        Jesus Castello says 6 months ago

        In that example arr would become

        & the end result would be

        If that value of arr looks weird is because each is not actually removing any items, it just keeps track of the current index & keeps going as long as the index is less than the array length (in other words: until it reaches the end of the array).

        I added another example to the post using until that results in [6, 5, 4, 3, 2, 1] (same order but in reverse, that’s normal for a stack).

        Hope that helps make things more clear 🙂

        Snehit says 6 months ago

        Thanks Jesus,

        This makes sense.

Ravi says 7 months ago

Thank you, I’ve enjoyed reading. Please keep posting more articles like this.

    Jesus Castello says 7 months ago

    I will while people keep sharing & reading my articles 🙂

hanumakanth says 7 months ago

Nice post

Anwar says 6 months ago

Nice post. Which syntax highlighting css have you used? Those are really nice!

    Jesus Castello says 6 months ago

    I’m using the “Crayon Syntax Highlighter” wordpress plugin with the “Obsidian” theme 🙂

Comments are closed