找到堆栈中最小的数字，并将其放在堆栈的顶部，而不更改其余数字的顺序

Question

我试图在Integer堆栈中找到最小的数字，并将其放置在堆栈的顶部，而不改变其余数字的顺序，因此，使用下面代码中所示的findSmallest方法后，像[1 2 3 4 5]这样最左边的数字是堆栈的顶部、最右边的数字是栈的底部的堆栈应该变成[2 3 4 5 1]，但由于某种原因，我在方法调用后尝试打印堆栈的内容后遇到了CCD_ 4。

这是我的代码：

import java.util.Scanner;
import java.util.Stack;
public class StackTest {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
Stack<Integer> stack1 = new Stack<>();
for (int i = 0; i < 5; i++) {
stack1.push(input.nextInt());
}
System.out.println("------------------");
findSmallest(stack1);
for (int i = 0; i < 5; i++) {
System.out.println(stack1.pop());
}
}
public static void findSmallest(Stack<Integer> stack1) {
Stack<Integer> stack2 = new Stack<>();
Integer min = stack1.peek();
int i = 0;
while(i < 5) {
if(stack1.peek() < min)
min = stack1.peek();
stack2.push(stack1.pop());
i++;
}
int j = 0;
while (j < 5) {
if(!(stack2.peek().equals(min)))
stack1.push(stack2.pop());
j++;
}
stack1.push(min);
stack2.pop();
}
}

Answer 1

避免像while (i < 5)这样的硬编码值。

您需要清空第一个堆栈，并用第一个堆栈的所有内容填充第二个堆栈。

在执行此操作时，您需要对照以前遇到的最小元素检查每个元素，并找到一个新的最小元素，然后您需要更新其值和位置。

之后，我们需要做相反的事情：用第二个堆栈的内容填充第一个堆栈，但有一个例外——我们需要跳过与最小元素对应的索引。为此，我们可以使用相同的索引，即不需要定义单独的变量。

这就是它的实施方式。

public static void findSmallest(Stack<Integer> stack1) {
if (stack1.isEmpty()) return; // guarding condition against an empty stack

Stack<Integer> stack2 = new Stack<>();
int min = stack1.peek();
int minInd = 0;
int ind = 0;

while(!stack1.isEmpty()) {
int next = stack1.pop();
if (next < min) {
min = next;    // updating the minimum value
minInd = ind;  // updating the minimum index
}
stack2.push(next); // saving the next element in the second stack
ind++;             // updating the index
}

while (!stack2.isEmpty()) {
int next = stack2.pop();
if (ind == minInd) {
ind--;         // updating the index
continue;      // moving to the next iteration step (we should skip the min number - it will be added at the top afterwards)
}
stack1.push(next); // saving the next element in the second stack
ind--;             // updating the index
}

stack1.push(min);      // adding the min number at top
}

注意：类Stack是遗留的，不鼓励使用(由于向后兼容性的原因，它仍然存在)。当您需要在Java中实现Stack数据结构时，请使用JDK中Deque接口的标准实现。因此，如果根据您的作业不需要使用Stack类，您可以用ArrayDeque替换它。

Answer 2

代码的这一部分就是问题所在：

while (j < 5) {
if (!(stack2.peek().equals(min))) 
stack1.push(stack2.pop());
j++;
}

为什么会出现这个问题？

你在if声明中试图做的是

1. 检查stack2顶部的num，如果是min，则跳过它
2. 如果num不是最小值，则将num置于stack1之上-->这本身就是两个步骤：[a]将num从stack2弹出，[b]

在找到最小值的情况下会发生什么？您忽略步骤2-这意味着您永远不会弹出顶部-即stack2的min-off。因此，当您再次循环时，stack2的顶部仍然是min。

你是怎么修的？有一种方法：

while (j < 5) {
int num = stack2.pop();//NOTE: I pop here instead of below
if (num != min) stack1.push(num);//I cleaned up this line a bit
j++;
}
stack1.push(min);
//NOTE: I deleted the pop from here, because I did it above

旁白：还有其他方法可以改进这个代码，但似乎你还有很多东西要学，所以我只回答了你问的特定问题，以免让你不知所措