Java Program to Implement Stack Data Structure

Java Program to Implement the Queue Data Structure

Stack is the fundamental Data Structure that can follow the Last In, First Out(LIFO) principle. It can work that the last element added to the stack will be the first one to be removed. It can operate like a stack of plates: We can only add or remove the topmost plate at any given time. The simplicity and efficiency of the stack make them crucial in various computer science applications.

In this article, we will learn about Stack Data Structure and How to Implement it in Java.

Stack Data Structure in Java

The Stack can be visualized as the collection of elements arranged one on top of the other. It can typically support the two primary operations are pushing(adding) the elements onto the stack and popping(removing) elements from the stack.

Implementation of Stack:

Stack can be implemented using the various underlying the data structures such as the arrays or linked lists.

Operations in Stack

There are only few counted operations can be performed in Stack Data Structure in Java as mentioned below:

push() : Method to push element in the Stack
pop() : Method to pop element from the Stack
top() : Returns the Top element from the Stack
isEmpty() : The isEmpty operation can used to check whether the stack is empty or not.
isFull() : The isFull Operation can be used to check whether the stack is full or not.

Algorithm for the Operations

Operation	Algorithm	Complexity
1. Push Operation	Check if stack is full using isFull() method. If stack is full then print an error message(“Stack Overflow”) and return. Increment the ‘top’ to move to next empty position in the stack. Insert the new element value into stackArray. Print the message indicating the element has been pushed onto the stack.	Time Complexity: O(1) Space Complexity: O(1)
2. Pop Operation	Check whether if the stack is empty using isEmpty() method. If stack is empty, print the error message (“Stack underflow”) and return -1. Retrieve the top element from the stackArray. Decremen the top to remove the top element from stack. Return the popped element in stack.	Time Complexity: O(1) Space Complexity: O(1)
3. Peek Operation	Check If stack is empty using isEmpty() method. If stack is empty,print the error message(“Stack is empty”) and return -1. Return the top element from stackArray without removing it.	Time Complexity: O(1) Space Complexity: O(1)
4. IsEmpty Operation	It returns true if stack is empty that indicates top variable is -1 that means no elements in stack, otherwise false.	Time Complexity: O(1) Space Complexity: O(1)
5. isFull Operation	It can returns true if stack is full i..e if top variable has reached the maximum capacity of stack(maxSize-1). Other =wise it returns false.	Time Complexity: O(1) Space Complexity: O(1)

Step by Step Implementation of Stack Data Structure

Define the class for the Stack
We can declare the necessary instance variables such as the size of stack, an array can store the elements and the variable to track the top of element of the stack.
Implement the constructor to initialize the stack with the given size.
Implement the methods to perform the stack operations such as push, pop, peek, isEmpty and isFull.
Write the algorithms for the each operation and taking care to handle the edge cases such as overflow or underflow.
Print the results of the operation based on the requirements of the stack.

Program to Implement Stack Structure in Java

Below is the implementation of Stack Structure in Java:

Java

public class StackExample {
    private int maxSize;
    private int[] stackArray;
    private int top;

    public StackExample(int size) {
        maxSize = size;
        stackArray = new int[maxSize];
        top = -1;
    }

    // Method to push an element onto the stack
    public void push(int value) {
        if (top == maxSize - 1) {
            System.out.println("Stack overflow");
            return;
        }
        stackArray[++top] = value;
        System.out.println(value + " pushed into the stack");
    }

    // Method to pop an element from the stack
    public int pop() {
        if (top == -1) {
            System.out.println("Stack underflow");
            return -1;
        }
        int poppedElement = stackArray[top--];
        System.out.println(poppedElement + " popped from the stack");
        return poppedElement;
    }

    // Method to peek the top element of the stack
    public int top() {
        if (top == -1) {
            System.out.println("Stack is empty");
            return -1;
        }
        return stackArray[top];
    }

    // Method to check if the stack is empty
    public boolean isEmpty() {
        return (top == -1);
    }

    public static void main(String[] args) {
        StackExample stack = new StackExample(5); // Creating a stack of size 5

        // Pushing elements onto the stack
        stack.push(10);
        stack.push(20);

        // Peeking the top element
        System.out.println("Top element of the stack: " + stack.top());

        // Popping elements from the stack
        stack.pop();
        stack.pop();
        stack.pop(); // Trying to pop from an empty stack

        // Checking if the stack is empty
        System.out.println("Is stack empty? " + stack.isEmpty());
    }
}

Output

10 pushed into the stack
20 pushed into the stack
Top element of the stack: 20
20 popped from the stack
10 popped from the stack
Stack underflow
Is stack empty? true

Time and Space Complexity:

The time complexity of the stack operations such as push, pop, peek, isEmpty and isFull and it can implemented using array is O(1).
The Space Complexity of the array based implementation is O(n) where n is the maximum size of the stack.

Applications of Stack

It can applies in expression evaluation and syntax parsing
Stack can be used in function call management in programming languages
It can be used in backtracking algorithms
This can applies in Undo mechanisms in text editors and software applications
This can used in memory management in recursive algorithms

Click Here to Learn more about Stack Data Structure

Conclusion

The stack data structure is versatile and efficient tool used in the various computer science applications. Its simplicity along with the constant time complexity for basic operations. Makes it an the essential concept for the understanding data structures and algorithms.

Tags:

#Java-DSA #Java-Stack #Java #Java