java - 使用一个 int 变量对 Stack 中的数字进行排序

Question

我有一个 Stack 变量(java 集合)，它包含五个整数，我还获得了一个 int 变量。是否可以对给定堆栈中的数字进行排序。我无法解决这个问题。如果您有任何想法，请在这里发帖。

Stack<Integer> s = new Stack<Integer>();
s.push(5);s.push(3);s.push(4);s.push(1);s.push(1);
int a;

除了上述代码片段中给出的变量之外，我们不应创建任何新变量，也不应使用 Collections.sort(s)。

Answer 1

效率极低，但遵守规则:)

Stack<Integer> s=new Stack<Integer>();
s.push(5);s.push(3);s.push(4);s.push(1);s.push(1);

int a = -1;
while (a == -1) { // Here 'a' is used as a kind of boolean that tells us whether we need to keep checking for items to reorder or not.
    for (a = 0; a < s.size() - 1; a++) { // Now 'a' becomes stack element's index.
        if (s.get(a) > s.get(a + 1)) {
            a = s.remove(a); // Here 'a' again changes meaning and holds the value that needs to be reordered.
            s.push(a);
            a = -1; // And here, 'a' is back to being used as a kind of boolean flag to control the outer loop.
            break;
        }
    }
}

编辑:基本上，我利用了一个事实，即我知道 Stack 扩展了 Vector。所以我实际上不必只使用标准的 Pop 和 Push 方法来访问/删除元素。我可以使用普通的 List 方法。

然后，我只是通过在不同的时间将它用于不同的目的(退出标志、循环索引、用于重新排序的值的临时存储)来最大限度地利用 a。通常是非常糟糕的编程习惯。

所以该算法基本上是循环遍历 Stack 元素。每当我找到一个大于下一个的元素时，我就会将其删除，然后将其放在 Stack 的末尾。在那一刻，我停止了循环，并将 a 重置为 -1 以确保我再次开始循环。我一直这样做，直到我能够遍历所有堆栈项目而无需重新排序。

编辑 2:这是另一种选择，它读起来有点复杂，但仍然遵守规则，并且按照冒泡排序模式执行得更好。使用的原则与我的第一次尝试几乎相同(滥用 Stack 作为 List + 使用变量 a 进行多次使用)。

Stack<Integer> s=new Stack<Integer>();
s.push(5);s.push(3);s.push(4);s.push(1);s.push(1);

int a = -1;
while (a < 0) { // keep looping if the previous loop performed at least one swap.
    a = 0;

    // if 'a' is >= 0, then it simply holds the index.
    // if 'a' < 0, then the index can be obtained by applying the bitwise complement operator.
    while ((a < 0 ? ~a : a) < (s.size() - 1)) { // loop all items except the last one.
        if (s.get(a < 0 ? ~a : a) > s.get((a < 0 ? ~a : a) + 1)) { // if this item is greater than the next, a swap is needed.
            s.insertElementAt(s.remove(a < 0 ? ~a : a), (a < 0 ? ~a : a) + 1); // swap this value with the next.

            // If this was not done already, flag the fact that a swap was performed by
            // applying the bitwise complement operator to 'a'.
            // This serves as a flag to let the outer loop know
            // that we'll need to perform the stack loop again.
            if (a >= 0) {
                a = ~a;
            }
        }

        // increment index. Or if the bitwise complement operator was applied,
        // then go the opposite way since the value is now negative.
        if (a >= 0) {
            a++;
        } else {
            a--;
        }
    }
}

编辑 3: 修改了我的最后一个算法以使用按位补码运算符而不是 Math.abs()。

此外，我想指出的是，与其他一些巧妙的尝试不同，该算法实际上并没有任何限制。它不会因为太多的递归调用而受到 StackOverflowException 的潜在影响，因为没有使用递归。使用的内存是稳定的。您可以在 Stack 中使用任何 int 值，即使是负值，它也能正常工作。