在堆疊中找到最小的數字并將其放在堆疊的頂部而不改變其余的順序

我試圖在整數堆疊中找到最小的數字并將其放在堆疊的頂部，而不改變其余數字的順序，所以一個堆疊，例如[1 2 3 4 5]最左邊的數字是堆疊的頂部，而[2 3 4 5 1]使用下面代碼中顯示的方法后，最右邊的數字應該成為堆疊的底部，但由于某種原因，我在方法呼叫后嘗試列印堆疊的內容后findSmallest遇到了一個問題。EmptyStackException

這是我的代碼：

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();
    }
}

uj5u.com熱心網友回復：

避免使用硬編碼的值，例如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 資料結構時 - 使用DequeJDK 中介面的標準實作。因此，如果您不需要Stack根據您的作業使用課程，您可以將其替換為ArrayDeque.

uj5u.com熱心網友回復：

您的代碼的這一部分是問題所在：

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

為什么會出現這個問題？

你在你的if宣告中試圖做的是

1. 檢查num頂部的stack2，如果是min則跳過它。
2. 如果num不是最小值，則num放在stack1. --> 這本身就是 2 個步驟： [a]彈出num和[b ]推stack2到.numstack1

在找到最小值的情況下會發生什么？您忽略了第 2 步- 這意味著您永遠不會彈出頂部 - 這min是stack2. 因此，當您再次回圈時，頂部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

旁白：還有其他方法可以改進此代碼，但您似乎還有很多東西要學，所以我只解決了您提出的具體問題，以免讓您不知所措。

標籤：爪哇 数据结构 堆

上一篇：錯誤：java.lang.SecurityException：我的位置需要權限ACCESS_FINE_LOCATION或ACCESS_COARSE_LOCATION

下一篇：密碼未在SpringSecurity中編碼