Understanding Stacks

Stacks are one of the non-primitive linear data structures. It follows the principle of last in first out (LIFO) principle or first in last out (FILO).

Stacks are containers with only one opening that allows them to perform operations like push, pop, peek etc.

Stacks are containers with only one opening that allows them to perform operations like push, pop, peek etc. You can think of it as a stack of boxes on top of each other. The box can be placed only at the top of the previous box (push), and only the topmost box can be accessed at any time (peek). To access any other box, we have to remove all the boxes on top of it (pop).

Implementation of a Stack Using Arrays

Let’s design our own stack using arrays that follow the requirements above. 

//C++
 
class Stack{
public:
    int arr[1000];
    int top;
    int size;
    
    Stack(){
        top = -1;
        size = 1000;
    }
    void push(int x){
        if(top == size - 1) cout<<"Stack Overflow\n";
        else arr[++top] = x;
    }
 
    void pop(){
        if(top == -1) cout<<"Stack Underflow\n";
        else top--;
    }
    int peek(){
        if(top == -1) {
cout<<"Stack is empty\n";
return INT_MIN;
   }
        return arr[top];
    }
};

As we have implemented a stack using arrays, the size of the stack is not dynamic. Every time we do a push, pop, or peek operation to ensure that the stack is not overflowing or underflowing; otherwise, we might receive garbage values.

Time complexities:

push = O(1)
pop =  O(1)
peek = O(1)

Implementation of a Stack Using Linked Lists

Let’s design a stack using linked lists that follows the requirements above. 

class Node{
public:
int val;
Node* next;
Node(int data){
val = data;
next = NULL;
}
};
 
class Stack{
Node* top;
public:
Stack(){
top = NULL;
}
 
void push(int x){
Node* newNode = new Node(x);
newNode->next = top;
top = newNode;
cout<<"pushed "<}
void pop(){
if(!top) cout<<"Stack Underflow\n";
else 
{
top = top->next;
cout<<"popped the top element\n";
}
}
int peek(){
if(!top){
cout<<"Stack is empty\n";
return INT_MIN;
}
return top->val;
}
};

Implementing stack using linked lists instead of arrays makes it dynamic in size. The only disadvantage is extra memory used to store pointers.

Time complexities:

push = O(1)
pop =  O(1)
peek = O(1)

C++ STL Stack

C++ Standard template library provides in-built stack containers.

#include 
#include  
using namespace std;
int main() {
    stack s;
    for(int i=0;i<50;++i){
        s.push(i);
    }
    for(int i=0;i<50;++i){
        cout<";
        s.pop();
    } 
    return 0;
}

Uses of the Stacks

Backtracking algorithms: In backtracking algorithms, we frequently need to go back to the previous state if the current state is not leading to the solution. This can be done by storing previous states in the stack.

Function call: Whenever we call a function, we don’t just need to execute the instructions inside the function, but we need to return to where we left. This is done by storing the address of the program counter in the stack, assigning the address at the top of the stack to the program counter, and popping the stack whenever the function is complete.

Web browser back button: Your web browser keeps a stack of the web pages that you have visited in that window and goes back to the last website whenever you click the back button.

Balanced parentheses: Stack is used to checking if the given set of parentheses are balanced if every opening bracket has a corresponding closing bracket.

Evaluating expressions: Stack is used to evaluating mathematical expressions in infix, postfix, or prefix.

Converting expressions: Stack is also used to convert between postfix, prefix and infix expressions.

Undo Redo operations.

String reversal: Characters are pushed in a stack is popped in reverse order.