数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学Java程序：查找栈中最大和最小元素
栈是一种基本的遵循后进先出 (LIFO) 原则的数据结构。栈有很多用例，例如组织函数调用和撤销操作。通常，人们可能会遇到查找栈中最大和最小元素的问题，本文将演示使用 Java 完成此任务的多种方法。
理解栈
栈是一种线性数据结构，只允许在一端进行操作，称为栈顶。主要操作包括：
- Push（压栈）：将元素添加到栈顶。
- Pop（出栈）：移除并返回栈顶元素。
- Peek（查看）：查看栈顶元素，但不移除它。
- IsEmpty（是否为空）：检查栈是否为空。
问题陈述
目标是确定栈中的最大和最小元素。考虑到栈的 LIFO 特性，无法直接访问除栈顶之外的元素。这就需要遍历栈，同时跟踪最大值和最小值。
使用两个附加变量
这里我们使用两个变量 min 和 max 分别跟踪最小值和最大值。遍历栈，并在处理每个元素时更新这些变量。这是最简单的方法，也是最耗时和最耗空间的方法。
import java.util.Stack;
public class MaxMinInStack {
public static void main(String[] args) {
Stack < Integer > stack = new Stack < > ();
stack.push(10);
stack.push(20);
stack.push(30);
stack.push(5);
stack.push(15);
int[] result = findMaxMin(stack);
System.out.println("Maximum element: " + result[0]);
System.out.println("Minimum element: " + result[1]);
}
public static int[] findMaxMin(Stack <Integer> stack) {
if (stack.isEmpty()) {
throw new IllegalArgumentException("Stack is empty");
}
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (Integer element: stack) {
if (element > max) {
max = element;
}
if (element < min) {
min = element;
}
}
return new int[] {
max,
min
};
}
}
输出
Maximum element: 30 Minimum element: 5
使用辅助栈
这里我们通过使用 pop 操作遍历栈并更新 min 和 max。辅助栈临时保存元素，然后将其恢复到原始栈中。
import java.util.Stack;
public class MaxMinInStack {
public static void main(String[] args) {
Stack <Integer> stack = new Stack < > ();
stack.push(10);
stack.push(20);
stack.push(30);
stack.push(5);
stack.push(15);
int[] result = findMaxMinWithAuxiliaryStack(stack);
System.out.println("Maximum element: " + result[0]);
System.out.println("Minimum element: " + result[1]);
}
public static int[] findMaxMinWithAuxiliaryStack(Stack <Integer> stack) {
if (stack.isEmpty()) {
throw new IllegalArgumentException("Stack is empty");
}
Stack <Integer> tempStack = new Stack < > ();
int max = stack.peek();
int min = stack.peek();
while (!stack.isEmpty()) {
int current = stack.pop();
if (current > max) {
max = current;
}
if (current < min) {
min = current;
}
tempStack.push(current);
}
// Restore the original stack
while (!tempStack.isEmpty()) {
stack.push(tempStack.pop());
}
return new int[] {
max,
min
};
}
}
输出
Maximum element: 30 Minimum element: 5
使用两个栈
这种方法使用两个额外的栈，一个用于记住最大元素 (maxStack)，另一个用于记住最小元素 (minStack)。每次新元素进入主栈时，如果它使最大值或最小值变大，我们也会将其放入 maxStack 或 minStack 中。
import java.util.Stack;
public class MaxMinInStack {
public static void main(String[] args) {
Stack <Integer> stack = new Stack < > ();
stack.push(10);
stack.push(20);
stack.push(30);
stack.push(5);
stack.push(15);
int[] result = findMaxMinWithTwoStacks(stack);
System.out.println("Maximum element: " + result[0]);
System.out.println("Minimum element: " + result[1]);
}
public static int[] findMaxMinWithTwoStacks(Stack <Integer> stack) {
Stack <Integer> maxStack = new Stack < > ();
Stack <Integer> minStack = new Stack < > ();
while (!stack.isEmpty()) {
int current = stack.pop();
if (maxStack.isEmpty() || current >= maxStack.peek()) {
maxStack.push(current);
}
if (minStack.isEmpty() || current <= minStack.peek()) {
minStack.push(current);
}
}
int max = maxStack.peek();
int min = minStack.peek();
return new int[] {
max,
min
};
}
}
输出
Maximum element: 30 Minimum element: 5
使用修改后的栈结构
修改栈结构，使其本身包含最大值和最小值以及常规栈元素。每个元素都保存为一个包含值、当前最大值和当前最小值的对。
import java.util.Stack;
public class MaxMinInStack {
static class StackNode {
int value;
int currentMax;
int currentMin;
StackNode(int value, int currentMax, int currentMin) {
this.value = value;
this.currentMax = currentMax;
this.currentMin = currentMin;
}
}
public static void main(String[] args) {
Stack <StackNode> stack = new Stack < > ();
push(stack, 10);
push(stack, 20);
push(stack, 30);
push(stack, 5);
push(stack, 15);
int[] result = findMaxMinWithModifiedStack(stack);
System.out.println("Maximum element: " + result[0]);
System.out.println("Minimum element: " + result[1]);
}
public static void push(Stack <StackNode> stack, int value) {
int max = stack.isEmpty() ? value : Math.max(value, stack.peek().currentMax);
int min = stack.isEmpty() ? value : Math.min(value, stack.peek().currentMin);
stack.push(new StackNode(value, max, min));
}
public static int[] findMaxMinWithModifiedStack(Stack <StackNode> stack) {
if (stack.isEmpty()) {
throw new IllegalArgumentException("Stack is empty");
}
StackNode topNode = stack.peek();
return new int[] {
topNode.currentMax, topNode.currentMin
};
}
}
输出
Maximum element: 30 Minimum element: 5
结论
查找栈中最大和最小元素可以使用不同的方法，每种方法都有其优点和权衡。所示方法包括使用额外变量、辅助栈、为最大值和最小值管理单独的栈或更改栈本身的结构。
每种技术都提供了一种特定方法来处理访问或保存栈元素的问题，这使其适用于某些情况，具体取决于内存限制、性能要求和数据完整性需求。了解和应用这些方法可以帮助开发人员有效地处理 Java 中的栈，使他们的应用程序最适合某些情况。
更新于：2024年8月18日
147 次浏览
广告