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中文網其他相關文章！