Stacks, dinero, cash, moolah, however you choose to refer to it doesn’t matter, money makes the world go ‘round and sometimes fall apart. At a time when the stock market is seeing some of the worst single day point drops in US history and a record 3.3 million Americans have filed for unemployment. What better way is there to spend our time than to turn a blind eye to the uncertainty that is the current state of our economy and revisit classic data structures? In times of mass uncertainty and chaos, computers bring me comfort. Unlike humans they are logical, unemotional and highly predictable because the output literally always depends on your input. Currently, instead of allowing my anxiety over the pending recession and the lack of consistency with this abrupt transition to remote life to consume me, I am finding solace in knowing that no matter what tower moments life throws at us, classic data structures will always stay the same. Stacks will always store data using the LIFO method, they can be implemented using a random access data structure such as a list or a sequential access data structure such as a linked list and while I’m unsure of when I will be able to return to work or my college campus, I do know that when implemented properly all stack operations run in constant time.
In computing, stacks are an abstract data type that function similarly to a literal stack such as a stack of plates, a stack of books or a stack of cash money. The only way to add an item to a stack or remove an item from a stack is at the top end of the stack. This method is referred to as the LIFO method, “Last In First Out”. It works exactly as the name implies, the first time that is added to the stack will be the last item removed and when removing an item we must remove the most recently added item first. Stacks are considered an abstract data type because their behavior is defined by a set of operations. The two primary behaviors of a stack are push, adding data to a stack and pop, removing data from a stack. Imagine that you live in some prehistoric time where there are no credit cards, apple pay, bitcoin or even checks so you have to pay for everything with cash. Over the course of the month as you work and accumulate money, you stack or push the money onto a pile in a corner of your bedroom like a responsible pre digital payments human. At the beginning of the next month when it’s time to pay all of your bills you take from the top of the stack or pop until there is nothing left.
An example of how stacks are used in computing is the way events are stored in your browser history. When you open a new browser window you are starting a new pile or stack. With each site that you visit you are adding data to the browser history. In the event that you need to backtrack to a site that you previously visited you would pop from the top of the stack until you reached the webpage of your choice. Another application that commonly uses the stack data structure is text editors. As you write each word is being added to the stack, in the event that you need to backtrack and remove words from a paragraph you would remove them as necessary and in the backend there is a pop operation happening.
Now we are going to build a simple text editor using an array stack data structure! This implementation is referred to as an array stack because we are going to build it using a list.
If we were to print new_document we’d see [“I”, “want”, “to”, “go”, “outside”]. Which, big mood. Next I’ll remove the item at the top of the stack.
At this point, if we were to print new_document we’d see [“I”, “want”, “to”, “go”]. Finally, let’s say we wanted to remove everything from the stack and start fresh. In order to do so we could simply pop until we reach the end of the stack. Before we can remove an item from the stack we need to ensure there is an item at the top of the stack that can actually be removed. To view the item at the top of the stack or check to see if a stack is empty we’d use the following code.
This extra steps ensure that we will not try to pop an item from an empty stack which will save us from getting an IndexError. Now that you’ve gotten a refresher on stacks or hopefully learned something new about them, I challenge you to build a stack you can use a linked list or an array like I did just be sure to remember LIFO.
