java - 下面使用链表实现队列有什么错误？

Question

我使用链表编写了以下队列实现，该链表不维护对尾节点的引用。当我尝试打印队列时，它仅输出头部，即仅输出一个节点。错误是什么？提前致谢!

package DataStructures;

import java.util.Scanner;

class Node {
    int x;
    Node nextNode;

    public Node(int x) {
        this.x = x;
        nextNode = null;
    }
}

class Queue {
    Node head = null;
    int n = 0;

    public void enqueue(int x) {
        if (n==0){
            head = new Node(x);
            n++;
            return;
        }
        Node tempHead = head;
        while (tempHead != null){
            tempHead = tempHead.nextNode;
        }
        tempHead = new Node(x);
        tempHead.nextNode = null;
        n++;
    }

    public int dequeue() {
        if (head == null) {
            throw new Error("Queue under flow Error!");
        } else {
            int x = head.x;
            head = head.nextNode;
            return x;
        }
    }

    public void printTheQueue() {
        Node tempNode = head;
        System.out.println("hi");
        while (tempNode != null){
            System.out.print(tempNode.x + "  ");
            tempNode = tempNode.nextNode;
        }

    }

}

public class QueueTest {

    private static Scanner in = new Scanner(System.in);

    public static void main(String[] args) {
        Queue queue = new Queue();
        while (true){
            int x = in.nextInt();
            if (x == -1){
                break;
            } else{
                queue.enqueue(x);
            }
        }

        queue.printTheQueue();
    }

}

Answer 1

您永远不会将节点分配给 nextNode，因此您的列表要么为空，要么由一个节点组成。

这是一个解决方案:

public void enqueue(int x) {
    n++;
    if (head == null) {
        head = new Node(x);
    else {
        Node last = head;
        while (last.nextNode != null)
            last = last.nextNode;
        last.nextNode = new Node(x);
    }
}

从技术上讲，您不需要n，但您可以将其用作列表大小的缓存。并且您应该在 deque() 中减少它。