Learn Stack Data-Structure From Scratch with Interview Questions

Stack is a linear Data-Structure following First In Last Out(FILO) order ie. The last element in a stack will be removed first.

Operations on a Stack -

• push() - pushes an element in the stack.

• pop() - removes an element from the top of the stack.

• peek()/top() - returns the top element of the stack.

• isEmpty() - checks if the stack is empty or not.

• isFull() - checks if the stack is full or not

Ways of implementing Stack -

• Using Arrays

• Using Linked list

Using Arrays -

#include <iostream>
using namespace std;

class Stack{
private:
  int top;
  int cap;
  int *arr;

public:

  Stack(int c){
    top = -1;
    cap = c;
    arr = new int[c];
  }

  void push(int x){ //pushes element in the stack
    if(isFull()){
      cout<<"Stack overflow";
    }
    top++;
    arr[top] = x;
  }

  int pop(){ //removes element from the top of stack
    if(isEmpty()){
      cout<<"Stack underflow";
    }
    int p = arr[top];
    top--;
    return p;
  }

  int peek(){ //returns top elements of the stack
    return arr[top];
  }

  bool isFull(){
       if(top == cap-1){
          return true;
       }
    return false; 
  }

  bool isEmpty(){ //checks if stack is empty or not
    if(top == -1){
      return true;
    }
    return false;
  }
};

Using Linked List -

class Node
{
public:
    int data;
    Node *next;
    Node(int d)
    {
        this->data = d;
        this->next = NULL;
    }
};

class myStack
{
private:
    Node *top;
    int size = 0;
    int capacity = 5;

public:
    myStack()
    {
        top = NULL;
    }
    void push(int x)
    {
        if (size >= capacity)
        {
            cout << "stack overflow";
            return;
        }
        Node *newNode;
        newNode = (Node *)malloc(sizeof(Node));
        newNode->data = x;
        newNode->next = top;
        top = newNode;
        size++;
    }

    int pop()
    {
        Node *temp;
        int data;
        if (size <= 0)
        {
            cout << "stack underflow";
            return;
        }
        temp = top;
        data = top->data;
        top = top->next;
        free(temp);
        size--;
        return data;
    }

    bool isEmpty()
    {
        return size <= 0;
    }

    int peek()
    {
        if (!isEmpty())
        {
            return top->data;
        }
        else
        {
            cout << "Stack is empty.";
        }
    }
    void display()
    {
        Node *temp = top;
        while (top != NULL)
        {
            cout << temp->data << " ";
            temp = temp->next;
        }
    }
};

Stack Overflow and Stack Underflow -

Stack Overflow - It is a situation in which the stack is full and no elements can be pushed ie. when we try to push more items in a stack than it can hold.

Stack Underflow - this happens when we try to pop an element from an empty stack.

Top Interview Questions -

• Balanced-parenthesis problem

• Astroid-collision problem

• Celebrity-problem

• Largest-Rectangle-histogram problem

• Maximal-Rectangle problem

• Stock-Span Problem

• Next-greater-element problem

• Next-greater-element-2(Circular)

• remove-k-digits problem

• delete the middle element of the stack

• sort the stack

• reverse the stack

• Implement stack using a queue

• Implement stack using two queue

Resources to get in-depth knowledge -

Aditya Verma Stack playlist -

Love Babbar Stack playlist -

Congrats! you have learned the fundamentals of Stack Data-Structure, make sure to subscribe to my blog to follow this series and follow me on Hashnode, where I'll be uploading content on Data Structures and Algorithms every weekend.