本教程將介紹如何使用Java查找給定堆棧的頂部和底部元素。

堆棧代表遵循后進(jìn)先出(LIFO)原則的線性數(shù)據(jù)集，因此元素在同一位置添加和刪除。我們將進(jìn)一步探討兩種查找給定堆棧的頂部和底部元素的方法，即通過迭代和遞歸。

問題陳述

我們將得到一個(gè)包含n個(gè)元素的堆棧數(shù)組，任務(wù)是在不以任何方式破壞它的前提下找到堆棧的第1個(gè)和第n個(gè)元素。因此，我們需要在自定義堆棧中使用迭代方法和遞歸方法執(zhí)行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>

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

對(duì)于第一種方法，我們將定義一個(gè)用作堆棧的數(shù)組，然后定義堆棧操作以通過迭代方法檢索所需元素。以下是查找給定堆棧的頂部和底部元素的步驟：

• 使用等于6的maxSize值初始化堆棧stackArray[]（在堆棧數(shù)組中最多容納6個(gè)元素），并將top設(shè)置為-1（表示空數(shù)組）。
• 通過push()操作將元素5、10、15、20、25和30壓入堆棧，同時(shí)遞增stackArray[top]中的top值。
• 檢查堆棧是否為空。然后使用peek()通過返回stackArray[top]來查找頂部元素，因?yàn)閠op已經(jīng)設(shè)置為數(shù)組中的最后一個(gè)元素。
• 最后，使用bottom()函數(shù)查找底部元素，該函數(shù)返回stackArray[0]的值，即堆棧數(shù)組中第一個(gè)也是最底部的元素。
• 輸出最終的頂部和底部值。

示例

以下是使用迭代方法查找給定堆棧的頂部和底部元素的Java程序：

class MyStack {
    private int maxSize;
    private int[] stackArray;
    private int top;
    // 使用MyStack構(gòu)造函數(shù)初始化堆棧
    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()查找堆棧數(shù)組中的底部元素（第一個(gè)添加的值）
    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); // 創(chuàng)建大小為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>

時(shí)間復(fù)雜度：在堆棧形成（壓入）期間為O(n)，因?yàn)槊總€(gè)元素都添加到數(shù)組的末尾，并且索引遞增每次增加1，直到大小n。在peek和bottom操作期間為O(1)，因?yàn)樗祷豷tackArray[top]和stackArray[0]。

空間復(fù)雜度：O(n)，因?yàn)槲覀儗axSize固定為存儲(chǔ)n個(gè)元素，與堆棧的大小成正比。

遞歸方法查找頂部和底部元素

在這種方法中，我們將使用遞歸來查找堆棧中的頂部和底部元素。堆棧使用push()操作進(jìn)行初始化和形成，并遞歸地提取所需元素。以下是查找給定堆棧的頂部和底部元素的步驟：

• 使用等于5的maxSize和最初設(shè)置為-1的top初始化堆棧。
• 檢查堆棧大小是否不超過maxSize。使用push()函數(shù)將每個(gè)整數(shù)值壓入堆棧，將top遞增1并將值存儲(chǔ)在stackArray[top]中。
• 使用遞歸方法查找底部元素，將當(dāng)前索引設(shè)置為top值。然后，如果索引為0，則返回stackArray[0]（底部元素），否則使用遞減1的索引遞歸調(diào)用該函數(shù)。
• 使用設(shè)置為0的索引查找頂部元素。在基本情況下，如果當(dāng)前索引等于top值，則返回stackArray[top]。否則，使用遞增1的索引遞歸調(diào)用該函數(shù)。
• 遞歸地打印stackArray[]中的所有元素，基本情況是如果索引小于0，則停止遞歸。否則，調(diào)用該函數(shù)并使用遞減1的索引遞歸打印整數(shù)值。
• 調(diào)用main函數(shù)并打印頂部和底部元素以及整個(gè)堆棧。

示例

以下是使用遞歸方法查找給定堆棧的頂部和底部元素的Java程序：

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

輸出

<code>堆棧中的頂部元素是 --> 30
堆棧中的底部元素是 --> 5</code>

時(shí)間復(fù)雜度：總共為O(n)，因?yàn)樵诖笮閚的堆棧形成期間，一個(gè)元素在push()操作中花費(fèi)O(1)。在最壞情況下，遞歸操作花費(fèi)O(n)。

空間復(fù)雜度：由于遞歸調(diào)用堆棧，遞歸為O(n)。數(shù)組本身也使用O(n)來存儲(chǔ)n個(gè)元素。

結(jié)論

總之，這兩種方法都分別適用于各自的情況，其中直接數(shù)組方法提供了對(duì)堆棧元素的常數(shù)時(shí)間訪問以及其簡單的交互實(shí)現(xiàn)。另一方面，遞歸方法提供了對(duì)堆棧操作的遞歸視角，使其更通用并強(qiáng)調(diào)了算法方法。理解這兩種方法使您掌握堆棧的基礎(chǔ)知識(shí)以及何時(shí)使用任何一種方法的知識(shí)。

以上是Java程序以查找給定堆棧的頂部和底部元素的詳細(xì)內(nèi)容。更多信息請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！