What is a Stack?

Stack is a linear data structure that follows the Last In First Out(LIFO) principle which means the element which is pushed last will be taken out first.
A real-world example of the stack is piles of plates(We place them one over the other and when we take a plate we generally pick the top one which was placed the last). Another example of the stack is bangles that are worn by women. It is a stack of bangles as the first inserted bangle is removed at the last.

Applications of Stack:

Recursion: In recursion, there is a function call stack that decides the order in which the functions will be executed.
Undo/Redo: These also contain a stack of commands/decisions made so that undo and redo can be done.
Backward/Forward button: The backward and forward button on the webpages also uses stack on the basis on which the buttons work.

Operations:

Certain operations can be done on the data structure, that is:

push(x): x will be pushed/inserted on top of the stack.
pop(): The top element/last inserted element will be deleted.
top()/peek(): The top/last inserted element will be read.
size(): This returns the number of elements in the stack.

Implementation:

The stack can be and cannot be implemented using different data structures, let's discuss it:

As we have seen above, with stack we can insert elements at the top/the back and deletion will also be done at the back only.

Arrays:
- Static: We can use static arrays to implement stack when the size is fixed. We can take a static array and we can insert it at the back and delete it at the back as well. The limitation is the size should be fixed.
- Dynamic: To overcome the limitation of the static array, we can use dynamic arrays(Vectors in C++). Dynamic arrays use the space smartly and will only use the required amount of space and can also resize themselves while deleting.

Linked List:

We can use both Singly Linked List(SLL) and Doubly Linked List(DLL) to implement the stack.
For SLL, we can have a head pointer and we can insert and delete the elements at the head pointer.
For DLL, we can have head and tail pointers to simulate the same, as there will be a way for the tail pointer to move backward(using prev*) we can insert and delete items at the tail pointer itself.

Let's see some algorithms and solve some problems:

Algorithm: Nearest Smallest Element:

This is an algorithm that is used to find the nearest smallest element on the left/right depending on the algorithm.
For eg: A: 4 5 2 10 8 2

NSL: -1 4 -1 2 2 -1

NSR: 2 2 -1 8 2 -1
Let us see how the NSL(Nearest Smallest Element on the Left) works:

4 is the first element, and there is no smallest element for it on the left, so its NSL should be -1/any number to denote that the NSL doesn't exit. For 5, the NSL will be 4 as it is <5 and it is on the immediate left. For 2, there is no element smaller than 2 on the left so -1. For 10, its immediate smaller element on the left is 2 and it goes on.
Similarly can be done for NSR(Nearest Smallest Element on the Right) by iterating from right to left.
Same can be implemented for Nearest Greatest on the left and right as well.
We can implement this algorithm using Stack. I will discuss the entire algorithm in the upcoming articles. Stay tuned :)

Q. Given a string, we have to reverse it and print the reversed string.

Example: s="abcd" output="dcba"

We take a stack and push the string character by character into the stack and then we pop the characters from the stack and concatenate them together to form the reversed string.

Time Complexity: O(N)

Space Complexity: O(N)

string reverse(string s){
    int n=s.length();
    stack<int> st;
    for(int i=0;i<n;i++){
        st.push(s[i]);
    }
    string ans;
    while(!st.empty()){
        ans+=(st.top());
        st.pop();
    }
    return ans;
}

I have used stack data structure using STL (C++ Standard Template Library). But as discussed it can be implemented using Linked List or Dynamic arrays as well.

Summary:

Stack is a great data structure and has many real-world applications.
We saw how the stack is implemented internally, its applications, the operations done on it and some questions related to it.

A small note from my side:

This is my first few attempts at blogging, so if there are any errors please excuse me for that. I will be blogging about a lot more topics regarding DSA and computer science in general. So do consider following me on Hashnode, Twitter and LinkedIn.

I hope you all had a good read and if you gained any benefit reading this article or there is any doubt regarding the above topic or there is an error that I might have missed, leave a comment below or reach out on LinkedIn, I will be more than happy to help you out! :)

Venketesh's Blog