Data Structures & Algorithms
DSA - Home
DSA - Introduction
DSA - Environment Setup
DSA - Algorithms Basics
DSA - Characteristics of Algorithms
DSA - Asymptotic Analysis
Data Structures
DSA - Data Structure Basics
DSA - Data Structures and Types
DSA - Array Data Structure
Linked Lists
DSA - Linked List Data Structure
DSA - Single Linked List Data Structure
DSA - Doubly Linked List Data Structure
DSA - Circular Linked List Data Structure
Stack & Queue
DSA - Stack Data Structure
DSA - Expression Parsing
DSA - Queue Data Structure
Searching Algorithms
DSA - Searching Algorithms
DSA - Linear Search Algorithm
DSA - Binary Search Algorithm
DSA - Interpolation Search
DSA - Jump Search Algorithm
DSA - Exponential Search
DSA - Fibonacci Search
DSA - Sublist Search
DSA - Hash Table
Sorting Algorithms
DSA - Sorting Algorithms
DSA - Bubble Sort Algorithm
DSA - Insertion Sort Algorithm
DSA - Selection Sort Algorithm
DSA - Merge Sort Algorithm
DSA - Shell Sort Algorithm
DSA - Heap Sort
DSA - Bucket Sort Algorithm
DSA - Counting Sort Algorithm
DSA - Radix Sort Algorithm
DSA - Quick Sort Algorithm
Graph Data Structure
DSA - Graph Data Structure
DSA - Depth First Traversal
DSA - Breadth First Traversal
DSA - Spanning Tree
Tree Data Structure
DSA - Tree Data Structure
DSA - Tree Traversal
DSA - Binary Search Tree
DSA - AVL Tree
DSA - Red Black Trees
DSA - B Trees
DSA - B+ Trees
DSA - Splay Trees
DSA - Tries
DSA - Heap Data Structure
Recursion
DSA - Recursion Algorithms
DSA - Tower of Hanoi Using Recursion
DSA - Fibonacci Series Using Recursion
Divide and Conquer
DSA - Divide and Conquer
DSA - Max-Min Problem
DSA - Strassen's Matrix Multiplication
DSA - Karatsuba Algorithm
Greedy Algorithms
DSA - Greedy Algorithms
DSA - Travelling Salesman Problem (Greedy Approach)
DSA - Prim's Minimal Spanning Tree
DSA - Kruskal's Minimal Spanning Tree
DSA - Dijkstra's Shortest Path Algorithm
DSA - Map Colouring Algorithm
DSA - Fractional Knapsack Problem
DSA - Job Sequencing with Deadline
DSA - Optimal Merge Pattern Algorithm
Dynamic Programming
DSA - Dynamic Programming
DSA - Matrix Chain Multiplication
DSA - Floyd Warshall Algorithm
DSA - 0-1 Knapsack Problem
DSA - Longest Common Subsequence Algorithm
DSA - Travelling Salesman Problem (Dynamic Approach)
Approximation Algorithms
DSA - Approximation Algorithms
DSA - Vertex Cover Algorithm
DSA - Set Cover Problem
DSA - Travelling Salesman Problem (Approximation Approach)
Randomized Algorithms
DSA - Randomized Algorithms
DSA - Randomized Quick Sort Algorithm
DSA - Karger’s Minimum Cut Algorithm
DSA - Fisher-Yates Shuffle Algorithm

Data Structures & Algorithms - Stack Algorithm

Share with a Friend

Stack Algorithm

A stack is a linear data structure that operates on the principle of LIFO (Last In, First Out). Elements are added and removed from the top, meaning the last element added is the first one to be removed. Stacks are fundamental in various algorithms and programming tasks.

Key Concepts and Operations:

Push:Adds an element to the top of the stack.
Pop:Removes and returns the element at the top of the stack.
Peek:Returns the element at the top of the stack without removing it.
isEmpty: Checks if the stack is empty.
isFull:(for fixed size stack) returns true if full.

Operation on Stack

PUSH: PUSH operation implies the insertion of a new element into a Stack. A new element is always inserted from the topmost position of the Stack; thus, we always need to check if the top is empty or not, i.e., TOP=Max-1 if this condition goes false, it means the Stack is full, and no more elements can be inserted, and even if we try to insert the element, a Stack overflow message will be displayed.

Algorithm:

Step-1: If TOP = Max-1

Print “Overflow”

Goto Step 4

Step-2: Set TOP= TOP + 1

Step-3: Set Stack[TOP]= ELEMENT

Step-4: END

POP: POP means to delete an element from the Stack. Before deleting an element, make sure to check if the Stack Top is NULL, i.e., TOP=NULL. If this condition goes true, it means the Stack is empty, and no deletion operation can be performed, and even if we try to delete, then the Stack underflow message will be generated.

Algorithm:

Step-1: If TOP= NULL

Print “Underflow”

Goto Step 4

Step-2: Set VAL= Stack[TOP]

Step-3: Set TOP= TOP-1

Step-4: END

PEEK: When we need to return the value of the topmost element of the Stack without deleting it from the Stack, the Peek operation is used. This operation first checks if the Stack is empty, i.e., TOP = NULL; if it is so, then an appropriate message will display, else the value will return.

Algorithm:

Step-1: If TOP = NULL

PRINT “Stack is Empty”

Goto Step 3

Step-2: Return Stack[TOP]

Step-3: END

Stack Implementation in C (Using Array)

C C++ Java Python

#include <stdio.h>
#include <stdlib.h>
#define SIZE 5
 
int stack[SIZE], top = -1;
 
// Push operation
void push(int value) {
    if (top == SIZE - 1) {
        printf("Stack Overflow\n");
    } else {
        stack[++top] = value;
        printf("Inserted %d\n", value);
    }
}
 
// Pop operation
void pop() {
    if (top == -1) {
        printf("Stack Underflow\n");
    } else {
        printf("Deleted %d\n", stack[top--]);
    }
}
 
// Peek operation
void peek() {
    if (top == -1) {
        printf("Stack is empty\n");
    } else {
        printf("Top element is %d\n", stack[top]);
    }
}
 
// Display stack
void display() {
    if (top == -1) {
        printf("Stack is empty\n");
    } else {
        printf("Stack elements:\n");
        for (int i = top; i >= 0; i--) {
            printf("%d\n", stack[i]);
        }
    }
}
 
int main() {
    int choice, value;
    while (1) {
        printf("\n--- Stack Menu ---\n");
        printf("1. Push\n2. Pop\n3. Peek\n4. Display\n5. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);
        switch (choice) {
        case 1:
            printf("Enter the value to push: ");
            scanf("%d", &value);
            push(value);
            break;
        case 2:
            pop();
            break;
        case 3:
            peek();
            break;
        case 4:
            display();
            break;
        case 5:
            exit(0);
        default:
            printf("Invalid choice\n");
        }
    }
    return 0;
}

Output

--- Stack Menu ---

Push
Pop
Peek
Display
Exit


Enter your choice: 1
Enter the value to push: 10
Inserted 10

Enter your choice: 1
Enter the value to push: 20
Inserted 20
 
Enter your choice: 4
Stack elements:
20
10
 
Enter your choice: 2
Deleted 20
 
Enter your choice: 3
Top element is 10

#include <iostream>
#define SIZE 5
using namespace std;
 
class Stack {
    int arr[SIZE];
    int top;
 
public:
    Stack() { top = -1; }
 
    void push(int value) {
        if (top == SIZE - 1)
            cout << "Stack Overflow\n";
        else
            arr[++top] = value, cout << "Inserted " << value << "\n";
    }
 
    void pop() {
        if (top == -1)
            cout << "Stack Underflow\n";
        else
            cout << "Deleted " << arr[top--] << "\n";
    }
 
    void peek() {
        if (top == -1)
            cout << "Stack is empty\n";
        else
            cout << "Top element: " << arr[top] << "\n";
    }
 
    void display() {
        if (top == -1)
            cout << "Stack is empty\n";
        else {
            cout << "Stack elements:\n";
            for (int i = top; i >= 0; i--)
                cout << arr[i] << "\n";
        }
    }
};
 
int main() {
    Stack s;
    int choice, val;
    while (true) {
        cout << "\n1.Push 2.Pop 3.Peek 4.Display 5.Exit\nEnter choice: ";
        cin >> choice;
        switch (choice) {
        case 1:
            cout << "Enter value: ";
            cin >> val;
            s.push(val);
            break;
        case 2:
            s.pop();
            break;
        case 3:
            s.peek();
            break;
        case 4:
            s.display();
            break;
        case 5:
            exit(0);
        default:
            cout << "Invalid choice\n";
        }
    }
    return 0;
}

Output

--- Stack Menu ---

Push
Pop
Peek
Display
Exit


Enter your choice: 1
Enter the value to push: 10
Inserted 10

Enter your choice: 1
Enter the value to push: 20
Inserted 20
 
Enter your choice: 4
Stack elements:
20
10
 
Enter your choice: 2
Deleted 20
 
Enter your choice: 3
Top element is 10

import java.util.Scanner;
 
class Stack {
    int size = 5;
    int[] stack = new int[size];
    int top = -1;
 
    void push(int value) {
        if (top == size - 1)
            System.out.println("Stack Overflow");
        else
            stack[++top] = value;
            System.out.println("Inserted " + value);
    }
 
    void pop() {
        if (top == -1)
            System.out.println("Stack Underflow");
        else
            System.out.println("Deleted " + stack[top--]);
    }
 
    void peek() {
        if (top == -1)
            System.out.println("Stack is empty");
        else
            System.out.println("Top element: " + stack[top]);
    }
 
    void display() {
        if (top == -1)
            System.out.println("Stack is empty");
        else {
            System.out.println("Stack elements:");
            for (int i = top; i >= 0; i--)
                System.out.println(stack[i]);
        }
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Stack s = new Stack();
        while (true) {
            System.out.println("\n1.Push 2.Pop 3.Peek 4.Display 5.Exit");
            System.out.print("Enter your choice: ");
            int ch = sc.nextInt();
            switch (ch) {
                case 1:
                    System.out.print("Enter value: ");
                    s.push(sc.nextInt());
                    break;
                case 2:
                    s.pop();
                    break;
                case 3:
                    s.peek();
                    break;
                case 4:
                    s.display();
                    break;
                case 5:
                    System.exit(0);
                default:
                    System.out.println("Invalid choice");
            }
        }
    }
}

Output

--- Stack Menu ---

Push
Pop
Peek
Display
Exit


Enter your choice: 1
Enter the value to push: 10
Inserted 10

Enter your choice: 1
Enter the value to push: 20
Inserted 20
 
Enter your choice: 4
Stack elements:
20
10
 
Enter your choice: 2
Deleted 20
 
Enter your choice: 3
Top element is 10

stack = []
 
def push():
    val = int(input("Enter value to push: "))
    stack.append(val)
    print(f"Inserted {val}")
 
def pop():
    if not stack:
        print("Stack Underflow")
    else:
        print(f"Deleted {stack.pop()}")
 
def peek():
    if not stack:
        print("Stack is empty")
    else:
        print("Top element:", stack[-1])
 
def display():
    if not stack:
        print("Stack is empty")
    else:
        print("Stack elements:", list(reversed(stack)))
 
while True:
    print("\n1.Push 2.Pop 3.Peek 4.Display 5.Exit")
    choice = int(input("Enter choice: "))
    if choice == 1:
        push()
    elif choice == 2:
        pop()
    elif choice == 3:
        peek()
    elif choice == 4:
        display()
    elif choice == 5:
        break
    else:
        print("Invalid choice")

Output

--- Stack Menu ---

Push
Pop
Peek
Display
Exit


Enter your choice: 1
Enter the value to push: 10
Inserted 10

Enter your choice: 1
Enter the value to push: 20
Inserted 20
 
Enter your choice: 4
Stack elements:
20
10
 
Enter your choice: 2
Deleted 20
 
Enter your choice: 3
Top element is 10

Stack Implementation in C (Using Linked List)

C C++ Java Python

#include <stdio.h>
#include <stdlib.h>
 
struct Node {
    int data;
    struct Node* next;
};
 
struct Node* top = NULL;
 
void push(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = top;
    top = newNode;
    printf("Pushed %d\n", value);
}
 
void pop() {
    if (top == NULL) {
        printf("Stack Underflow\n");
        return;
    }
    printf("Popped %d\n", top->data);
    struct Node* temp = top;
    top = top->next;
    free(temp);
}
 
void peek() {
    if (top == NULL)
        printf("Stack is empty\n");
    else
        printf("Top element: %d\n", top->data);
}
 
void display() {
    struct Node* temp = top;
    if (temp == NULL) {
        printf("Stack is empty\n");
        return;
    }
    printf("Stack elements:\n");
    while (temp) {
        printf("%d\n", temp->data);
        temp = temp->next;
    }
}
 
int main() {
    int choice, value;
    while (1) {
        printf("\n1.Push 2.Pop 3.Peek 4.Display 5.Exit\nEnter choice: ");
        scanf("%d", &choice);
        switch (choice) {
            case 1:
                printf("Enter value: ");
                scanf("%d", &value);
                push(value);
                break;
            case 2: pop(); break;
            case 3: peek(); break;
            case 4: display(); break;
            case 5: exit(0);
            default: printf("Invalid choice\n");
        }
    }
    return 0;
}

Output

--- Stack Menu ---

Push
Pop
Peek
Display
Exit


Enter your choice: 1
Enter the value to push: 10
Inserted 10

Enter your choice: 1
Enter the value to push: 20
Inserted 20
 
Enter your choice: 4
Stack elements:
20
10
 
Enter your choice: 2
Deleted 20
 
Enter your choice: 3
Top element is 10

#include <iostream>
using namespace std;
 
struct Node {
    int data;
    Node* next;
};
 
class Stack {
    Node* top;
 
public:
    Stack() { top = nullptr; }
 
    void push(int val) {
        Node* newNode = new Node();
        newNode->data = val;
        newNode->next = top;
        top = newNode;
        cout << "Pushed " << val << endl;
    }
 
    void pop() {
        if (!top) {
            cout << "Stack Underflow\n";
            return;
        }
        cout << "Popped " << top->data << endl;
        Node* temp = top;
        top = top->next;
        delete temp;
    }
 
    void peek() {
        if (!top)
            cout << "Stack is empty\n";
        else
            cout << "Top element: " << top->data << endl;
    }
 
    void display() {
        Node* temp = top;
        if (!temp) {
            cout << "Stack is empty\n";
            return;
        }
        cout << "Stack elements:\n";
        while (temp) {
            cout << temp->data << "\n";
            temp = temp->next;
        }
    }
};
 
int main() {
    Stack s;
    int choice, val;
    while (1) {
        cout << "\n1.Push 2.Pop 3.Peek 4.Display 5.Exit\nEnter choice: ";
        cin >> choice;
        switch (choice) {
            case 1:
                cout << "Enter value: ";
                cin >> val;
                s.push(val);
                break;
            case 2: s.pop(); break;
            case 3: s.peek(); break;
            case 4: s.display(); break;
            case 5: exit(0);
            default: cout << "Invalid choice\n";
        }
    }
    return 0;
}

Output

--- Stack Menu ---

Push
Pop
Peek
Display
Exit


Enter your choice: 1
Enter the value to push: 10
Inserted 10

Enter your choice: 1
Enter the value to push: 20
Inserted 20
 
Enter your choice: 4
Stack elements:
20
10
 
Enter your choice: 2
Deleted 20
 
Enter your choice: 3
Top element is 10

import java.util.Scanner;
 
class Node {
    int data;
    Node next;
}
 
class Stack {
    Node top = null;
 
    void push(int val) {
        Node newNode = new Node();
        newNode.data = val;
        newNode.next = top;
        top = newNode;
        System.out.println("Pushed " + val);
    }
 
    void pop() {
        if (top == null)
            System.out.println("Stack Underflow");
        else {
            System.out.println("Popped " + top.data);
            top = top.next;
        }
    }
 
    void peek() {
        if (top == null)
            System.out.println("Stack is empty");
        else
            System.out.println("Top element: " + top.data);
    }
 
    void display() {
        Node temp = top;
        if (temp == null) {
            System.out.println("Stack is empty");
            return;
        }
        System.out.println("Stack elements:");
        while (temp != null) {
            System.out.println(temp.data);
            temp = temp.next;
        }
    }
}
 
public class StackLinkedList {
    public static void main(String[] args) {
        Stack s = new Stack();
        Scanner sc = new Scanner(System.in);
        int ch;
        while (true) {
            System.out.println("\n1.Push 2.Pop 3.Peek 4.Display 5.Exit");
            System.out.print("Enter choice: ");
            ch = sc.nextInt();
            switch (ch) {
                case 1:
                    System.out.print("Enter value: ");
                    s.push(sc.nextInt());
                    break;
                case 2: s.pop(); break;
                case 3: s.peek(); break;
                case 4: s.display(); break;
                case 5: System.exit(0);
                default: System.out.println("Invalid choice");
            }
        }
    }
}

Output

--- Stack Menu ---

Push
Pop
Peek
Display
Exit


Enter your choice: 1
Enter the value to push: 10
Inserted 10

Enter your choice: 1
Enter the value to push: 20
Inserted 20
 
Enter your choice: 4
Stack elements:
20
10
 
Enter your choice: 2
Deleted 20
 
Enter your choice: 3
Top element is 10

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
class Stack:
    def __init__(self):
        self.top = None
 
    def push(self, value):
        new_node = Node(value)
        new_node.next = self.top
        self.top = new_node
        print(f"Pushed {value}")
 
    def pop(self):
        if not self.top:
            print("Stack Underflow")
        else:
            print(f"Popped {self.top.data}")
            self.top = self.top.next
 
    def peek(self):
        if not self.top:
            print("Stack is empty")
        else:
            print(f"Top element: {self.top.data}")
 
    def display(self):
        if not self.top:
            print("Stack is empty")
            return
        temp = self.top
        print("Stack elements:")
        while temp:
            print(temp.data)
            temp = temp.next
 
stack = Stack()
while True:
    print("\n1.Push 2.Pop 3.Peek 4.Display 5.Exit")
    ch = int(input("Enter choice: "))
    if ch == 1:
        val = int(input("Enter value: "))
        stack.push(val)
    elif ch == 2:
        stack.pop()
    elif ch == 3:
        stack.peek()
    elif ch == 4:
        stack.display()
    elif ch == 5:
        break
    else:
        print("Invalid choice")

Output

--- Stack Menu ---

Push
Pop
Peek
Display
Exit


Enter your choice: 1
Enter the value to push: 10
Inserted 10

Enter your choice: 1
Enter the value to push: 20
Inserted 20
 
Enter your choice: 4
Stack elements:
20
10
 
Enter your choice: 2
Deleted 20
 
Enter your choice: 3
Top element is 10

Real-World Applications of Stack

Application Area	Use of Stack
Web Browsers	Backtracking visited URLs (Back button history)
Programming Languages	Function call management (call stack)
Expression Evaluation	Infix to Postfix, Postfix evaluation
Undo Feature	Undo in text editors or apps
Compilers	Syntax parsing using stacks
Operating Systems	Memory management, recursion stack
Balancing Symbols	Checking for balanced parentheses ()[]{}
Reversing Items	Reverse strings or arrays

✅ Stack Implementation Code in Different Languages

We'll use a Linked List-based stack for better flexibility (dynamic size).

C C++ Java Python

/*
* C Program: Stack + Example Use (Reverse String)
*/

 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
struct Node {
    char data;
    struct Node* next;
};
 
struct Node* top = NULL;
 
void push(char c) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = c;
    newNode->next = top;
    top = newNode;
}
 
char pop() {
    if (top == NULL) return '\0';
    char c = top->data;
    struct Node* temp = top;
    top = top->next;
    free(temp);
    return c;
}
 
void reverseString(char* str) {
    for (int i = 0; str[i]; i++)
        push(str[i]);
 
    for (int i = 0; str[i]; i++)
        str[i] = pop();
}
 
int main() {
    char str[100];
    printf("Enter a string: ");
    gets(str);
 
    reverseString(str);
    printf("Reversed string: %s\n", str);
 
    return 0;
}

Output

Input:

Enter a string: hello

Output:

Reversed string: olleh

// C++ Program: Stack + Use Case (Balanced Parentheses)
 
#include <iostream>
#include <stack>
using namespace std;
 
bool isBalanced(string expr) {
    stack<char> s;
    for (char ch : expr) {
        if (ch == '(' || ch == '{' || ch == '[')
            s.push(ch);
        else if (ch == ')' && !s.empty() && s.top() == '(')
            s.pop();
        else if (ch == '}' && !s.empty() && s.top() == '{')
            s.pop();
        else if (ch == ']' && !s.empty() && s.top() == '[')
            s.pop();
        else
            return false;
    }
    return s.empty();
}
 
int main() {
    string expr;
    cout << "Enter expression: ";
    cin >> expr;
 
    if (isBalanced(expr))
        cout << "Balanced\n";
    else
        cout << "Not Balanced\n";
 
    return 0;
}

Output

Input:
    Enter expression: {[(a+b)*(c-d)]}
Output:    
Balanced
Input:
Enter expression: (a+b]*c)
Output:
Not Balanced

//Java Program: Stack + Use Case (Backspace Editor Simulation)
import java.util.Stack;
import java.util.Scanner;
 
public class StackApplication {
    public static String simulateTyping(String input) {
        Stack<Character> stack = new Stack<>();
        for (char ch : input.toCharArray()) {
            if (ch != '#')
                stack.push(ch);
            else if (!stack.isEmpty())
                stack.pop();
        }
 
        StringBuilder result = new StringBuilder();
        for (char ch : stack)
            result.append(ch);
 
        return result.toString();
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Type text (use '#' for backspace): ");
        String input = sc.nextLine();
 
        System.out.println("Result: " + simulateTyping(input));
    }
}

Output

Input:
    Type text (use '#' for backspace): ab#c#de##
    Output:
Result: d
 
Explanation:

a → stack: [a]
b → [a, b]
# → pop b → [a]
c → [a, c]
# → pop c → [a]
d → [a, d]
e → [a, d, e]
# → pop e → [a, d]
# → pop d → [a]
 Result: "a"

 # Python Program: Stack + Use Case (Infix to Postfix Conversion)
 
def precedence(op):
    if op in ('+', '-'): return 1
    if op in ('*', '/'): return 2
    return 0
 
def infix_to_postfix(expr):
    result = []
    stack = []
 
    for char in expr:
        if char.isalnum():
            result.append(char)
        elif char == '(':
            stack.append(char)
        elif char == ')':
            while stack and stack[-1] != '(':
                result.append(stack.pop())
            stack.pop()
        else:
            while stack and precedence(char) <= precedence(stack[-1]):
                result.append(stack.pop())
            stack.append(char)
 
    while stack:
        result.append(stack.pop())
    return ''.join(result)
 
expr = input("Enter infix expression: ")
print("Postfix expression:", infix_to_postfix(expr))

Output

Input:

Enter infix expression: (a+b)*c

Output:

Postfix expression: ab+c*

Input:

Enter infix expression: a+b*c

Output:

Postfix expression: abc*+