队列反转函数调用后仅显示单个数据问题排查求助

我需要实现队列反转，但调用reverseQueue函数后，队列始终只显示单个数据。怀疑dequeue函数有问题，但找不到故障点。

我的dequeue函数 #

public String dequeue(){ //get and remove the front node from the queue
        // check if it's empty
        if(this.rear == null){
            System.out.println("Queue is empty");
            return "Null";
        }else if(this.rear.getNext() == null){
            Node tmp = this.front;
            this.front = null;
            this.rear = null;
            return tmp.getData();
        }
        else{
            String data = front.getData();
            front = front.getNext();
            return data;
        }
    } 

我的enqueue函数 #

public void enqueue(Node node){ //insert one node at the end of the queue
        if(this.front == null){  
            this.rear = node;
            this.front = this.rear;
            return;
        }
        this.rear.setNext(node);
        this.rear = node;
    }

我的push和pop函数 #

public void push(Node node){ //push a node into stack
        node.setNext(this.top);
        this.top = node;
    }

public Node pop(){ //get and remove the top node from this stack
        //check if it is empty
        if(this.top == null){
            System.out.println("Stack is empty");
            return null;
        }else{
            Node currentTop = this.top;
            this.top = this.top.getNext();
            currentTop.setNext(null);
            return currentTop;
        }
    }

我的reverse函数 #

public static MyQueue reverseQueue(MyQueue queue){
        if(!queue.isEmpty()){
            MyStack s = new MyStack();
            String x;
            while(!queue.isEmpty()){
                x = queue.dequeue();
                s.push(new Node(x));
            }
            while(!s.isEmpty()){
                queue.enqueue(s.pop());
            }
            return queue;
        }else{
            System.out.println("empty queue");
            return queue;
        }
    }

测试代码 #

MyQueue queue = new MyQueue();
        queue.enqueue(new Node("1"));
        queue.displayQueue();
        queue.enqueue(new Node("2"));
        queue.displayQueue();
        queue.enqueue(new Node("3"));
        queue.displayQueue();
        // queue.dequeue();
        // queue.displayQueue();
        System.out.println(queue.isEmpty());

        reverseQueue(queue);
        queue.displayQueue();

终端输出 #

1
12
123
false
1

问题原因与修复 #

问题出在dequeue函数的判断逻辑错误：

队列的rear节点永远是链表的最后一个节点，它的next属性始终为null，不管队列中有1个还是多个元素。原代码中this.rear.getNext() == null这个条件永远为真，导致只要队列不为空，第一次调用dequeue就会触发该分支，直接把front和rear置为null。后续的dequeue操作会认为队列已空，最终只有第一个元素被压入栈，反转后队列自然只剩第一个元素。

修正后的dequeue函数

将判断条件改为this.front == this.rear（即队列仅含一个节点时）：

public String dequeue(){ //get and remove the front node from the queue
    // check if it's empty
    if(this.rear == null){
        System.out.println("Queue is empty");
        return "Null";
    }else if(this.front == this.rear){ // 仅当队列只剩一个节点时清空front和rear
        Node tmp = this.front;
        this.front = null;
        this.rear = null;
        return tmp.getData();
    }
    else{
        String data = front.getData();
        front = front.getNext();
        return data;
    }
} 

修正后，测试代码的终端输出会变为：

1
12
123
false
321

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