java - 为什么我的队列实现不起作用

Question

我正在尝试在java中创建队列的链表实现，我们正在从基本的IQueue接口(interface)开始工作，然后我们有一个列表元素类，它定义列表/队列中的元素，然后我们还有一个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();
    }
}

测试.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 方法中，您不会从头部移动，并且没有该头部将始终具有下一个元素

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;