创建队列 class 并从头到尾打印里面的元素

Question

我目前有一个作业需要创建自己的队列class和enqueue()、dequeue()等方法，并从头到尾显示元素。这是我到目前为止所做的：

节点class:

  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:

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：

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

我相信您的 enqueue 逻辑在很大程度上是正确的，因为您在队列末尾添加新元素并将 this.rear 重置为添加的新元素。但是，你应该使你的 displayQueue 方法递归，这样你就可以遵循 FIFO，first-in-first-out 原则并从头到尾遍历队列而不是你现在拥有的，它正在遍历队列从头到尾。此处推荐递归的原因是，您当前以从最后一个节点到第一个节点只有 one-way 路由的方式构建队列，反之亦然，因此递归方法的基本条件可以当您迭代的节点是 null 时。那时你可以开始打印出节点，因为你 back-track 从队列的开始到结束。请注意，当您正在迭代的节点是队列的开始时，您正在迭代的节点的 next 指针将为 null 。这是带有辅助函数的递归 displayQueue 方法的样子，

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 函数来检查队列是否为空。

创建队列 class 并从头到尾打印里面的元素

Create the Queue class and print the element inside from first to last

java

queue