👨💻 In here, a stack is a data structure of ordered items where items can be inserted and removed only at one end. This means that the most recently placed item can be removed from the stack first. A stack follows the LIFO (Last In First Out) principle.
To give an example, think of a pile of books. 📚 We keep one book on top of another, creating a pile with many books. When we want to retrieve a book, we remove them one by one starting from the last one until we reach the book we want. This concept is called Last In First Out (LIFO). The book we put on top of the pile last is the one we retrieved first. 📖
💡Stack is a Last In First Out data structure.
In stack, there are some basic operations. Mainly there are three main operations.
1. Push2. Pop
3. Peek
Also, there is one main initialization called top.
So let’s see what basic operations do.
Push()
When we work with a stack, we add elements to it using a push operation. However, before doing so, we need to check whether the stack is already full or not. This is especially important when we implement the stack using arrays. In such cases, the size of the array is predetermined, and we can only grow or shrink the stack within that size.
To illustrate this, let's consider an example where we need to add 20, 40, 60, and 80 to a stack that already has one element. First, we need to check if the stack is not already full. If it is not full, then we can proceed with the push operation. The images below can help you understand this concept more clearly.
First, let’s draw the stack we have.
Before that, I said that there is one main initialization called top. So always top will be pointed to the last element of the stack.
Let’s add the elements.
Now, What will happen?🤔We push the 20 to the stack but still the top is 10 Is it correct?
It is incorrect. So we must have to point the top into the last element so now the top should be pointed to the 20.
Let’s do the remaining as we did like before.
So finally the stack will look like below.
Pop()
This will look at the item on the top of the stack and remove it. The operation pop will get the item at the top and will remove it. Before doing the pop() operation, we should have to consider whether the stack is empty or not. Because if the stack is empty then what should we remove? There are no elements. So we have to first consider whether the stack is empty or not. If the stack is not empty then we can do the pop operation. For better understanding let’s move on to an example.
There is a stack with four elements. So let’s do the pop operation.
Is this empty? No, It’s not. Then we can do the pop().
The top was 40. But now it is removed. Now what should be the top? Always the last element should be the top. So now the last element is 30. The top should be pointed to 30.
Likewise, we can do the pop operation until the stack is empty.
So now the stack is empty. Furthermore, we can’t do the pop operation.
I think that you have a clear idea about how pop() works. Let’s move on to see how Peek() works.
Peek()
When we perform a peek operation on a stack, we are simply checking the top item on the stack without removing it. For instance, if we have a stack with four elements, namely 10, 20, 30, and 40, the top of the stack will be pointing to 40. By performing a peek operation, we can retrieve the value of 40 but it will remain in the stack.
Let’s clear it with illustrations.
Here the top is pointed to 40.
💡The Pop() operation will remove and get the top element but the Peek() operation gets the top element without removing it. Pop() and Peek() operations can not be done if the stack is empty.
Well, Now you have a clear idea about what stack and the operations of it. Let’s see how to implement the stack using array and LinkedList.First, we will look at how to implement a stack using an array.
Let’s implement an efficient stack using an array: optimal data structure for Push, Pop, and Peek operations in your code
As a first step, we have to initialize the size of the stack. After we are initializing the size, then we can add the elements to an array.
Let’s consider about size of 4 arrays.
💡If the size of an array is 4, Then the length of it will be always 1 greater than the size. Here length will be 4+1 = 5.
Let’s push……
Wait a moment❗Did you forget something?🤔
Do you remember? We have to consider whether the stack is full or not before doing the push operation. In this case, it is not full it is empty. So we can continue.
❌We can not push 60. Because the array is already full.
The final stack which is implemented by the array will look like below.
If we want to add 60, then we have to delete one element and put 60 into that location. But do you remember? Stack is LIFO(Last In First Out) data structure. So the last element should go out first. Then we have to first delete the 50 and push 60. So how to do the pop() operation? Let’s see.
When we do pop() operation 50 will be removed.
Then it will look like this and the top will be pointed to the 40.
So now there is one space, then we can add 60 by doing a push() operation.
But instead of pop() if we did the peek() operation, It won't remove the 50. But it will get the 50. Because it is the element which is pointed by the top and it is the last element.
As we implemented the stack using an array, Also we can implement the stack using LinkedList.The main advantage of implementing a stack using a linked list is that we don't have to decide on the size of the stack beforehand. Let's go through the steps to implement a stack with elements 10, 20, 30, and 40 using a linked list. First, create the linked list and then add the elements in the order specified.
To add the nodes we have to use the push() operation. In the first stage, we have an empty node.
When we need to remove the element, We have to do the pop() operation. Let’s consider the above stack.
When we do a pop() operation it will delete the last node and the top will be pointed to the node before the last one as below.
But if we do the peek() operation it won’t remove the node but it will get the node which is pointed by the top.
Let’s consider the above stack.
