Stack Data Structure

Stack is an abstract data type (ADT), which has its own values called top and operation on those values called push and pop.

  • Stack follows the principle of LIFO (Last In First Out).

Operations on Stack

There are the following operations on the stack data structure

  • push – insert element (value) into the stack.
  • pop – remove and return the top of the stack element.
  • isEmtpy – return true if the stack is empty, otherwise false.
  • isFull – return if true the stack full, otherwise false.
  • top – top is a pointer, pointing to the top of the stack’s element

Stack representation (Implementation)

We can represent the stack using the following ways

  1. Array Representation
  2. Linked List Representation

Stack Representation using Array

#include <iostream>

// size of stack
#define SIZE 5
using namespace std;

// stack definition
struct Stack {
    int arr[SIZE];
    int top=-1;
};

// s1 is a structre variable
Stack s1; 

// return true if stack is full, else false
bool isFull() {
    if (s1.top == SIZE-1) {
        return true;
    }
    return false;
}

// return true if stack is emtpy else false
bool isEmpty() {
    if (s1.top == -1) {
        return true;
    }
    return false;
}

// insert element into stack top
void push(int val) {
    if(! isFull()) {
        s1.arr[++s1.top] = val;
    } else {
        cout << "Overflow occured" << endl;
    }
}

// remove top element of the stack & return it
int pop() {
    if(! isEmpty()) {
        int n = s1.arr[s1.top];
        s1.top--;
        return n;
    } else {
        cout << "Underflow occured" << endl;
        return -1;
    }
}

int main() {
    push(4);
    push(3);
    push(2);
    push(1);
    push(0);
    
    cout << pop() << endl;
    cout << pop() << endl;
    cout << pop() << endl;
    cout << pop() << endl;
    cout << pop() << endl;
    // underflow
    cout << pop() << endl;

    
    return 0;
}

// Output
// 0
// 1
// 2
// 3
// 4
// Underflow occured
// -1
 

// adding soon

// adding soon

// adding soon

Stack Representation using Linked List

 
// stack implementation using linked list

#include <iostream> 
#define SIZE 5
using namespace std;

// Stack Node
struct Node {
    int data;
    struct Node *next;
};

// top pointer point to top of the stack node if stack not emtpy
struct Node *top = NULL;

bool isEmpty() {
    if (top == NULL) {
        return true;
    }
    return false;
} 

// insert element into stack top
void push(int val) {
    if (isEmpty()) {
        top = new Node();
        top->data = val;
        top->next = NULL;
    } else {
        Node *newNode = new Node();
        newNode->data = val;
        newNode->next = top;
        top = newNode;
    }
}

// remove top element of the stack & return it
int pop() {
    if (isEmpty()) {
        cout << "Underflow occured" << endl;
        return -1;
    } else {
        int n = top->data;
        top = top->next;
        return n;
    }
}

int main(int argc, char const *argv[]) {
    push(4);
    push(3);
    push(2);
    push(1);
    push(0);
    
    cout << pop() << endl;
    cout << pop() << endl;
    cout << pop() << endl;
    cout << pop() << endl;
    cout << pop() << endl;
    // underflow
    cout << pop() << endl;
    return 0;
}


// Output

// 0
// 1
// 2
// 3
// 4
// Underflow occured
// -1

// adding soon

// adding soon

// adding soon

Applications of Stack

  • Expression evolution.
  • Manage function calls.
  • Recursion.
  • Infix to postfix.
  • Backtracking.
  • DFS (Depth First Search)