
Stack
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
- Array Representation
- 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)