队列反转算法优化探讨：能否在Queue方法内用Stack实现？

首先直接回应你的核心疑问：完全可以在Queue类的成员方法中新建Stack对象来实现队列反转，这是一种直观易理解的方案。另外，针对你基于链表实现的自定义队列，还有空间效率更高的原地反转方案，下面分几种方案详细说明：

方案1：在Queue类中封装栈实现反转 #

把反转逻辑封装成Queue类的成员方法，既符合面向对象的设计思路，还能直接复用原队列（无需额外创建新队列）。修改后的代码如下：

package test;
import java.util.Stack;

public class InverseDemo {
    public static void main(String[] args) {
        Queue q = new Queue();
        q.enqueue(3);
        q.enqueue(4);
        q.enqueue(5);
        
        q.reverse(); // 调用类内方法完成反转
        
        while (!q.isEmpty()) {
            System.out.println(q.dequeue()); // 输出5、4、3
        }
    }
}

class Queue {
    private Node first;
    private Node last;
    private int N;

    class Node {
        int item;
        Node next;
    }

    public boolean isEmpty() {
        return first == null;
    }

    public int size() {
        return N;
    }

    public void enqueue(int item) {
        Node oldlast = last;
        last = new Node();
        last.item = item;
        last.next = null;
        if (isEmpty()) first = last;
        else oldlast.next = last;
        N++;
    }

    public int dequeue() {
        int item = first.item;
        first = first.next;
        if (isEmpty()) last = null;
        N--;
        return item;
    }

    // 新增：用栈实现的队列反转方法
    public void reverse() {
        Stack<Integer> stack = new Stack<>();
        // 1. 将队列所有元素移到栈中
        while (!isEmpty()) {
            stack.push(dequeue());
        }
        // 2. 将栈中元素重新移回原队列
        while (!stack.isEmpty()) {
            enqueue(stack.pop());
        }
    }
}

这个方案逻辑简单、容易维护，时间复杂度为O(n)（每个元素入栈和出栈各一次），空间复杂度为O(n)（需要额外栈存储所有元素），适合大多数常规场景。

方案2：原地反转链表（最优空间效率） #

因为你的Queue是基于单向链表实现的，我们可以直接反转链表的节点指向，不需要额外的栈或队列空间，把空间复杂度降到O(1)，这是效率最高的方案：

// 在Queue类中新增原地反转方法
public void reverseInPlace() {
    if (isEmpty() || size() == 1) {
        return; // 空队列或单个元素无需反转
    }
    
    Node prev = null;
    Node current = first;
    Node nextNode;
    
    // 反转链表的next指向
    while (current != null) {
        nextNode = current.next;
        current.next = prev;
        prev = current;
        current = nextNode;
    }
    
    // 交换队列的头尾指针
    Node temp = first;
    first = last;
    last = temp;
}

这个方案时间复杂度同样是O(n)（仅遍历一次链表），但不需要额外存储结构，适合处理大规模队列的反转场景。

方案3：递归实现反转 #

如果你偏爱简洁的代码风格，可以用递归方式实现反转，本质是利用JVM的调用栈替代显式的Stack对象：

// 在Queue类中新增递归反转方法
public void reverseRecursively() {
    if (isEmpty()) {
        return;
    }
    int item = dequeue();
    reverseRecursively();
    enqueue(item);
}

这个方案代码非常简洁，但要注意递归深度限制：如果队列元素过多（比如超过1万），可能会触发StackOverflowError，更适合小规模队列的场景。

方案对比总结 #

内容的提问来源于stack exchange，提问作者1107405052