Java program to find the top and bottom elements of a given stack

This tutorial will explain how to use Java to find the top and bottom elements of a given stack.

The

Stack represents a linear dataset that follows the Last in First Out (LIFO) principle, so elements are added and removed at the same location. We will further explore two ways to find the top and bottom elements of a given stack, i.e. iterate over and recursively .

Problem Statement

We will get a stack array containing n elements, and the task is to find the 1st and nth elements of the stack without destroying it in any way. Therefore, we need to use the

iterative methods and the recursive methods in our custom stack to ensure that the original stack remains unchanged.

Enter 1

<code>stack = [5, 10, 15, 20, 25, 30]</code>

Output 1

<code>堆栈中的顶部元素是 --> 30
堆栈中的底部元素是 --> 5</code>

Enter 2

<code>stack = [1000, 2000, 3000, 4000, 5000]</code>

Output 2

<code>堆栈元素：5000 4000 3000 2000 1000
底部元素：1000
顶部元素：5000</code>

Iteration method to find top and bottom elements

For the first method, we will define an array used as the stack and then define the stack operation to retrieve the desired element by the iterative method. Here are the steps to find the top and bottom elements of a given stack:

Initialize the stack with a
• maxSize value equal to 6 and set top to -1 (represents an empty array) . Press elements 5, 10, 15, 20, 25, and 30 onto the stack by push() operation, while increasing the top value in stackArray[top]
.
• Check whether the stack is empty. Then use peek()
to find the top element by returning stackArray[top], because top is already set to the last element in the array.
• Finally, use the bottom() function
to find the bottom element, which returns the value of stackArray[0], that is, the first and bottommost element in the stack array.
• Output the final top and bottom values.
• Example

The following is a Java program that uses iterative methods to find the top and bottom elements of a given stack:

Output

class MyStack {
    private int maxSize;
    private int[] stackArray;
    private int top;
    // 使用MyStack构造函数初始化堆栈
    public MyStack(int size) {
        this.maxSize = size;
        this.stackArray = new int[maxSize];

        // 将Top变量初始化为-1，表示空堆栈
        this.top = -1;
    }
    // 将元素添加到stackArray中
    public void push(int value) {
        if (top < maxSize -1) {
            stackArray[++top] = value;
        } else {
            System.out.println("堆栈已满");
        }
    }
    // 使用peek()查找顶部元素
    public int peek() {
        if (top >= 0) {
            return stackArray[top];
        } else {
            System.out.println("堆栈为空。");
            return -1;
        }
    }
    // 使用bottom()查找堆栈数组中的底部元素（第一个添加的值）
    public int bottom() {
        if (top >= 0) {
            return stackArray[0];
        } else {
            System.out.println("堆栈为空。");
            return -1;
        }
    }
}
public class Main {
    public static void main(String[] args) {
        MyStack stack = new MyStack(6); // 创建大小为6的堆栈
        // 将元素压入堆栈
        stack.push(5);
        stack.push(10);
        stack.push(15);
        stack.push(20);
        stack.push(25);
        stack.push(30);
        // 检索顶部和底部元素
        int topElement = stack.peek();
        int bottomElement = stack.bottom();
        // 打印最终输出
        System.out.println("堆栈中的顶部元素是 --> " + topElement);
        System.out.println("堆栈中的底部元素是 --> " + bottomElement);
    }
}

Time Complexity:

<code>堆栈中的顶部元素是 --> 30
堆栈中的底部元素是 --> 5</code>

O(n) during stack formation (pressure), because each element is added to the end of the array, and the index is incremented by 1 each time until the size n. O(1) during peek and bottom operations, because it returns stackArray[top] and stackArray[0].

Space complexity:

O(n), because we fix maxSize to store n elements, proportional to the size of the stack.

Recursive method to find top and bottom elements

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

• Initialize the stack with maxSize which is equal to 5 and top set to -1.
• Check whether the stack size does not exceed maxSize. Use the push() function to push each integer value on the stack, increment top by 1 and store the value in stackArray[top].
• Use the recursive method to find the bottom element and set the current index to the top value. Then, if the index is 0, then stackArray[0] (bottom element), otherwise the function is called recursively with an index decrementing by 1.
• Find the top element with an index set to 0. In the basic case, if the current index is equal to the top value, then stackArray[top] is returned. Otherwise, the function is called recursively using an index incremented by 1.
• Recursively prints all elements in stackArray[], the basic case is that if the index is less than 0, then the recursion is stopped. Otherwise, call the function and print the integer value recursively with an index decremented by 1.
• Call the main function and print the top and bottom elements as well as the entire stack.

Example

The following is a Java program that uses a recursive method to find the top and bottom elements of a given stack:

<code>stack = [5, 10, 15, 20, 25, 30]</code>

Output

<code>堆栈中的顶部元素是 --> 30
堆栈中的底部元素是 --> 5</code>

Time Complexity: Total is O(n), because an element spends O(1) in the push() operation during stack formation of size n. In the worst case, recursive operations cost O(n).

Spatial complexity: Due to the recursive call stack, recursively is O(n). The array itself also uses O(n) to store n elements.

Conclusion

In short, both methods are applicable to their respective cases, where the direct array method provides constant time access to stack elements and its simple interactive implementation. On the other hand, recursive methods provide a recursive perspective on stack operations, making them more general and emphasizing algorithmic methods. Understanding these two methods gives you the basics of the stack and when to use either method.

The above is the detailed content of Java program to find the top and bottom elements of a given stack. For more information, please follow other related articles on the PHP Chinese website!