Data Structure The Stack
Stack is a linear data structure which follows a particular order in which the operations are performed. I will try to explain Stack with these objectives:
- What is the Stack?
- What is the Definition?
- What are the use cases for a stack in the real world?
- How to Implement operations on a stack data structure?
What is the Stack?
Stack is data collection of data structure. It’s a data collection which relies on LIFO principles. I know you are starting to think about the meaning of “ LIFO” The LIFO means the last element added to stack will be the first element removed for a List. Basically the terminology is Last In First Out. The last thing to be added in will be the first thing to be removed. It is very important to remember this logic to understand stack well. There are many ways to implement Stack. I will implement the stack in an Array and Singly Linked List.
Let’s visualize a stack.
As we see our stack on diagram it will give us some idea how to remove items from a Linked List. According to diagram the number (9) is the last thing added on the Linked List. Based on Stack logic number(9) will be the first thing in the Linked List. If we keep removing items from the stack the second item will be number(10) then number(11) and on the end number(12) which is the first item in the Linked List will be removed.
Where to Stacks are Used
We can use stack for managing function invocations as follows.
As you see we are removing from the top on stack how our debugger animation show us on our console above.
Using Stacks in Real World
We are also using stacks in the real world. Imagine when we take a picture then we are trying to do some edit for fixing the picture adjusting the light etc. If we edited wrong action and we want to take a picture with undo and revert it original. Whatever we are edited in picture or undo we are using stacks for those actions to be use in picture. We are adding(edit) something on the picture then we are removing(undo) something from the picture. We can say this is the best example of how to use a stack in the real world.
Implementation Of Stack
I mentioned at the beginning of the article that there are many ways to implement stack. But the easiest way to implement stack to use array. Some programming languages have their own stack data type but JavaScript does not have its own stack data type. But we can still build a stack in an array or Linked list. The most important part we have to implement on Stack with the Logic as the last item added will be the first item removed.
Implementation Of Stack In An Array
As you see it’s very easy to implement a stack in an array. Based on the example above. We created a Stack with an array . As you know The push() method adds new items to the end of an array. According to Stack logic we have to remove the last item from the array. In our example “Google” is the last item in the array. If I want to keep removing the sequence of the removed items should “Google”, ‘’ FaceBook”, ‘’Amazon ‘’. We also have a method for array to make the stack easier for us. As you know The pop() method removes the last element from an array. If you implement it on your console you should see its works perfectly like in example. Actually When we use stack in arrays we don’t need indices or index numbers. We just need the last item added should be the first item to be removed. Array gives us more operations than what we need for to use a Stack. It is easy and fast to implement stack in arrays. But I will also implement stack on Linked List from scratch to make the logic clear.
Implement Stack in Singly Linked List
We talked about whether we don’t need any indices or indexes when we need to create a stack. The only thing we need is the logic of the stack. Last Item added should be the first item to be removed. I will try to implement a stack in a Singly linked list to show you how do we implement Stack from scratch?
First of all we need two classes defined called Stack and Node to store data.
class Stack {
constructor() {
this.first = null;
this.last = null;
this.size = 0;
}
}class Node {
constructor(value){
this.value = value;
this.next = null;
}
}
If you remember When we created Linked List we need two pointers which are called head and tail. We also initialized the length of the list. But When we created Stack instead of head and tail we changed our pointer as first, last and size like the same idea when we created a singly Linked list.
Also for the Node Class we have a value for each node and the next pointer in the stack.
Pushing Pseudocode
- The function should accept value
- Create a new node with that value
- If there are no nodes in the stack, set the first and last property to be newly created node;
- If there is at least one node, create a variable that stores a current first property on the stack;
- Reset the first property on the node ti be previously created variable
- Increment the size of the stack by 1
Pop Pseudocode
- If there are no nodes in the stack, return null;
- Create a temporary variable to store the first property on the stack
- If there is only 1 node, set the first and last property to be null
- If there is more Ethan one node, set the first property to be the next property on the current first
- Decrement the size by 1
- Return the value of the node removed;
class Node {
constructor(value){
this.value = value;
this.next = null;
}
}class Stack {
constructor() {
this.first = null;
this.last = null;
this.size = 0;}
push(val){
var newNode = new Node(val);
if(!this.first){
this.first = newNode;
this.last = newNode;
} else {
var temp = this.first;
this.first = newNode;
this.first.next = temp;
}
return ++this.size;
}
pop() {
if(!this.first) return null;
var temp = this.first;
if(this.first === this.last){
this.last = null;
}
this.first = this.first.next
this.size--;
return temp.value
}
}
I just want to talk about some important point in this code. As you know push() and pop() has constant time. But for Singly Linked List pop() is not a constant time. Because the pop() is to iterate all items in the list from beginning and just stop one node before the end. If we want to make it constant time we should use shift and unshift but I just changed the name of shift and unshift as push and pop but they functionally are working as unshift(adding item the beginning) and shift (removing from the beginning). The function is working much faster and have a constant time like this.
