1
\$\begingroup\$

Please review my Queue implementation and let me know if you have any suggestions. I am not returning an exception for any of the methods defined here. As we know the exception is thrown only for add and remove functions and not for poll or offer functions.

    public class QueueImplementation<T> {
    private QueueNode<T> first;
    private QueueNode<T> last;
    private int size;

    private static class QueueNode<T> {
        private T val;
        private QueueNode<T> next;

        public QueueNode(T val) {
            this.val = val;
            this.next = null;
        }

        public void setNext(QueueNode<T> nextNode) {
            next = nextNode;
        }

        public QueueNode<T> getNext() {
            return next;
        }

        public T getValue() {
            return val;
        }

        @Override
        public String toString() {
            if(val == null) {
                return "null";
            }
            return val.toString();
        }

    }

    public void offer(T val) {
        QueueNode<T> cur = new QueueNode(val);
        if(size == 0) {
            cur.setNext(first);
            first = cur;
            last = cur;
            size++;
            return;
        }

        last.setNext(cur);
        last = cur;
        size++;
    }

    public T peek() {
        if(!isEmpty()) {
            return first.getValue();
        }
        else {
            return null;
        }
    }

    public QueueNode<T> poll() {
        if(isEmpty()) {
            return null;
        }

        QueueNode<T> cur = first;
        first = first.getNext();
        size--;
        return cur;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        size = 0;
        first = null;
        last = null;
    }

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        if(size == 0) {
            return "[]";
        }

        StringBuilder sb = new StringBuilder();
        QueueNode<T> cur = first;
        sb.append(cur.getValue() + "<-");

        while(cur.getNext() != null && !cur.equals(last)) {
            sb.append(cur.getNext().getValue() + "<-");
            cur = cur.getNext();
        }

        return sb.append("null").toString();
    }

    public static void main(String[] args) {
        QueueImplementation<Integer> q = new QueueImplementation<>();
        System.out.println(q.size());
        System.out.println(q.poll()); //returns null;
        System.out.println(q.peek()); //return null;
        q.offer(1);
        q.offer(10);
        q.offer(100);
        System.out.println(q.size());
        System.out.println(q.peek());
        System.out.println(q.poll());
        System.out.println(q.size());
        System.out.println(q.peek());
        System.out.println(q.poll());
        System.out.println(q.poll());
        System.out.println(q.size());
        System.out.println(q.poll());
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Please discontinue putting "thanks" in posts. Only show your gratitude with upvotes and accepts. \$\endgroup\$ – Jamal Sep 4 '16 at 20:55
1
\$\begingroup\$
@Override
public String toString() {
    if(size == 0) {
        return "[]";
    }

    StringBuilder sb = new StringBuilder();
    QueueNode<T> cur = first;
    sb.append(cur.getValue() + "<-");

    while(cur.getNext() != null && !cur.equals(last)) {
        sb.append(cur.getNext().getValue() + "<-");
        cur = cur.getNext();
    }

    return sb.append("null").toString();
}

Empty stack prints "[]", stack with one element prints 1<-null. Where are the surrounding brackets? Also, you can use a do-while loop here to prevent needing to specify how to print twice:

@Override
public String toString() {
    if(size == 0) {
        return "[]";
    }

    StringBuilder sb = new StringBuilder();
    QueueNode<T> cur = first;

    do {
        sb.append(cur.getValue() + "<-");
        cur = cur.getNext();
    } while(cur != null);

    return sb.append("null").toString();
}

It also vastly simplifies the iteration.


public void offer(T val) {
    QueueNode<T> cur = new QueueNode(val);
    if(size == 0) {
        cur.setNext(first);
        first = cur;
        last = cur;
        size++;
        return;
    }

    last.setNext(cur);
    last = cur;
    size++;
}

This could be simplified to reduce duplication - step 1, making the else case explicit...

public void offer(T val) {
    QueueNode<T> cur = new QueueNode(val);
    if(size == 0) {
        cur.setNext(first);
        first = cur;
        last = cur;
        size++;
    } else {
        last.setNext(cur);
        last = cur;
        size++;
    }
}

Step two, moving similar instructions into the shared area.

public void offer(T val) {
    QueueNode<T> cur = new QueueNode(val);
    if(size == 0) {
        cur.setNext(first);
        first = cur;
    } else {
        last.setNext(cur);
    }
    last = cur;
    size++;
}

Additionally, you can make use of isEmpty() here for increased clarity.


public QueueNode<T> poll() {
    if(isEmpty()) {
        return null;
    }

    QueueNode<T> cur = first;
    first = first.getNext();
    size--;
    return cur;
}

poll() is returning internal nodes. You want to return the value instead. Don't expose your internal nodes. Use exceptions for indicating pulling from an empty queue.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.