資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告