Java程序以查找给定堆栈的顶部和底部元素

本教程将介绍如何使用Java查找给定堆栈的顶部和底部元素。

堆栈代表遵循后进先出(LIFO)原则的线性数据集，因此元素在同一位置添加和删除。我们将进一步探讨两种查找给定堆栈的顶部和底部元素的方法，即通过迭代和递归。

问题陈述

我们将得到一个包含n个元素的堆栈数组，任务是在不以任何方式破坏它的前提下找到堆栈的第1个和第n个元素。因此，我们需要在自定义堆栈中使用迭代方法和递归方法执行peek()操作，确保原始堆栈保持不变。

输入1

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

输出1

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

输入2

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

输出2

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

迭代方法查找顶部和底部元素

对于第一种方法，我们将定义一个用作堆栈的数组，然后定义堆栈操作以通过迭代方法检索所需元素。以下是查找给定堆栈的顶部和底部元素的步骤：

• 使用等于6的maxSize值初始化堆栈stackArray[]（在堆栈数组中最多容纳6个元素），并将top设置为-1（表示空数组）。
• 通过push()操作将元素5、10、15、20、25和30压入堆栈，同时递增stackArray[top]中的top值。
• 检查堆栈是否为空。然后使用peek()通过返回stackArray[top]来查找顶部元素，因为top已经设置为数组中的最后一个元素。
• 最后，使用bottom()函数查找底部元素，该函数返回stackArray[0]的值，即堆栈数组中第一个也是最底部的元素。
• 输出最终的顶部和底部值。

示例

以下是使用迭代方法查找给定堆栈的顶部和底部元素的Java程序：

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);
    }
}

输出

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

时间复杂度：在堆栈形成（压入）期间为O(n)，因为每个元素都添加到数组的末尾，并且索引递增每次增加1，直到大小n。在peek和bottom操作期间为O(1)，因为它返回stackArray[top]和stackArray[0]。

空间复杂度：O(n)，因为我们将maxSize固定为存储n个元素，与堆栈的大小成正比。

递归方法查找顶部和底部元素

在这种方法中，我们将使用递归来查找堆栈中的顶部和底部元素。堆栈使用push()操作进行初始化和形成，并递归地提取所需元素。以下是查找给定堆栈的顶部和底部元素的步骤：

• 使用等于5的maxSize和最初设置为-1的top初始化堆栈。
• 检查堆栈大小是否不超过maxSize。使用push()函数将每个整数值压入堆栈，将top递增1并将值存储在stackArray[top]中。
• 使用递归方法查找底部元素，将当前索引设置为top值。然后，如果索引为0，则返回stackArray[0]（底部元素），否则使用递减1的索引递归调用该函数。
• 使用设置为0的索引查找顶部元素。在基本情况下，如果当前索引等于top值，则返回stackArray[top]。否则，使用递增1的索引递归调用该函数。
• 递归地打印stackArray[]中的所有元素，基本情况是如果索引小于0，则停止递归。否则，调用该函数并使用递减1的索引递归打印整数值。
• 调用main函数并打印顶部和底部元素以及整个堆栈。

示例

以下是使用递归方法查找给定堆栈的顶部和底部元素的Java程序：

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

输出

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

时间复杂度：总共为O(n)，因为在大小为n的堆栈形成期间，一个元素在push()操作中花费O(1)。在最坏情况下，递归操作花费O(n)。

空间复杂度：由于递归调用堆栈，递归为O(n)。数组本身也使用O(n)来存储n个元素。

结论

总之，这两种方法都分别适用于各自的情况，其中直接数组方法提供了对堆栈元素的常数时间访问以及其简单的交互实现。另一方面，递归方法提供了对堆栈操作的递归视角，使其更通用并强调了算法方法。理解这两种方法使您掌握堆栈的基础知识以及何时使用任何一种方法的知识。

以上是Java程序以查找给定堆栈的顶部和底部元素的详细内容。更多信息请关注PHP中文网其他相关文章！