Find Top and Bottom Elements of a Given Stack in Java

In this tutorial, we will be looking at how to find the top and the bottom elements in a given stack using Java.
When we look at the stack, it represents a linear dataset following the Last In, First Out (LIFO) principle, hence the elements are added and removed in the same place. We will further explore two approaches for finding a given stack's top and bottom elements, i.e. via iteration and recursion.

Problem Statement

We will be given a stack array of n elements and the task is to find the 1st and nth element of the stack without disrupting it in any way. Therefore we need to perform the peek() operation using both iterative approach and recursion in a custom stack, ensuring the original stack stays intact.

Input 1

stack = [5, 10, 15, 20, 25, 30]

Output 1

The Top element in the stack is --> 30
The Bottom element in the stack is --> 5

Input 2

stack = [1000, 2000, 3000, 4000, 5000]

Output 2

Stack Elements: 5000 4000 3000 2000 1000
Bottom Element: 1000
Top Element: 5000

Iterative Method for Finding Top and Bottom Elements

For the first approach, we will define an array which is used to hold elements as a stack and then define stack operations to retrieve the required elements through the iterative method. Following are the steps to find the top and bottom elements of a given stack ?

• Initializing the stack stackArray[] using maxSize value equal to 6 (holds max 6 elements in stack array) and setting the top = -1 (represents empty array).
• Push the elements 5, 10, 15, 20, 25 and 30 onto the stack through the push() operation, along with incrementing the top value in stackArray[top].
• Check if the stack is empty. Then use the peek() to find the top element by returning stackArray[top], as the top is already set to the last element in the array.
• At last find the bottom element using the bottom() function, which returns the value of stackArray[0], the first and the bottommost element in the stack array.
• Outputs the final top and bottom values.

Example

Below is the Java program to find the top and bottom elements of a given stack using iterative method ?

class MyStack {
    private int maxSize;
    private int[] stackArray;
    private int top;
    // Initialized stack using the MyStack constructor
    public MyStack(int size) {
        this.maxSize = size;
        this.stackArray = new int[maxSize];
        
        //initializing Top variable to -1 representing empty stack
        this.top = -1;
    }
    // Adding elements into the stackArray
    public void push(int value) {
        if (top < maxSize - 1) {
            stackArray[++top] = value;
        } else {
            System.out.println("Stack is full. Cannot push element.");
        }
    }
    // Finding the top element (recently added value) in the stack using peek()
    public int peek() {
        if (top >= 0) {
            return stackArray[top];
        } else {
            System.out.println("Stack is empty.");
            return -1;
        }
    }
    // Finding bottom element (fist added value) in stack array using bottom()
    public int bottom() {
        if (top >= 0) {
            return stackArray[0];
        } else {
            System.out.println("Stack is empty.");
            return -1;
        }
    }
}
public class Main {
    public static void main(String[] args) {
        MyStack stack = new MyStack(6); // Create stack of size 6
        // Pushing elements to stack
        stack.push(5);
        stack.push(10);
        stack.push(15);
        stack.push(20);
        stack.push(25);
        stack.push(30);
        // Retriving top and bottom elements
        int topElement = stack.peek();
        int bottomElement = stack.bottom();
        // Print final output
        System.out.println("The Top element in the stack is --> " + topElement);
        System.out.println("The Bottom element in the stack is --> " + bottomElement);
    }
}

Output

The top Element in the stack is --> 30
The bottom Element in the stack is --> 5

Time Complexity: O(n) during the Stack Formation (Push) as each element is added at the end of the array and index increments increase by 1 up to size n. O(1) during the peek and bottom operations as it returns stackArray[top] and stackArray[0].

Space Complexity: O(n), as we fix masSize to store n elements, proportional to the size of the stack.

Recursive Method for Finding Top and Bottom Elements

In this approach, we will be using recursion to find the top and bottom elements in the stack. The stack is initialized and formed using the push() operation and recursively extracting the required elements. Following are the steps to find the top and bottom elements of a given stack ?

• Initialize the stack with maxSize equal to 5 and top set to -1 initially.
  
• Checking if the stack size does not exceed maxSize. Push each integer value into the stack using push() function, incrementing the top by 1 and storing the value in stackArray[top].
  
• Find the bottom element using the recursive approach, setting the current index equal to the top value. Then if the index is 0, return stackArray[0] (bottom element), otherwise recursively call the function with index decremented by 1.
  
• Find the top element with the index set to 0. In the base case return stackArray[top] if the current index equals top value. Otherwise, recursively call the function with an index incremented by 1.
  
• Print all the elements in the stackArray[] recursively, with the base case if the index is less than 0 then stop the recursion. Else call the function and recursively print the integer values with the index decremented by 1.
  
• Call the main function and print the top and bottom elements along with the whole stack.

Example

Below is the Java program to find the top and bottom elements of a given stack using recursive method ?

class MyStack {
    private int maxSize;
    private int[] stackArray;
    private int top;
    // Initialize stack using constructor
    public MyStack(int size) {
        this.maxSize = size;
        this.stackArray = new int[maxSize];
        this.top = -1; // Top set to -1 as its empty
    }
    // Iterative push to form the stack
    public void push(int value) {
        if (top < maxSize - 1) {
            stackArray[++top] = value;
        } else {
            System.out.println("Stack is full. Cannot push element.");
        }
    }

    // Recursive method to get the bottom element
    public int BottomRecursive(int index) {
       // Base case: When we reach the bottom of the stack (index 0), we return the bottom element
        if (index == 0) {
            return stackArray[0];
        }
        // Recursive case: If not bottom element, move towards the bottom of the stack
        return BottomRecursive(index - 1);
    }
    // Recursive method to get the top element
    public int TopRecursive(int index) {
        // Base case: if the index equals top, we have reached the top
        if (index == top) {
            return stackArray[top];
        }
        // Recursive case: move towards the top
        return TopRecursive(index + 1);
    }
    // Recursive method to print elements (for visualization)
    public void printStackRecursive(int index) {
        // Base case: stop when the index is less than 0
        if (index < 0) {
            return; 
        }
        // Recursive case: keep printing the element at the current index and move down
        System.out.print(stackArray[index] + " ");
        printStackRecursive(index - 1);
    }
    public int getTop() {
        return top;
    }
}
public class Main {
    public static void main(String[] args) {
        MyStack stack = new MyStack(5); // Create a stack of size 5
        // Pushing elements to stack
        stack.push(1000);
        stack.push(2000);
        stack.push(3000);
        stack.push(4000);
        stack.push(5000);
        // Print the stack elements
        System.out.print("Stack Elements: ");
        stack.printStackRecursive(stack.getTop());
        System.out.println();
        // Get the bottom element recursively
        int bottomElement = stack.BottomRecursive(stack.getTop());
        System.out.println("Bottom Element: " + bottomElement);
        // Get the top element recursively
        int topElement = stack.TopRecursive(0);
        System.out.println("Top Element: " + topElement);
    }
}

Output

Stack Elements: 6000 5000 4000 3000 2000 1000 
Bottom Element: 1000
Top Element: 6000

Time Complexity: O(n) overall as during the Stack Formation of size n, one element takes O(1) in push() operation. Recursive operations take O(n) in the worst case.
Space Complexity: O(n), for recursion due to the recursive call stack. The array also uses O(n) itself to store n elements.

Conclusion

In conclusion, both approaches are suitable in respective cases, where the direct array approach offers constant-time access to the stack elements and its straightforward interaction to implement. On the other hand, the recursive approach provides a recursive perspective on stack operations, making it more generalized and emphasizing an algorithmic approach. Understanding both these methods equips you with the fundamentals of the stack and the knowledge of when to use any of the approaches.