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){
if(isFull()){
cout<<"Stack overflow";
}
top++;
arr[top] = x;
}
int pop(){
if(isEmpty()){
cout<<"Stack underflow";
}
int p = arr[top];
top--;
return p;
}
int peek(){
return arr[top];
}
bool isFull(){
if(top == cap-1){
return true;
}
return false;
}
bool isEmpty(){
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 -
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.
