Stack Data Structure in Java

A stack is a linear data structure follows a particular order to perform the operations on it.

Stack data structure follows LIFO (Last In First Out) means element inserted into Stack last will be removed first from the stack.

A realtime example is a Stack of Books which stacks over on another.

The book which is pushed into a stack of books last will be removed first because it is not possible to remove the other book from the stack except the top one.

There are mainly 3 operations performed in Stack:

1. push():  This method is used to add/insert an element into a stack. if Stack is full then it returns Stack Overflow Message.
2. pop(): This method is used to remove the element from the stack. In Stack, the element always removed from the top. If Stack is empty then it returns Stack Underflow message.
3. peek (): This method always returns the top element from the stack.
4. isEmpty(): This method returns true when Stack is empty otherwise returns false.

Applications of Stack:

• Expression Parsing ie; Conversion of Infix to Prefix/Postfix.
• Parentheses Checking
• UNDO-REDO Functionality in Text editors.

Push Operation in Stack:

To demonstrate the push operation, Here we are taking an array of Character with {A, B, C, D, E, F} we are going to push each element one by one into the stack and see what’s happening:

Step 1: In the Starting the Stack is empty and we have 5 elements to insert into the stack.

Step 2:  element A inserted into the Stack and removed from the array.

Step 3: same as A all the element inserted into Stack.

The size of Stack is the same as the size of array we are inserted into the stack and after all, element inserted. if we want to insert on the extra element. then Stack generates an error message ie; Stack Overflow.

Peek Operation in Stack:

peek() method always return the top element of the stack. In this example, if we call the peek() method then it will return the “F”  because “F”  is the current top element of the stack.

Pop operation in Stack:

In pop() operation the element on the top of the stack removed.

Step 1: when we apply pop() operation in the above stack then it removes the top element from the stack.

Step 2: Same applying the pop() operation in the stack will remove all the element from the stack.

All the elements are removed from the Stack, if we again apply the pop() method in Stack then it will return an error Message ” Stack Underflow” means there are no elements in the stack.

Time Complexities of Stack Operations:

Access:  O(n)

Search:   O(n)

Insertion:  O(1)

Deletion: O (1)

We can implement Stack in two ways:

• Array Implementation of Stack
• LinkedList Implementation of Stack

Stack Implementation using LinkedList in Java:

There are 2 classes 1st is the Stack.java that have all the implementations for Stack that is used in the main class.

Stack.class:

public class Stack {

    int data;
    Stack next;

    public Stack() {
    }

    public Stack(int data) {
        this.data = data;
        this.next = null;
    }


    public Stack push(Stack top, int ele) {
        Stack s = new Stack(ele);
        if (top == null) {
            top = s;
        } else {
            s.next = top;
            top = s;
        }
        return top;
    }

    public Stack pop(Stack top){
        if (top == null){
            System.out.println("Stack is Empty.");
        }else{
            Stack temp = top;
            top = top.next;
            temp.next = null;
            System.out.println(String.format("%d removed from Stack.",temp.data));
        }
        return top;
    }

    public void display(Stack top){
        if (top == null){
            System.out.println("Stack is Empty.");
        }else{
            Stack temp = top;
            while(temp.next!= null){
                System.out.print(String.format("%d --->",temp.data));
                temp = temp.next;
            }
            System.out.print(String.format("%d--->NULL",temp.data));
        }
        System.out.println();
    }

    public int stackSize(Stack top){
        int count = 0;
        Stack temp = top;
        if (temp == null){
            return count;
        }else{
            while (temp.next != null){
                ++count;
                temp = temp.next;
            }
            count++;
        }
        return count;
    }

}

StackImplementation.java:

import java.util.Scanner;

public class StackImplementation {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        System.out.println("Enter the Size of Stack : ");
        int n = scanner.nextInt();

        System.out.println("=================================");

        Stack s = new Stack();

        Stack top = null;

        System.out.println("Enter the stack Elements : ");

        for (int i=0;i<n;i++){
            int ele = scanner.nextInt();
            top = s.push(top,ele);
        }

        System.out.println("=================================");

        System.out.println("Stack after Inserting the elements : ");
        s.display(top);

        System.out.println("=================================");

        System.out.println("Stack Size after inserting the elements : ");
        System.out.print(s.stackSize(top));

        System.out.println();

        System.out.println("=================================");


        System.out.println("After applying the pop() operation :");
        top = s.pop(top);

        System.out.println("=================================");

        System.out.println("Stack after 1st pop() operation performed : ");
        s.display(top);

        System.out.println("=================================");

        System.out.println("Stack Size after 1st pop() : ");
        System.out.print(s.stackSize(top));

        System.out.println("=================================");

    }
}

Output 1:

Enter the Size of Stack : 
6
=================================
Enter the stack Elements : 
2
6
8
5
3
4
=================================
Stack after Inserting the elements : 
4 --->3 --->5 --->8 --->6 --->2--->NULL
=================================
Stack Size after inserting the elements : 
6
=================================
After applying the pop() operation :
4 removed from Stack.
=================================
Stack after 1st pop() operation performed : 
3 --->5 --->8 --->6 --->2--->NULL
=================================
Stack Size after 1st pop() : 
5
=================================

Output 2:

Enter the Size of Stack : 
1
=================================
Enter the stack Elements : 
5
=================================
Stack after Inserting the elements : 
5--->NULL
=================================
Stack Size after inserting the elements : 
1
=================================
After applying the pop() operation :
5 removed from Stack.
=================================
Stack after 1st pop() operation performed : 
Stack is Empty.

=================================
Stack Size after 1st pop() : 
0
=================================

Hope you like this post.

If you have any doubt please feel free to comment below.

Please share the Post and follow newsletter for more post.

You may also learn these to build the Knowledge:

• Array in Java
• Array length in Java
• Linear Search in Java
• Christmas Tree Pattern Program
• Memory Management in Java
• Pattern Programs in Java
• Check number is Even or Odd without using modulus operator?