In this tutorial, we are going to learn the Stack Data Structure and how to implement stack in C, C++, Java, Python .
Stack is a Linear Data Structure in which operation performed from one side only i.e. Top Of The Stack.
The real life example of stack is pile of plates where plates are simply placed top of each other.
The plate at 1st position is pushed first and the plate at 5th position is pushed at the end. This means order of operation in stack is LIFO(Last In First Out) or FILO(First In Last Out).
Operations of Stack
Following basic operations are performed in the stack:
Push
: Add an element to top of the stack. If stack is full then its overflow condition.Pop:
Remove an element from top of the stack. If stack is empty then its underflow condition.Peek or Top:
Show element at top of the stack without removing it.isEmpty
: Returns True if stack is empty else return FalseisFull:
Returns True if stack is full else return False
Time Complexity of array based stack for push(), pop(), peek(), isEmpty() & isFull() is O(1) i.e. constant time.
Applications of Stack
- Infix to Post-fix conversion
- Undo-Redo functionality in editors, browsers.
- To go backward and forward in web browsers.
- In Depth First Search(DFS) algorithms.
- String reversal
Stack Implementations using array
#include <stdio.h> #include <stdlib.h> #define MAX 10 int count = 0; // Creating a stack struct stack { int items[MAX]; int top; }; typedef struct stack st; void createEmptyStack(st *s) { s->top = -1; } // Check if the stack is full int isfull(st *s) { if (s->top == MAX - 1) return 1; else return 0; } // Check if the stack is empty int isempty(st *s) { if (s->top == -1) return 1; else return 0; } // Add elements into stack void push(st *s, int newitem) { if (isfull(s)) { printf("Overflow"); } else { s->top++; s->items[s->top] = newitem; } count++; } // Remove element from stack void pop(st *s) { if (isempty(s)) { printf("\n Underflow \n"); } else { printf("Item popped= %d", s->items[s->top]); s->top--; } count--; printf("\n"); } // Print elements of stack void printStack(st *s) { printf("Stack: "); for (int i = 0; i < count; i++) { printf("%d ", s->items[i]); } printf("\n"); } // Driver code int main() { int ch; st *s = (st *)malloc(sizeof(st)); createEmptyStack(s); push(s, 1); push(s, 2); push(s, 3); push(s, 4); printStack(s); pop(s); printStack(s); }
#include <iostream> #include <stdlib.h> using namespace std; #define MAX 10 int size = 0; // Creating a stack struct stack { int items[MAX]; int top; }; typedef struct stack st; void createEmptyStack(st *s) { s->top = -1; } // Check if the stack is full int isfull(st *s) { if (s->top == MAX - 1) return 1; else return 0; } // Check if the stack is empty int isempty(st *s) { if (s->top == -1) return 1; else return 0; } // Add elements into stack void push(st *s, int newitem) { if (isfull(s)) { printf("Overflow"); } else { s->top++; s->items[s->top] = newitem; } size++; } // Remove element from stack void pop(st *s) { if (isempty(s)) { printf("\n Underflow \n"); } else { printf("Item popped= %d", s->items[s->top]); s->top--; } size--; cout << endl; } // Print elements of stack void printStack(st *s) { printf("Stack: "); for (int i = 0; i < size; i++) { cout << s->items[i] << " "; } cout << endl; } // Driver code int main() { int ch; st *s = (st *)malloc(sizeof(st)); createEmptyStack(s); push(s, 1); push(s, 2); push(s, 3); push(s, 4); printStack(s); pop(s); printStack(s); }
class Stack { private int arr[]; private int top; private int capacity; // Creating a stack Stack(int size) { arr = new int[size]; capacity = size; top = -1; } // Add elements to stack public void push(int x) { if (isFull()) { System.out.println("OverFlow\n"); System.exit(1); } arr[++top] = x; } // Remove element from stack public int pop() { if (isEmpty()) { System.out.println("Underflow"); System.exit(1); } return arr[top--]; } // function to return the size of the stack public int size() { return top + 1; } // Check if the stack is empty public Boolean isEmpty() { return top == -1; } // Check if the stack is full public Boolean isFull() { return top == capacity - 1; } public void printStack() { for (int i = 0; i <= top; i++) { System.out.println(arr[i]); } } public static void main(String[] args) { Stack stack = new Stack(5); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.pop(); stack.printStack(); } }
# Creating a stack def create_stack(): stack = [] return stack # Creating an empty stack def check_empty(stack): return len(stack) == 0 # Adding items into the stack def push(stack, item): stack.append(item) # Removing an element from the stack def pop(stack): if (check_empty(stack)): return "underflow" return stack.pop() stack = create_stack() push(stack, str(1)) push(stack, str(2)) push(stack, str(3)) push(stack, str(4)) print("popped item: " + pop(stack)) print("Elements in the stack " + str(stack))