You can use a stack when you need to remember something and only ever need the last thing.
If you need to access any item in a collection at any time, then a stack is not going to work. I didn’t explain stacks before because in a way, it’s like a restricted vector. Make sure to listen to the earlier episodes 39 through 46 for more information about other collections. You’ll want to use a stack whenever you need to stop what you’re doing, remember everything so you can come back to your paused task later, and then go do something else.
Make sure to listen to the full episode or read the full transcript below for examples and more details. And if you like these episodes, consider supporting the podcast by becoming a patron. The link is at the top and bottom of this page. For just $1 per month, you can get an additional podcast episode available only to patrons. The first patron episode begins Nov-2017.
Transcript
If you need to access any item in a collection at any time, then a stack is not going to work. I didn’t explain stacks before because in a way, it’s like a restricted vector. Make sure to listen to the earlier episodes 39 through 46 for more information about other collections.
You’ll want to use a stack whenever you need to stop what you’re doing, remember everything so you can come back to your paused task later, and then go do something else.
In a way, a stack is sort of unfair. Imagine if a restaurant used a stack to keep track of arriving guests to determine who gets a table next. You reach a restaurant called The Full Stack and find it almost empty. But the receptionist carefully takes your name and let’s you know that you’re first in line. But before you get a table, some more guests arrive. And then some more. You’re really glad that you beat the crowd. But then why haven’t you been seated yet?
Maybe they forgot about you. It happens. So you go back to the receptionist who tells you not to worry, you’re still first in line. Then you notice something. A person wearing a green jacket arrives, signs in, and almost immediately gets called for a table. What’s going on?
You go back to the receptionist who explains that the restaurant is called The Full Stack because of their innovative new registration system that uses a stack. With this new system, the last guest to arrive is the next to get a table.
Obviously, The Full Stack restaurant won’t be in business very long. But that doesn’t mean that a stack is useless. There are times when it’s exactly what you need.
A stack gives you two basic operations, push and pop. When you call push, you’re adding something to the top of the stack. Think of it like a deck of cards. Pushing will place a new card on top of the stack. The other operation is pop and this removes whatever is currently on top of the stack.
Now a deck of cards will let you pick up several cards at once and remove a card from the middle. A stack won’t let you do this. Not because it can’t. After all, a stack will probably just be using a vector to store its items. That means that it has access to get to any item in the vector. All of this is private to the stack though. As far as you’re concerned, you can only work with the top of the stack.
When that’s all you need or want anyway, then why use a vector when you can use a stack with just the methods you need and nothing else? Episode 39 explains the array collection which is similar to a vector.
The reason I’m discussing stacks now is because you need to understand them in order to understand another type of tree. I was going to discuss abstract syntax trees and was about to refer you to the earlier episode about stacks when I realized there was no episode about stacks yet.
Because stacks never need to add or remove items from the beginning or middle, then they don’t have to worry about shifting items around. A stack can still run out of room and then a push will cause the stack to allocate more memory. This is not a list where memory gets allocated for each item. A stack still behaves like an array in this sense. All the items in a stack will be located together in memory. So when a stack runs out of memory, it needs to find a new and bigger place in memory and then it moves all the items to the new location. This keep everything together and allows the stack to grow when needed. Stacks don’t usually shrink once they’ve grown.
There might be more elaborate designs out there that maintain the stack in one or more blocks of memory. This can eliminate the need to copy items around but means extra overhead for the stack to keep track of all the blocks. Think of this like what we do when counting coins. We place the coins in stacks, right? But once the stacks get too high, we start another stack. Okay, maybe that wasn’t the best example because we stack coins like this because it helps us to count them better. Not because we only want to spend the top coin.
It doesn’t matter how complicated or simple a stack is inside. When you want to use a stack, you still have two basic operations, push and pop.
I’ve described push. What about pop? Well, pop, just removes whatever is on top and gives it back to you. If a stack is empty when you call pop, then this is an error and the stack will probably throw an exception.
Computers have a form of a stack built into them. Actually, it’s built into the microprocessor and it’s what allows you to call methods and return from them. This stack is a bit different because while it has push and pop abilities, it also exposes a pointer to the actual data. There’s no object-oriented encapsulation here so your code can get to items directly. I’ll explain more in a future episode.