创建队列类并从第一个到最后一个打印内部的元素

Question

我目前有一个任务，我需要创建我自己的队列类和方法，如enquue（）、dequue（），并从头到尾显示元素。这是我到目前为止所做的：

节点类：

  class Node{
        //attributes
        public String data;
        public Node next;
    
        //basic constructor
        Node(){
    
        }
    
        Node(String data){
            this.data = data;
            this.next = null;
        }
    
        //accessors
        public String getData(){
            return this.data;
        }
        public Node getNext(){
            return this.next;
        }
    
        //mutators
        public void setData(String tmpData){
            this.data = tmpData;
        }
        public void setNext(Node tmpNext){
            this.next = tmpNext;
        }
    }

这是我的队列类：

class MyQueue{
    //attributes
    private Node front, rear;

MyQueue(){
    this.front = null;
    this.rear = null;
}

//method to insert one node at the end of the queue
public void enqueue(Node node){
    node.next = this.rear;
    this.rear = node;
}

//get and remove the front node from queue
public String dequeue(){
    //check if the queue empty or not
    if(this.rear == null){
        System.out.println("Queue is empty");
        return null;
    } else if(this.rear.next == null){ // the queue only have 1 element
        this.rear = null;
        return this.rear.toString();
    } else{ //remove the front node
        Node tmp = this.rear;
        //traverse to reach the second element
        while (tmp.next.next != null) {
            tmp = tmp.next;
        }
        //remove first element
        tmp.next = null;
        return tmp.next.toString();
    }
}

//check if the queue is empty or not
public boolean isEmpty(){
    if(this.rear == null){
        return true;
    } else{
        return false;
    }
}

//method to display
public void displayQueue(){
    if(this.rear == null){
        System.out.println("Queue is empty");
    } else{
        Node tmp = this.rear;
        while(tmp != null) {
            System.out.print(tmp.data + " ");
            tmp =tmp.next;
        }
        System.out.println();
    }
}
}

以及测试的主要类别：

class Main{
    public static void main(String[] args) {
        MyQueue queue = new MyQueue();
        queue.enqueue(new Node("1"));
        queue.enqueue(new Node("2"));
        queue.enqueue(new Node("3"));
        queue.displayQueue();
        
    }
}

所以我想要的输出是

1 2 3

但是，我的输出是：

3 2 1

你们能看看吗，我想这一定和displayQueue（）方法有关，但是我不知道如何修复它，你们能帮我吗？非常感谢

Answer 1

我相信，您的en队列逻辑在很大程度上是正确的，因为您在队列的末尾添加了新元素，并将this.rear重置为添加的新元素。但是，您应该使您的displayQueue方法递归，以便您可以遵循先进先出原则，并从开始到结束遍历队列，而不是像现在这样从结束到开始。这里推荐递归的原因是，您当前构建队列的方式是从最后一个节点到第一个节点只有一条单向路径，反之亦然，因此递归方法的基本条件可以是当节点您的迭代是null。此时，您可以开始打印节点，同时从队列的开始到结束进行回溯。请注意，当您正在迭代的节点是队列的开始时，您正在迭代的节点的下一个指针将为空。下面是递归displayQueue方法在使用helper函数时的样子，

public void displayQueue(){
    if (this.rear == null) {
        System.out.println("Queue is empty");
    } 
    else {
        displayQueueHelper(this.rear);
    }
}

private void displayQueueHelper(Node n) {
    if (n == null) {
        return;
    }
    displayQueueHelper(n.next);
    System.out.print(n.data + " ");
}

我选择使用递归助手函数，因为您仍然应该使用主外部displayQueue函数来检查队列是否是空的，然后再决定是否迭代队列。