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

Question

我正在尝试在 java 中创建队列的链表实现，我们从基本的 IQueue 接口开始工作，然后我们有一个列表元素 class，它定义 [=30] 中的元素=] 然后我们还有一个 MyQueue class，其中存储了大量信息。我将在下面提供所有代码。我还写了一个 test.java main class 到运行这一切，看看它是否工作然后当我编译它和运行它时我得到了一些错误，这也是显示。

接口：

/**
* 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.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());
}

所以你有无限循环。

另外，添加新元素时，不仅当前tail必须引用新元素'next'，新元素还必须引用tail '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;

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

Why wont my queue implementation work

java

queue

linked-list