There’s a lot of miscellaneous computer science jargon. So much so, that it can be overwhelming to try and comprehend it all.
One such term that is thrown around often is the stack.
I’ve found that so many programmers and engineers use the stack to describe everything, from a data structure, to a technical stack, to a hardware stack, to a stack of plates or pancakes.
So what exactly is a stack? In this article, we’ll dive into the concept and applications of the stack data structure.
What is a stack?
If you asked someone who knew nothing about computer science about a stack, they might tell you that it’s a collection of items that are piled on top of each other.
And in fact, that’s not far from the truth in computer science as well.
If you have a stack of plates, where would you take a plate from? Where would you add a plate?
A typical answer for both questions would be the top of the stack of plates. When you need a plate, the fastest way to get it is from the top of the stack. When you need to store a plate, the fastest way to store it is to place it on the top of the stack.
(This cat adeptly proves that taking from the top of the stack is the easiest)
This line of thinking is very similar to the way the stack data structure is described.
A stack is an Abstract Data Type (ADT) that represents a list of items. More specifically, it describes the operations you can perform on this list.
Using a stack, one can either have an item “pushed” ( added ) onto the last item of the list, or have the last item “popped” ( removed ) from the list. Typically, only the top item of a stack is accessible, but that can change from implementation to implementation.
This way, you can only have the ability to change the very last item of the list at one given point in time. This pattern is called Last In, First Out (LIFO), and refers to the way in which data is added and removed from the list ( the last element added is the first to be removed ).
Now that you know what a stack is, what the heck is an Abstract Data Type?
An Abstract Data Type, also known as an ADT, is a set of rules to store data. In the stack’s case, the set of rules is that the data is stored in a list, and you can only take from and add to the top of the list. How you actually implement this ADT using code is up to the programmer, hence why it is called abstract. As long as it functions according to the set of rules, it is that data type/structure.
There are many different ADTs, but that is pretty much the minimum of what you’d need to know about ADTs.
If you’d like to know more about ADTs and some examples of them, this GeeksForGeeks article dives into the subject:
Abstract Data Types - GeeksforGeeks
Abstract Data type (ADT) is a type (or class) for objects whose behaviour is defined by a set of value and a set of…
Uses of stacks
It’s hard to grasp the true strength of the stack data structure without seeing it in action, so here are a few examples in which stacks are useful:
Backtracking is a common use of stacks, used in order to retain history and “backtrack” through that history in order to achieve a result.
A few examples of algorithms that would require backtracking include pathfinding, the undo/redo features in certain software, and game AI. There are countless more, but we’ll use a maze pathfinding algorithm as an example.
Here, we traverse a maze as indicated by the red line in the diagram below:
Whenever we move a single space, we would “push” that movement onto the stack (whether the movement is indicated by maze coordinates or by move direction doesn’t matter).
Whenever we would reach a dead end, we “pop” a movement off and check if a unique movement is possible from the previous move. If not, we repeat that process, until a new unique path is found and we “push” that movement onto the stack.
This process repeats until whatever desired result is reached (maybe finding the exit, or a specific square, or merely traversing the entire maze). You can find some example code of a maze pathfinding algorithm below:
You may find that backtracking is also achievable through the use of recursion, and also the queue ADT. While queues are out of the scope of this article and somewhat unrelated, recursion is similar to the use of stacks and much more relevant.
We’ll go into further detail of why that is in the stacks and recursion section.
While most operations and expressions in coding languages are written using infix notation, they’re often evaluated differently by the machine.
Before the code is executed by the machine, the expression is converted from infix to postfix ( or sometimes prefix ) notation. Understanding of these different notations is not needed, but here’s a quick diagram showing how they’re formatted if you’re curious:
Conversion from one notation to the other is done using a stack. Evaluation of a postfix/prefix expression is also done using a stack and is much faster than evaluating an infix expression. This is the primary reason this conversion is used. During runtime, the machine analyzes the expressions in postfix/prefix notation and improves performance in doing so. For time’s sake, I won’t go into the algorithms for conversion and evaluation. If you want to check out those algorithms, GeeksForGeeks provides useful explanations and code walkthroughs below:
— Infix to Postfix conversion —
Stack | Set 2 (Infix to Postfix) - GeeksforGeeks
Stack | Set 2 (Infix to Postfix) Prerequisite - Stack | Set 1 (Introduction) Infix expression:The expression of the…
— Evaluating a postfix expression —
Stack | Set 4 (Evaluation of Postfix Expression) - GeeksforGeeks
The Postfix notation is used to represent algebraic expressions. The expressions written in postfix form are evaluated…
The Call Stack
In all likelihood, you’ve already used the call stack, even if you haven’t heard of it before.
Each program is typically assigned a single call stack at runtime (or one per thread if the program is multi-threaded). The prime purpose of a call stack is to keep track of the current function call (or context) a program was in.
Once a function call returns, it is popped off of the top of the stack and the return value of that function call is given to the previously called function (which is now at the top of the stack).
Below is an example of the call stack in action, with some details left out for simplicity’s sake.
It’s up to the implementation of the operating system or language to determine what kind of information a call stack holds (local variables, parameters, context, etc). But each and every call stack will always keep track of the function call (or whatever equivalent) the program is currently in.
Since the stack is an ADT, it stores data, which means there must be some sort of limit to how many function calls can be pushed onto the call stack. Once the allocated memory limit for the call stack is reached, a “Stack Overflow” error typically occurs.
A common time in which you might see this error is if you are experimenting with recursion.
Recursion is the process in which a function makes a call to itself. Without base cases or recursive cases, this can easily form an infinite loop in which a function calls itself over and over again until it eventually exceeds the memory limit of the call stack and crashes the program.
An exception to this case is if the language supports tail recursion or something like it to prevent recursion from filling the call stack.
Tail recursion is an optimization done by the compiler, where if the recursive call is the last line of the function, there is no need to add the recursive call to the stack if it’s just the same function with new parameters.
For a more in-depth explanation of how tail recursion works, take a look at this GeeksForGeeks article:
Tail Recursion - GeeksforGeeks
What is tail recursion? A recursive function is tail recursive when recursive call is the last thing executed by the…
The call stack keeps track of the history of function calls. This permits the program to be able to keep track of things such as local scope and parameters, and also allows for recursion as a concept.
Stacks and Recursion
If you recall at the end of the backtracking section, recursion was offered as an alternative to using a stack data structure. The reasoning behind this is that recursion also uses a stack. Specifically, the call stack.
Since it’s because of the call stack that we’re able to use recursion, it’s actually possible to simulate the behavior of recursion in a program using a stack.
There are some pros and cons to simulating recursion:
- A big plus is that it usually uses less RAM, as making a function call creates more overhead. Some of this overhead can be mitigated using tail recursion if it’s supported in the language you’re using.
- In most languages, the amount of memory allocated for the call stack is less than the amount you can allocate with your own stack. This means using your own stack will allow for more flexibility as you progress into further levels of depth.
- It is typically more intuitive to write recursive functions than it is to design a loop that makes use of your own stack. Thus, recursive functions are often easier to write.
Overall, in terms of performance, using your own stack to simulate recursion is almost always better. However, it is often easier to implement a recursive function over simulating a recursive algorithm with a stack. It’s up to you to decide whether that extra bit of performance is worth the time.
Why we use stacks
There are many, many different applications of the stack; this article barely scratches the surface of the things it is used for.
In spite of that, all of these applications of the stack will use the concepts described above, because stacks are used for their intuitive ability to track history. There are other ways you can use stacks, but this is the most prominent application of the stack.
Remember that even though many different applications of the stack exist, they all do the same thing: they push and pop data from a stack. This generality is what makes stacks, as well as ADTs, so useful.