为什么我的队列实现不能工作

Question

我试图用java实现一个队列的链表，我们从一个基本的IQueue接口开始工作，然后我们有一个定义列表/队列中元素的列表元素类，然后我们还有一个存储大部分信息的MyQueue类。我将提供下面的所有代码。我还编写了一个test.java主类来运行它，看看它是否正常工作，然后当我编译并运行它时，我遇到了一些错误，这些错误也会显示出来。

接口：

/**
* An interface for a generic queue
*/
public interface IQueue<E> {
    // Add an element to the (end of) queue.
    public void enqueue(E element);
    // Remove and return element from the (start of) queue.
    public E dequeue();
    // Returns true when the queue has no elements, false otherwise.
    public boolean isEmpty();
}

列表元素：

public class ListElement<E> {
    private final E value;
    private ListElement<E> next;
    private ListElement<E> prev;
    public ListElement(E value) {
        this.value = value;
    }
    public E getValue() {
        return this.value;
    }
    public ListElement<E> getNext() {
        return this.next;
    }
    public ListElement<E> getPrev() {
        return this.prev;
    }
    public void setNext(ListElement<E> e) {
        this.next = e;
    }
    public void setPrev(ListElement<E> e) {
        this.prev = e;
    }
}

MyQueue.java：

import java.util.ArrayList;
public class MyQueue<E> implements IQueue<E> {
    private ListElement<E> head;
    private ListElement<E> tail;
    public MyQueue() {
        head = null;
        tail = null;
    }
    // INCOMPLETE.
    public E modifyHead(E newhead) {
        ListElement<E> update_head = new ListElement(newhead);
        ListElement<E> oldhead = new ListElement(head);
        head = update_head;
        // Modifies the head of the queue to contain newhead.
        // Returns the old value in the head.
        return oldhead.getValue();
    }
    public boolean isEmpty() {
        return (head == null);
    }
    public E dequeue() {
        if (isEmpty()) {
            return null;
        }
        ListElement<E> tmp = head;
        head = tmp.getNext();
        if (head == null) {
            tail = null;
        }
        return tmp.getValue();
    }
    public void enqueue(E value) {
        ListElement<E> tmp = new ListElement(value);
        if (isEmpty()) {
            tail = head = tmp;
        } else {
            tail.setNext(tmp);
            tail = tmp;
        }
    }
    public String toString() {
        ArrayList a = new ArrayList();
        while (head.getNext() != null){
            a.add(head.getNext());
        }
        return a.toString();
    }
}

Test.java：

public class test{
    public static void main(String args[]){
        MyQueue test = new MyQueue();
        test.MyQueue();
        test.enqueue("Kieran");
        test.enqueue("Lavelle");
        test.toString();
        test.modifyHead("Replacement Head");
        test.toString();
    }
}

很抱歉有这么多代码，但我觉得这一切都是为了帮助解决这个问题。提前感谢，这里是错误：

Exception in thread "main" java.lang.NoClassDefFoundError: test/java
Caused by: java.lang.ClassNotFoundException: test.java
    at java.net.URLClassLoader$1.run(URLClassLoader.java:202)
    at java.security.AccessController.doPrivileged(Native Method)
    at java.net.URLClassLoader.findClass(URLClassLoader.java:190)
    at java.lang.ClassLoader.loadClass(ClassLoader.java:306)
    at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:301)
    at java.lang.ClassLoader.loadClass(ClassLoader.java:247)

有点意外，我跑错了。新错误：

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at java.util.Arrays.copyOf(Arrays.java:2760)
    at java.util.Arrays.copyOf(Arrays.java:2734)
    at java.util.ArrayList.ensureCapacity(ArrayList.java:167)
    at java.util.ArrayList.add(ArrayList.java:351)
    at MyQueue.toString(MyQueue.java:55)
    at test.main(test.java:6)

Answer 1

在toString方法中，您不会从head移动，如果没有head，将始终具有下一个元素

while (head.getNext() != null){
     a.add(head.getNext());
}

所以你有一个无限循环。

此外，添加新元素时，当前尾部不仅必须用"next"引用新元素，新元素还必须用"prev"引用尾部。

在toString中，您应该使用类似的内容

ListElement<E> item = head;
a.add(item);
while (item.getNext() != null){
     a.add(item.getNext());
     item = item.getNext();
}

当添加类似的元素时

tail.setNext(tmp);
tmp.setPrev(tail);
tail = tmp;