Stacks on Stacks on Stacks — An Introduction to the Data Structure
If you’re starting to study some basic data structures and algorithms like I am, this article might be helpful for you. Stacks and Queues are two very similar data structures that, while definitely are not used on a day to day basis, can be very helpful in many programming contexts and can model some pretty tough problems. Learning how they work and how to implement them can be very useful in tackling some of the hardest programming challenges. Today we’ll be looking at what stacks and queues are, and model an array-based implementation.
So what is a stack? Well, let’s illustrate it with an example. Think of a literal stack. It can be of anything. A stack of plates, a stack of cards, a stack of chocolates, a stack of CDs, a stack of movies. Let’s take an example with CDs.
Now, how do you create this stack of tunes? Well, you simply keep stacking the CDs on top of each other. But let’s say you’ve made your stack, and, oh no! You realized you want the Rick Astley CD from the middle because you want to listen to “Never Gonna Give You Up”. Groan. Now you have to take off all of the CDs, starting with the one you put on the top. The last one in is the first one out.
Just like our stack of CDs, the stack data structure is a LIFO (Last-In, First-Out) data structure. Whichever element you put in first is the first one that comes off. This is the primary difference between the stack and its close cousin, the queue, which we’ll talk about in the next article in this series.
So what are some of the basic things we want a stack to do? Well, we should be able to add things to it and take things off. In programming, this is denoted with the push and pop operations.
When we push something onto a stack, we should first make sure that the stack has enough space for another element. And when we pop an element from the stack, we should make sure that the stack isn’t empty. We don’t want our stack of CDs to fall over (oh no, stack overflow!). But we also don’t want to try to get a CD from a pile that doesn’t have anything in it, because that just wouldn’t make sense.
With these considerations in mind, let’s get started on our implementation of an array-based stack in Java.
There are 3 pieces of data we need before we start creating our stack functionality. First is a reference to the index of the top of the stack. The second is an array. Our stack is essentially a glorified array. The third is our size, so we can make sure we’re not adding things to full stacks.
Right below this is is a constructor for our Stack object. Essentially, this tells the computer what to do when you try to create a new stack somewhere else in your program.
Before we can get to the meat of the object, let’s make sure we take our earlier considerations into account. Earlier we talked about how complications can arise when a stack is empty or if it’s full. So let’s put in a couple of methods that tell us whether or not a stack is empty or full so we can add that to our control flow later on.
NOW for the fun stuff. Let’s implement the push functionality. Just to remind you, “push” adds an element to the top of the stack if it’s not full. So, before we add anything to the stack, let’s make sure it’s not full, and if it is, we need to throw an error. Otherwise, we can add to the stack and update the index of the top to reflect the CD we’ve just added to the top of the pile.
The same thing goes for pop. We have to make sure we’re not returning an element that doesn’t exist, so first, we check if the stack is empty, and if it is, we throw an error. If it’s not empty, we can go ahead and pluck an element off the top of the stack and reduce the index of the top by 1, because now, the number of elements in the stack is one less than it was before.
There we have it, the basic functionality of a stack. Now you have the basic idea down to implement some of the most common applications of a stack: reversing a word, undo/redo in text editors, or even just modeling a stack of your favorite CDs.
To view my full implementation of a stack, you can check out on GitHub.
Cheers!
Gauri
Do you like this article? Does anything not make sense? Do you have any suggestions or improvements to make my code or my articles better? Feel free to shoot me a message or comment on this post. Thank you!
