資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Java程式查詢給定棧的頂部和底部元素
在本教程中，我們將學習如何使用Java查詢給定棧的頂部和底部元素。
當我們檢視棧時，它表示一個遵循後進先出 (LIFO) 原則的線性資料集，因此元素在同一位置新增和刪除。我們將進一步探討兩種查詢給定棧的頂部和底部元素的方法，即透過迭代和遞迴。
問題陳述
我們將得到一個包含 n 個元素的棧陣列，任務是查詢棧的第 1 個和第 n 個元素，而不會以任何方式破壞它。因此，我們需要使用迭代方法和遞迴在自定義棧中執行peek() 操作，確保原始棧保持不變。
輸入 1
stack = [5, 10, 15, 20, 25, 30]
輸出 1
The Top element in the stack is --> 30 The Bottom element in the stack is --> 5
輸入 2
stack = [1000, 2000, 3000, 4000, 5000]
輸出 2
Stack Elements: 5000 4000 3000 2000 1000 Bottom Element: 1000 Top Element: 5000
查詢頂部和底部元素的迭代方法
對於第一種方法，我們將定義一個陣列，用於將元素作為棧儲存，然後定義棧操作以透過迭代方法檢索所需的元素。以下是查詢給定棧的頂部和底部元素的步驟：- 使用等於 6 的maxSize值初始化棧stackArray[]（在棧陣列中最多儲存 6 個元素），並將頂部設定為 -1（表示空陣列）。
- 透過push() 操作將元素 5、10、15、20、25 和 30 推入棧，同時遞增stackArray[top]中的頂部值。
- 檢查棧是否為空。然後使用peek()透過返回 stackArray[top] 來查詢頂部元素，因為頂部已經設定為陣列中的最後一個元素。
- 最後，使用bottom() 函式查詢底部元素，該函式返回 stackArray[0] 的值，即棧陣列中第一個也是最底部的元素。
- 輸出最終的頂部和底部值。
示例
以下是使用迭代方法查詢給定棧的頂部和底部元素的 Java 程式：
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);
}
}
輸出
The top Element in the stack is --> 30 The bottom Element in the stack is --> 5
時間複雜度：在棧形成（Push）期間為 O(n)，因為每個元素都新增到陣列的末尾，並且索引遞增每次增加 1，直到大小 n。在 peek 和 bottom 操作期間為 O(1)，因為它返回 stackArray[top] 和 stackArray[0]。
空間複雜度：O(n)，因為我們將 masSize 固定為儲存 n 個元素，與棧的大小成正比。
查詢頂部和底部元素的遞迴方法
在這種方法中，我們將使用遞迴來查詢棧中的頂部和底部元素。棧使用push() 操作進行初始化和形成，並遞迴地提取所需的元素。以下是查詢給定棧的頂部和底部元素的步驟：
- 初始化棧，maxSize等於 5，頂部最初設定為 -1。
- 檢查棧大小是否不超過 maxSize。使用 push() 函式將每個整數值推入棧，將頂部遞增 1 並將值儲存在stackArray[top]中。
- 使用遞迴方法查詢底部元素，將當前索引設定為頂部值。然後，如果索引為 0，則返回stackArray[0]（底部元素），否則遞迴呼叫該函式並將索引遞減 1。
- 使用設定為 0 的索引查詢頂部元素。在基本情況下，如果當前索引等於頂部值，則返回stackArray[top]。否則，遞迴呼叫該函式並將索引遞增 1。
- 遞迴列印stackArray[]中的所有元素，基本情況是如果索引小於 0，則停止遞迴。否則，呼叫該函式並遞迴列印索引遞減 1 的整數值。
- 呼叫main 函式並列印頂部和底部元素以及整個棧。
示例
以下是使用遞迴方法查詢給定棧的頂部和底部元素的 Java 程式：
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);
}
}
輸出
Stack Elements: 6000 5000 4000 3000 2000 1000 Bottom Element: 1000 Top Element: 6000
時間複雜度：總體為 O(n)，因為在大小為 n 的棧形成期間，一個元素在 push() 操作中需要O(1)。在最壞情況下，遞迴操作需要 O(n) 。
空間複雜度：由於遞迴呼叫棧，因此為 O(n)。陣列本身也使用O(n)來儲存 n 個元素。
結論
總之，這兩種方法在各自的情況下都是合適的，其中直接的陣列方法提供對棧元素的常數時間訪問，並且其易於實現的互動。另一方面，遞迴方法提供了對棧操作的遞迴視角，使其更具通用性，並強調演算法方法。理解這兩種方法使您掌握了棧的基礎知識以及何時使用任何一種方法的知識。
更新於： 2024年9月23日
2K+ 瀏覽量
廣告