# 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.

![Stack Representation](https://www.tutorialspoint.com/data_structures_algorithms/images/stack_representation.jpg align="center")

## 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 -

```cpp
#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 -

```cpp
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](https://github.com/ratishjain12/DSA/blob/main/Stack%26Queue/stack/questions/balanced-parenthesis.cpp)
    
*   [Astroid-collision problem](https://github.com/ratishjain12/DSA/blob/main/Stack%26Queue/stack/questions/asteroid-collision.cpp)
    
*   [Celebrity-problem](https://github.com/ratishjain12/DSA/blob/main/Stack%26Queue/stack/questions/celebrity-problem.cpp)
    
*   [Largest-Rectangle-histogram problem](https://github.com/ratishjain12/DSA/blob/main/Stack%26Queue/stack/questions/largest-rect-histogram.cpp)
    
*   [Maximal-Rectangle problem](https://github.com/ratishjain12/DSA/blob/main/Stack%26Queue/stack/questions/maximal-rectangle.cpp)
    
*   [Stock-Span Problem](https://github.com/ratishjain12/DSA/blob/main/Stack%26Queue/stack/questions/stock_span.cpp)
    
*   [Next-greater-element problem](https://github.com/ratishjain12/DSA/blob/main/Stack%26Queue/stack/questions/next-greater-element.cpp)
    
*   [Next-greater-element-2(Circular)](https://github.com/ratishjain12/DSA/blob/main/Stack%26Queue/stack/questions/next-greater-element-2.cpp)
    
*   [remove-k-digits problem](https://github.com/ratishjain12/DSA/blob/main/Stack%26Queue/stack/questions/remove-k-digits.cpp)
    
*   [delete the middle element of the stack](https://github.com/ratishjain12/DSA/blob/main/Stack%26Queue/stack/questions/deleteMiddle.cpp)
    
*   [sort the stack](https://github.com/ratishjain12/DSA/blob/main/Stack%26Queue/stack/questions/sortStack.cpp)
    
*   [reverse the stack](https://github.com/ratishjain12/DSA/blob/main/Stack%26Queue/stack/questions/reverseStack.cpp)
    
*   [Implement stack using a queue](https://github.com/ratishjain12/DSA/blob/main/Stack%26Queue/stack/implementation-prblms/usingqueue.cpp)
    
*   [Implement stack using two queue](https://github.com/ratishjain12/DSA/blob/main/Stack%26Queue/stack/implementation-prblms/usingtwoqueue.cpp)
    

## Resources to get in-depth knowledge -

Aditya Verma Stack playlist -

%[https://www.youtube.com/watch?v=P1bAPZg5uaE&list=PL_z_8CaSLPWdeOezg68SKkeLN4-T_jNHd] 

Love Babbar Stack playlist -

%[https://www.youtube.com/watch?v=_6COl6V6mng&list=PLDzeHZWIZsTrhXYYtx4z8-u8zA-DzuVsj] 

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.