Stack is one of the most popular and widely known data structures in computer science, and one of the easiest to learn and understand. But often, maybe because of the way it is introduced or taught, it seems kind of useless and boring to learn.
Stacks are not one of those useless thing that you need to learn just to pass your exams or to crack the coding interview, but they are actually used for a lot of things that you do daily on the computer.
Practical Applications
They are the building blocks of function calls and recursive functions. Yes, this is a common application that you maybe aware of, but think about it — right now there are hundreds (if not thousands) of functions existing on your call stack in memory maintained by your OS. Every time a function is called, some memory is reserved (PUSH) for it on the call stack, and when it returns, the memory is deallocated (POP).
The undo/redo function that has become a part of your muscle memory now, uses the stack pattern. All your actions are pushed onto a stack, and whenever you ‘undo’ something, the most recent action is popped off. The number of undos you can do is determined by the size of this stack.
The stack pattern is also used to keep track of the ‘most recently used’ feature. I am sure you have come across the most recently seen files, items, tools etc.. across different applications. Your browser uses the stack pattern to maintain the recently closed tabs, and reopen them.
Your code editor uses a stack to check if you have closed all your parentheses properly, and even to prettify your code.
This ties to the more formally described use case of stacks — expression evaluation and syntax parsing. They are used to convert one notation of expression into another (like infix to postfix etc..), this is actually used in calculators. If you have prepared for coding interviews, you know the famous parentheses matching problem is solved using stack.They are used to implement back tracking algorithm, which is basically an algorithm with a goal, and if it takes a wrong path it simply ‘back tracks’ back to a previous state. These states are maintained using stacks. Simple games like tic-tac-toe can be solved using this approach.
A similar concept is used in the Depth First Search algorithm.Increase efficiency of algorithms — Several algorithms make use of the stack data structure and its properties. Examples are Graham Scan — which is used to find the convex hull, and the problem of finding the nearest smaller or larger value in an array.
The Stack Pattern
So what makes stacks special ? Well, it is the Last In First Out property — the element that was added last to the stack is removed first. There is only one way to insert or remove an element from a stack — from the top.
Stacks are often compared to a stack of plates in restaurant kitchens, where adding a new plate or removing an existing one from the stack is only possible from the top.
In computer science, instead of plates we store objects in the stack. They could be anything from numbers, strings, memory addresses, entire functions or even other data structures.
There are three operations that can be performed on a stack data structure:
PUSH: adds an element to the stack
POP: removes an element from the stack
TOP/PEEK: returns the value of the current element on top of the stack, without actually removing it.
Now say you push 3 items into the stack, A, B and C in order. Now C is on the top. Popping off elements would give you C, B and A. So the LIFO pattern can be also used to reverse a set of ordered items.
Implementing Stacks
Most programming languages nowadays have an inbuilt library for implementing stacks. If you are interested, you can implement it yourself from scratch too. Here are common implementations of stacks in Python and C++, especially useful if you are preparing for coding interviews.
Python
In python, the list data structure can be used as a stack.
C++
The C++ STL (Standard Template Library) has a great implementation of stack.
The idea behind this whole post was simply to appreciate how the simple stack data structure plays a very important role in how we use computers every day. If you enjoyed this, I am planning to do a series on other data structures as well, so please consider following and check out my YouTube Channel.
For questions, comments, feedback feel free to email me at adarsh1021@gmail.com or connect with me on Twitter (@adarsh_menon_ ).
Top comments (0)