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