Stack is a very usable data structure. It is not as widely as used in our daily coding tasks, because of its nature of LIFO. Let’s elaborate LIFO; LIFO is the abbreviation of Last-In-First-Out. What can it really mean for us? Well there is only one specific reason why you would want to use it that is; if you want to have a pile of things and every time you need to take one from the pile, you take it from the top.
Yes, we understood it well. In the LIFO setting we insert towards bottom and and take from the top.
Sample Stack Usage Areas
- In text editors “Undo” operations while we intend to remove an unwanted entry,
- Browsers’ back buttons; make use of a similar way to be able to navigate to the earlier pages,
- Recursive methods also utilize stack very well; starting from the first call till the last all of the operations are added on top of each other.
Complexity of Stack
Since the internals of implementations differ for each variation; Singly Linked List and Array, the operations can differ. The given table is suitable for Singly Linked List implementation;
image courtesy of bigocheatsheet.com
Operations on Stack
Stack has know three operations that we need to know. Some other implementations definitely have other operations as well like in the Java’s Stack implementation. However, these below operations are unique properties of the Stack data structure.
- push: pushes the element on top of stack
- pop: pops the element from the top and returns popped the value
- peek: returns the head data but doesn’t delete it, takes a peek at it.
There are multiple variations on the implementations; internally we can use a Singly Linked List or Array to hold the data. Then the Time Complexity of the operations differ. in the Stackoverflow Article, there are more insights of the internals of the implementations. In my own implementation I preferred to use the the Singly Linked List implementation.
The code can be also found in my Github Repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/DataStructures to see how the code works, you can also check its Unit Test.