java - 反转数组中的元素，并使用单个 for 循环将反转后的元素压入堆栈

Question

我一直在研究一种算法，该算法使用单个 for 循环反转数组的顺序，然后将反转数组的每个元素压入堆栈。我一直很难让它正常工作，但我可能错误地解释了说明。说明如下:

Describe in pseudocode an efficient algorithm for reversing the order of the numbers in A using a single for-loop that indexes through the cells of A, to insert each element into a stack, and then another for-loop that removes the elements from the stack and puts them back into A in reverse order.

我可以很容易地颠倒数组的顺序，但是在 for 循环终止之前我的堆栈没有填满。我的代码:

public static void reverseAndPush(int[] a, int start, int end)
{

    for (int i = 0; i < end; i++)
    {
        int temp = a[start];
        a[start] = a[end];
        //only elements 5 and 4 get pushed to the stack
        stack.push(a[start]);
        a[end] = temp;
        start++;
        end--;
    }
}

如果我删除堆栈部分，数组将成功反转。需要进行哪些更改才能使此代码成功运行？我觉得跟我的执行语句有关系i < end但我尝试过的任何东西都无法正常工作(很多索引超出绑定(bind)异常)。说明说要用伪代码来做，但我还是想实际尝试编写算法，只是为了玩一玩。

编辑

对于第二个for循环，我曾想过这样做:

for n to 1 do
     stack.pop()

但这是假设我必须使用第一个 for 循环将所有元素压入堆栈。我可能错了。

Answer 1

这里的技巧是了解堆栈的工作原理，更具体地说，当您从堆栈中添加/删除项目时，项目最终会在哪里结束。堆栈数据结构是 LIFO(后进先出)数据结构，因此您添加的最后一项是您调用 pop() 时获得的第一项。这是一个函数，可以使用堆栈的特性来执行您的问题所描述的内容

public static int[] reverseArrayWithStack(int[] arrayToReverse)
{
    Stack<Integer> stack = new Stack<>();

    for(int i = 0; i < arrayToReverse.length; i++)
        stack.push(arrayToReverse[i]);

    for(int j = 0; j < arrayToReverse.length; j++)
        arrayToReverse[j] = stack.pop();

    return arrayToReverse;
}

例子

给定一个数组 arr = {1,2,3,4,5}

第一个 for 循环 - stack = {1,2,3,4,5}，所有值都被压入堆栈

第二个 for 循环 - 再次从索引 0 开始，因为当我们从堆栈弹出时我们将返回 5 因此 arr[0] = stack.pop() = 5, arr[1] = statck.pop() = 4 , arr[2] = statck.pop() = 3 等。这允许我们使用堆栈的 pop() 方法的行为从索引 0 开始以相反的顺序放置项目。