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)