---

Java中反转栈的不同方法

在这篇文章中，我们将探讨使用Java反转栈的不同方法。栈是一种后进先出（LIFO）的数据结构，支持从同一侧插入（push）和移除（pop）元素。

我们可以将栈想象成桌子上的一摞盘子；从顶部拿盘子是最安全的。

2. 问题：反转栈

让我们深入探讨问题陈述。我们得到一个对象的_栈_作为输入，我们需要返回元素顺序相反的栈。这里有一个例子。

输入：[1, 2, 3, 4, 5, 6, 7, 8, 9] 输出：[9, 8, 7, 6, 5, 4, 3, 2, 1] 输入是前九个自然数的栈，我们的代码输出应该是顺序相反的相同自然数。我们可以将这个问题扩展到任何类型的栈，例如，一个_字符串_元素的栈，一个自定义对象如_Node_的栈等。

例如：

输入：["Red", "Blue", "Green", "Yellow"] 输出：["Yellow", "Green", "Blue", "Red"]

3. 使用_队列_反转栈

在这一部分，让我们看看如何通过使用_队列_数据结构来解决问题。_队列_是一个先进先出（FIFO）的数据结构，支持从后端添加元素和从前端移除元素。

给定一个元素的栈作为输入，我们可以一次从栈的顶部取出元素，并将它们插入到我们的队列中。 从我们的第一个自然数示例开始，我们将从指向9的栈顶部开始。我们在每一步将栈的顶部元素插入队列的后端，最终，我们将清空栈。此时，我们已经用以下顺序的元素填充了队列： (后端) [1, 2, 3, 4, 5, 6, 7, 8, 9] (前端)。

完成这项工作后，我们可以从队列中移除元素，这发生在前端，并将其推回到我们的栈上。 完成这项活动后，我们将得到我们期望的输出栈 [9, 8, 7, 6, 5, 4, 3, 2, 1]。

这是代码的样子，假设栈的类型是_Integer_：

public Stack reverseIntegerStack(Stack````<Integer>```` inputStack) {
    Queue````<Integer>```` queue = new LinkedList<>();
    while (!inputStack.isEmpty()) {
        queue.add(inputStack.pop());
    }
    while (!queue.isEmpty()) {
        inputStack.add(queue.remove());
    }
    return inputStack;
}

4. 使用递归反转栈

让我们讨论一种不使用任何额外数据结构解决问题的方法。递归是计算机科学中的核心概念，它涉及到一个方法反复调用自己，只要满足一个先决条件。 任何递归函数都应该有两个组成部分：

• 递归调用：在我们的例子中，递归调用该方法将从给定的栈中移除元素
• 停止条件：当给定的栈为空时，递归将结束

每次对递归方法的调用都会向JVM内存中的调用栈添加内容。我们可以利用这一事实来反转给定的栈。递归调用将从栈的顶部移除一个元素并将其添加到内存调用栈中。

当输入栈为空时，内存调用栈包含栈元素的逆序。 调用栈的顶部包含数字1，而最底部的调用栈包含数字10。此时，我们从调用栈中取出项目并将元素插入到栈的底部，反转元素的原始顺序。

让我们看看这里的两步递归算法的代码：

private void reverseStack(Stack````<Integer>```` stack) {
    if (stack.isEmpty()) {
        return;
    }
    int top = stack.pop();
    reverseStack(stack);
    insertBottom(stack, top);
}

reverseStack() 方法递归地从栈中弹出顶部元素。一旦输入栈为空，我们将当前在调用栈中的元素插入到栈的底部：

private void insertBottom(Stack````<Integer>```` stack, int value) {
    if (stack.isEmpty()) {
        stack.add(value);
    } else {
        int top = stack.pop();
        insertBottom(stack, value);
        stack.add(top);
    }
}

5. 比较反转栈的方法

我们讨论了两种反转给定栈的方法。这些算法适用于任何类型的_栈_。第一种使用额外的_队列_数据结构的解决方案在O(n)时间复杂度内反转栈。 然而，由于我们使用额外的空间形式的_队列_，空间复杂度也是O(n)。

另一方面，递归解决方案由于递归调用具有O(n²)的时间复杂度**，但由于我们使用程序调用栈来存储栈的元素，所以没有额外的空间复杂度。**

6. 结论

在这篇文章中，我们讨论了在Java中反转_栈_的两种方法，并比较了算法的运行时间和空间复杂度。像往常一样，所有代码示例都可以在GitHub上找到。