Data structures are a special type of object used to store and manipulate data. One such data structure is known as a stack. A stack is used to store data in a last in first out format, meaning that the last item added onto the stack is the first item that will be removed from it. Stacks have a number of different applications in computing, the most common being memory management and expression evaluation.
A stack implementation typically contains three methods, which as push, pop, and peek. Push will allow the user to put a single item onto the stack. Peek allows the user to see what value is on top of the stack, and pop allows the user to remove the top value from the stack. When we implement a stack, we keep track of only the top element. When we push a value onto the stack, the value being pushed becomes the new top. When we pop a value off the stack, we value underneath the top becomes the new top. As an example, suppose you have a stack and push the values 2 and 3 onto it. At this point, 3 would be the top value, since it was inserted last.
If we were to peek the value of the stack in its current state, it would give us the value 3, since that is the current top of the stack. If we were to pop a value of the stack, the current top value would be removed. So in this case, 3 would be removed, and 2 would become the new top.
The actual stack object has two components to it. First, we have a Node object, which holds a value, as well as a link to the next value in the stack. The second object is the actual stack itself, which keeps track of the top element, and allows the user to activate push, pop, and peek as required. To start, we will take a look at how to implement a node that holds a single integer value, and a link to the next node in the stack.
The Node object will have two properties, value, which will keep track of the value of the current node, and next, which will keep track of the node that comes after it. For these methods, we will implement getters and setters to be able to work with the values as required.
When we look at our stack example, we can see how each component maps to the Node object. If the top value is 3, and the value after it is 2, then we have a top Node with a value of 3 and a next value that is the Node that contains the value 2. The value at the bottom of the stack doesn’t point to anything, so when it is removed, the top of the stack is null, which is how we know that it is empty. When we implement a stack using a Node, we only have to keep track of a single property, which is the top Node. This Node will always be tracking the next Node in the sequence, meaning that as long as we know the top Node, we can get to any other Node in the stack, using the pop method.
As you can see, we set up the stack class with a single property, top, which is a Node as we defined earlier. From here, I have implemented the three methods to show how we could define these using the Node object. There are a few important ideas to take note of here. First, the push method takes in an integer value, and converts it into a Node object. We don’t want the user to have to create a Node object for each insert, so we handle this for them. Once we have done this, we either set the value to top if the stack is empty, or set the next value of the Node to the top and then set the inserted Node to the top.
Peek simply returns the value of what is on top of the stack. In contrast to this, pop will remove the value from the stack and then return it. To do this, we first get the value of the top and store it. From here, we set the top to be the next node that follows it and returns the value that was removed.
To actually use our stack, we just need to create an instance of the stack class and call the methods we want to use.
As a final note, I’ll show a visual representation of what this example is doing.
You can see from this diagram how the push, peek, and pop methods modify the stack structure. It’s important to remember that peek won’t modify the stack at all, but pop and push will. Stacks appear all over Computer Science, and you are sure to encounter them as you continue learning more complex topics. Implementing a stack will give you a good understanding of the structure so that when you encounter it being used, you will have a strong foundation in how it is implemented.