4. Connecting the dots — Big O and Stacks Data Structure
I wrote about linear data structures such as Arrays and Linked list(LL) previously. Now, let us look into Stacks which is also a linear data structure and is very similar to LL. A Stack is a collection of items that can only be stored or deleted in a particular order. An example of this would be pressing the back button on the browser to visit the previous webpages visited. In this case the last visited will be on the top.
Another example is a toy rings stacked vertically (see below). The last ring we put in first (blue colored ring) will be taken out last, and the items we put in last will be taken out first. This is called the last-in-first-out (LIFO) principle.
Stacks are represented from top to bottom like below.
Steps for creating a Stack
- Creating a node with Stack is same as previous article.
2. Creating a Stack with a single object
An object with a single node with a value of 8 gets created and the output is shown below.
Pushing an item to the top of the stack
Adding at the top in stack is very similar to adding to the beginning in Linked List using unshift(). We will be renaming unshift() to push() because we are adding it to the top.
Here is the output of push(). The length of the node is 5 and we add 8 to the top of the stack
Removing an item to the top of the stack
When we delete an item, we pop the top element off. No need to iterate through any data. So, the time taken for adding and removing a new item from the top of the stack will be Big O (1).
When we try to search for an item in a stack we’d have to search over all the items in the stack. The amount of time needed is directly proportional to the number of items in the stack which will be Big O (n).
Below is the entire code for stack data structure implemented.
With that, we covered an another interesting linear data structure.
To summarize, Stacks data structure comes into play when the order of actions are important. They have time complexities of Big O(1) or Big O(n) depending on the type of operation performed.
If you like this article, please follow me and give a clap!