Use of The Stack Data Structure
And its implementations, by Declan O’Donnell.
Introduction
This is an introduction to the use of the stack data structure it’s implementations. If you’re familiar with a little bit of programming but don’t yet know what stacks are… you’re in luck! That’s because you can imagine a stack as an array or linked list, except simpler, but first, let’s delve into the stack data structure itself.
What is a Stack Data Structure?
Stacks are an elementary data structure. A stack is a linear data structure that has restricted access. They are an ordered list or a collection that follows rules for insertion and deletion of data. Stacks follow the first-in-last-out (FILO) or the last-in-first-out (LIFO) patterns.
Stack Rules and Flow
As mentioned above, insertion and deletion of data are only possible from one end, hence the linear nature of a stack data structure. A real-world example of this could be a stack of plates or a C.D stack.
CD’s can only be ‘added’ to the top of the stack and can also only be ‘removed’ from the top. (FILO)
This operation of insertion and deletion is known as push and pop. There are many methods of the stack, we will go through a few of the more common ones below. As we saw above push is the insertion method which adds data to the top of the stack. Pop removes the topmost data from the stack.
Another common method is peek, which is similar to pop but in this case, we don’t remove the data completely. We just take a peek of the topmost data in the stack without removing it.
Some other methods include isEmpty and isFull. As the names suggest these methods check to see if the stack is empty or full and return booleans depending on the outcome. isEmpty will return true if the stack has no data. The inverse is true for isFull.
Implementing The Stack
A stack is implemented by allocating memory. There are two different ways to process this. We can either implement data statically such as using arrays or dynamically using linked lists. We will see this in the next example.
Let’s say you have a stack with the size of 3, implemented with either static or dynamic memory allocation. This memory is a finite resource and when initialized the top of the stack is at position -1. We then push some data onto the top of the stack, the top of the stack has now moved to position 0 and is occupied by the data.
We can keep calling this until we get to the maximum size allocated to memory. Once the top element is at the current size of the stack, if we try to push more data on top we get an Overflow error condition. To combat this we would need to allocate more memory to the stack or delete some of the stack’s data.
Let’s delete some of the data using the pop method as seen below. Now, what happens when the stack is empty and we try to use the pop method? As you may have guessed, we get an error with an Underflow condition. This is the opposite of the Overflow condition.
Stack in Code
Stack methods push, pop and size
What are the applications of the Stack?
The first basic application we will look at is if you wanted to reverse an array, string, or word. We do this by simply using push to insert each character, once completed we use pop to get the reversed result from the stack.
Another popular application of the stack is one we are all too familiar with which is the ‘undo’ mechanism used in most text editors. When you use the undo command the stack pops the last process pushed to the stack. When you use the redo command, you push the same command you popped into the redo stack.
A third and probably the most important for some programming languages and the web browser is the stack used in function invocations. When you call or invoke a function it gets pushed to the stack and then some value is returned. Recursive functions also use this pattern although recursion is a chain of functions that then calls itself based on the results returned from the function and stored in the stack. This can be seen in the Tower of Hanoi algorithm.
As well as in many algorithms, the stack data structure is used in multiple solutions. We mentioned the Tower of Hanoi algorithm above, it is also used in,
to name a few. Now onto the call stack and the implementations of a linear data structure.
The Call Stack
In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, program stack, control stack, run-time stack, or machine stack, and is often shortened to just “the stack”.
Although maintenance of the call stack is important for the proper functioning of most software, the details are normally hidden and automatic in high-level programming languages.
Put simply the call stack is a fancy To-Do list of function invocations. It is fundamental to how JavaScript and other synchronous programming languages work. It can also be very helpful for debugging due to its linear structure.
The “main” function you see in the stack above is always called from the program. It is the initialization of the first invoked function. Let’s say we have multiple functions, multiply, square, and printSquare, that call each other with a single invocation. It would look something similar to this.
We can see that using the methods we discussed earlier, we push the function calls onto the stack in order then pop them off as they return their results into the next call in the stack until main is invoked and the results are shown.
The call stack needs to wait to be completed before the next function can be invoked. If we had an infinite loop or a recursive function with no stopping condition, it would look something like this.
What do you expect to get as a result of this?
You guessed it! A stack overflow condition! As you can see the chrome browser only has a certain amount of memory allocated to the call stack. Once this size is exceeded it throws an error like the one shown in the image above.
If a call is unable to be completed and doesn’t get popped off the stack other functions or calls are blocked and can not be completed, they are left hanging. This is a process called blocking in the event loop. You may have experienced this when a page won’t refresh and the loading wheel is hanging in an infinite loop causing lag and packet loss.
To get around this we use asynchronous code or a process called multi-threading, but that is a story for another day!
Wrap Up
Hopefully, you’ve been able to learn a thing or two about stack data structures and their implementations in computer programming. This is but a scratch on the surface of this topic and in the future, I intended to follow up with a more in-depth analysis of the event cycle and callback queues! If not, at least you walked away knowing an additional data structure! Here is a quick overview of some of the topics discussed.
Stack operations:
- pop — Pulls (removes) the element out of the stack. The location is specified by the pointer
- push — Pushes (inserts) the element in the stack. The location is specified by the pointer.
- peek — returns the item on the top of the stack, without removing it.
- empty — returns true if the stack is empty, false otherwise
- size — returns the size of the stack
Stacks in detail:
- The stack data structure is a linear data structure
- It is an ordered set or collection of stack frames with the most recent data or set of data on top of the stack.
- The bottom of the stack is the first set of data, function issued, or pushed to the stack.
- The stack is processed from top to bottom and uses a LIFO or FILO workflow.
I hope this clarifies how the stack data structure and more specifically the call stack are handled in computer programming. If you wish to continue your journey to learn more, make sure to visit the following references:
