Contents
Definition
Stack is a very usable data structure that brings the LIFO setting into the game. Let’s elaborate LIFO; LIFO is the abbreviation of Last-In-First-Out. What does LIFO really mean for us? The intentions may vary and one of them is to have a pile of things stacked down to the bottom and take one from the top. Let’s apprehend the below illustration:
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 revert 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 method executions are added on top of each other.
Implementation
In the internally Stack can implement Singly Linked List or Array. Eventually the Time Complexity of the operations will slightly differ. In this stackoverflow Article, there are more insights and argument about the implementations. In my own implementation I preferred to use the Singly Linked List implementation.
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 three vital operations that we need to cover up. In some other languages and Stack implementations definitely have other additional operations like Java’s Stack implementation. However, these below operations are fundamental 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.
Code
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.