When it comes to working with abstract data structures there are two components that need to be understood: Queues and Stacks. In this guide walks through understanding the Stack data structure.

Real World Example of Stacks

As we spoke about previously in regards to the Queue data structure, it functions like a line at an amusement park. The first elements that go into the structure are also the first elements that come out. When it comes to understanding the stack data structure there is another helpful real world analogy.

Stacks work in the exact opposite way that queues do. In algorithm terminology stacks follow the Last In First Out (LIFO) data flow. This means that the last item added to the data structure will be the first element removed.

You can think about how this works by considering a tower of blocks. Each time you add a new block to the pile it goes on top. If you want to remove a block you can only remove the block on the top of the pile since that's the only one you have access to.

Understanding the Stack Data Structure

For our code example we're going to use the Scala programming language. However when it comes to working with abstract data types such as Stacks and Queues the language itself is not important.

Creating the Stack

In Scala we can create a new Stack structure with the following command:

scala> val stack = new scala.collection.mutable.Stack[String]

Running this command in the Scala Repl environment will create a stack with the String data structure and will return the following:

stack: scala.collection.mutable.Stack[String] = Stack()

Adding to the Stack

Like our example we're going to add blocks to our stack. We can add a single block by using the push method:

scala> stack.push("Red Block")

If you run this code you'll receive the following output:

res0: stack.type = Stack(Red Block)

We can add some more blocks with the commands:

scala> stack.push("Blue Block")
scala> stack.push("Green Block")

This will add two more blocks to the stack.

Viewing the Stack

We can see all of the items in the block stack by running the command:

scala> stack

This will output the entire structure and its contents:

scala.collection.mutable.Stack[String] = Stack(Green Block, Blue Block, Red Block)

Removing Items Off the Stack

Now let's start removing items from the stack. We're going to leverage the pop method in order to accomplish this. Which means we're going to pop items from the stack. If I run the command:

scala> stack.pop

It will output the following:

res4: String = Green Block

This is good since the Green Block was the last block we added to the stack.

I you run the stack pop command it will remove the Blue Block. And lastly if you run stack one more time it will show that the structure only has the Red Block, which was the first one added.

Summary

This structure is quite simple, which is one of the keys to an abstract data structure. Stacks need to be straightforward and only perform a few key tasks such as adding and removing elements.

The behavior of stacks and queues may seem incredibly basic. However you'll discover that when you're working with algorithms that utilize data structures, all of your programs will follow either the pattern of a stack or a queue. Which is why it's critical to understand how they perform.