Stack is the most popular and historical data structure. A list of items arranged one on top of others. Stack data structure popularly used to maintain program memory stack. It follows the last-in-first-out order. Let’s consider a stack of discs as shown in the below picture.
As shown in this diagram, only the top node can be removed at once.
In programming, We can implement stacks using either arrays or linked lists data structures. First of all, let’s try to take an example of stack and understand its implementation using arrays.
Example:
Input = {5, 10, 8, 3, 2, 9}
Top: 9
Stacks supports basic operations, those are push and pop. Let’s see these operations using arrays.
Push Operation
Initially top starts with index 0, If an element with value ‘5’ wants to push into an array it inserts at the top position then top moves to its next index, as shown in the picture.
After pushing 10 into the stack as shown in the picture top moves to its next position.
Now it pushes ‘8’ to the stack as shown in the picture. Here top moves to position 3.
Similarly, element 3 pushed into the stack and top moves to 4.
Value 2 pushes into stack and top is now at index 5 as shown in the picture.
Finally push 9 at top and move top to its next index as shown in the picture.
Stack cannot go beyond its capacity, as here its capacity is 6.
// Simple snippet to push logic.
if(top < capacity)
{
stack_arr[top] = input;
top++
}
Pop, In contrast while popping an element from the stack it first top moves to its previous position. Check below two-line snippet for how pop works.
// Simple snippet for pop logic
if(top > 0)
{
top_elm = stack_arr[top];
top--;
}
return top_elm;
Both these operations are of time complexity. The final code is as shown below.
Complexity:
Push: ,
Pop:
You can find some interesting problems at http://rjp.b44.myftpupload.com/tag/stack/
This is all about stack and its operations. If you have any approach which helps readers to understand better please write it in the comments below. Cheers!.