Kieran Lavelle
Kieran Lavelle

Reputation: 446

Why wont my queue implementation work

Im trying to make a linked list implementation of a queue in java we are working from a basic IQueue interface then we have a list element class which defines the elements in the list/queue then we also have a MyQueue class which the bulk of the information is stored in. I will provide all of the code below. I have also written a test.java main class to run it all and see if it is working then when I compiled it and ran it I got some errors which will also be shown.

Interface:

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

}

List element:

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

Sorry for that big bulk of code but I feel it is all needed to help the issue be worked out. Thanks in advance and here is the error:

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)

Bit of an accident I ran it wrong. New error:

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)

Upvotes: 1

Views: 292

Answers (1)

Ante Modric
Ante Modric

Reputation: 41

In toString method, you don't move from head, and without that head will always have next element

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

So you have inifinite loop.

Also, when adding new element, not only must current tail reference new element with 'next', new element must reference tail with 'prev'.

In toString you should something like this

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

And when adding element something like this

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

Upvotes: 1

Related Questions