数据结构
网络
关系型数据库管理系统
操作系统
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+ 浏览量
广告