Stacks
If you’ve ever used a feature such as undo (CMD + Z) or executed code then you’ve utilized a fundamental tool in computer science called a Stack. A Stack is a data structure that not only stores data in a very specific way, but also removes data in a very specific way.
Storing Data
A Stack is essentially a list of items that are stacked in order. When a item is added to the stack that item is added to one end of the list called the “Top”. When another item is added after, it is added to the list again at the Top and “stacked” on top of the previous item. In coding terms, when an item is added to a Stack that item was “pushed”. In addition, an item that is pushed to the Stack must always have some sort of value such as an integer.
Looking at the above diagram from left to right, we start with an empty Stack. Next, an item with the value of 1 is pushed to the stack. Since the data structure is empty before pushing item 1, that item is at one end of the Stack known as the “Base” which is essentially the bottom of the Stack. After that, another item with the value of 2 is pushed to the Stack. Notice how item 2 is pushed to the Stack specifically at one end of the Stack (the Top) and “on top” of the previous item (item 1). Finally, an item with the value of 3 is pushed to the Stack which is done so in the same way as the other items. Item 3 is now at the Top of the stack.
Removing Data
Now here is where a Stack becomes unique to other data structures. When an item is removed from the Stack, it is done so from the Top. More specifically only the item that was last added to the list is removed. In coding terms, when an item is removed from the Stack it was “popped”.
Going off the previous example, if we were to preform a pop command on the Stack, item 3 would be removed from the Stack because it was at the Top end. Going more in depth, the popping of a Stack also returns the value of the item it removed, so in this case the value returned would be 3.
Visualizing a Stack in code
Going off the examples from above, here is a simple representation in code using Python.
Overview
Stack:
A data structure that stores a list of items in a specific order. The bottom is known as the Base and the top is known as the Top. Items added to a Stack are always added at the top end. When removing items from a Stack, only the last item added (which would be at the top end) would be removed.
Push:
A command that adds an item to a Stack (always at the top) and the item must always have a value.
Pop:
A command that removes an item from a Stack (always from the top) which also returns the items value.
Conclusion
Going back to the examples used in the beginning for applications of Stacks; a feature such as undo (CMD + Z) or executing code, you may now come to understand how the data structure can be useful.
In a word processor, the software records what the user types in a document and pushes the most recent entry as an item to a Stack (the entry being whatever was typed in the last few seconds). When the user uses the undo feature, the Stack pops and the software then deletes the popped item’s value which would be the last entry the user typed in the document.
When executing code, there is something called a Call Stack. Your computer utilizes a Call Stack in order to run software, executing code in order. When a block of code needs to be run, that block is pushed to the Call Stack. The Call Stack then continually pops in which the popped block of code is then run. This is an organized and efficient method of computing.
One last example; a stack of dishes! Though now you should be able to figure out how that is similar to the Stack data structure yourself 😉.