1
\$\begingroup\$

I am working on brushing up my data-structures knowledge, and was hoping to have my code/thoughts reviewed.

Interface:

package dataStructures;

import java.util.NoSuchElementException;

    public interface QueueInterface<E> {
    /**
     * Puts an element into the queue and returns this interface to allow method chaining.
     * 
     * @param element
     *            - A generic element to add to the queue
     * @return QueueInterface to allow method chaining.
     */
    QueueInterface<E> add(E element);

    /**
     * Returns the first element in the queue. Throws an exception if there are no elements in the queue.
     * 
     * @return The first element in the queue
     * @throws NoSuchElementException
     *             When there are no elements in the queue
     */
    E element() throws NoSuchElementException;

    /**
     * Returns the first element, and removes it from the queue. Throws an exception if there are no elements in the queue.
     * 
     * @return The first element in the queue
     * @throws NoSuchElementException
     *             When there are no elements in the queue
     */
    E remove() throws NoSuchElementException;

    /**
     * Attempt to add an element to the queue. Returns true if it was successful.
     * 
     * @param element
     *            - A generic element to add to the queue
     * @return true if the element was added to the queue.
     */
    boolean offer(E element);

    /**
     * @return the first element in the queue. Returns null if the queue is empty.
     */
    E peek();

    /**
     * @return the first element and remove it from the queue. Returns null if the queue is empty.
     */
    E poll();
}

Generic Array:

package dataStructures;

import java.util.NoSuchElementException;

public class GenericArrayQueue<T> implements QueueInterface<T> {
    private T[] data;
    private int front, size, back;

    public final static int DEFAULT_INITIAL_ARRAY_SIZE = 16;
    /**
     * MAX_ARRAY_SIZE is set to Integer.MAX_VALUE - 8 to prevent OutOfMemoryErrors.
     */
    public static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    public GenericArrayQueue() {
        this(DEFAULT_INITIAL_ARRAY_SIZE);
    }

    public GenericArrayQueue(int capacity) throws IllegalArgumentException {
        if (capacity < 1) {
            throw new IllegalArgumentException("Queue capacity must be 1 or greater");
        }

        if (capacity > MAX_ARRAY_SIZE) {
            throw new IllegalArgumentException("Stack capacity is greater then maximum array size");
        }

        // Data variable is private so it will never be returned to the client
        // and the only method that can push elements onto the array would have to be the same type so it is OK
        // to suppress the warning message.
        @SuppressWarnings("unchecked")
        T[] tempData = (T[]) new Object[capacity];
        data = tempData;
    }

    @Override
    public QueueInterface<T> add(T e) throws IllegalArgumentException {
        if (size == data.length) {
            throw new IllegalArgumentException("Ran out of memory to queue");
        }

        data[back] = e;
        back = (back + 1) % data.length;
        size++;
        return this;
    }

    @Override
    public T element() throws NoSuchElementException {
        if (size == 0) {
            throw new NoSuchElementException("Queue does not contain any items.");
        }

        return data[front];
    }

    @Override
    public T remove() throws NoSuchElementException {
        if (size == 0) {
            throw new NoSuchElementException("Queue does not contain any items.");
        }

        size--;
        T output = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        return output;
    }

    @Override
    public boolean offer(T e) {
        if (size == data.length) {
            return false;
        }

        size++;
        data[back] = e;
        back = (back + 1) % data.length;
        return true;
    }

    @Override
    public T peek() {
        return size == 0 ? null : data[front];
    }

    @Override
    public T poll() {
        if (size == 0) {
            return null;
        }

        T output= data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        return output;
    }
}

Generic Linked List:

package dataStructures;

import java.util.NoSuchElementException;

public class GenericLinkedListQueue<E> implements QueueInterface<E> {
    private Node<E> first, last;

    private static class Node<E> {
        private E data;

        private Node<E> back;

        public Node(E element) {
            data = element;
        }
    }

    @Override
    public QueueInterface<E> add(E element) {
        Node<E> newElement = new Node<E>(element);
        if (first == null) {
            first = newElement;
        } else {
            if (first.back == null) {
                first.back = newElement;
            } else {
                last.back = newElement;
            }

            last = newElement;
        }

        return this;
    }

    @Override
    public E element() throws NoSuchElementException {
        if (first == null) {
            throw new NoSuchElementException("Queue does not contain any items.");
        }

        return first.data;
    }

    @Override
    public E remove() throws NoSuchElementException {
        if (first == null) {
            throw new NoSuchElementException("Queue does not contain any items.");
        }

        E output = first.data;
        first = first.back;
        return output;
    }

    @Override
    public boolean offer(E e) {
        // Only way for the offer to return false is if we run out of VM memory.
        add(e);
        return true;
    }

    @Override
    public E peek() {
        return first == null ? null : first.data;
    }

    @Override
    public E poll() {
        if (first == null) {
            return null;
        }

        E output = first.data;
        first = first.back;

        return output;
    }

}

JUnit

package dataStructures;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNotEquals;

import java.util.NoSuchElementException;

import org.junit.Before;
import org.junit.Test;

public class QueueTest {

    QueueInterface<String> queueTest;

    @Before
    public void setUp() throws Exception {
        queueTest = new GenericLinkedListQueue<>();
        // queueTest = new GenericArrayQueue<>();
    }

    @Test
    public void testAdd() {
        queueTest.add("5");
        assertEquals("5", queueTest.element());
        queueTest.add("4");
        assertEquals("5", queueTest.element());
        queueTest.add("3");
        assertEquals("5", queueTest.element());
        queueTest.add("2");
        assertEquals("5", queueTest.element());
        queueTest.add("1");
        assertEquals("5", queueTest.element());

        assertEquals("5", queueTest.remove());
        assertEquals("4", queueTest.remove());
        assertEquals("3", queueTest.remove());
        assertEquals("2", queueTest.remove());
        assertEquals("1", queueTest.remove());
    }

    @Test
    public void testElement() {
        queueTest.add("5");
        assertEquals("5", queueTest.element());
        queueTest.add("4");
        assertEquals("5", queueTest.element());
        queueTest.add("3");
        assertEquals("5", queueTest.element());
        queueTest.add("2");
        assertEquals("5", queueTest.element());
        queueTest.add("1");
        assertEquals("5", queueTest.element());
    }

    @Test(expected = NoSuchElementException.class)
    public void testElementError() {
        queueTest.element();
    }

    @Test
    public void testRemove() {
        queueTest.add("5");
        queueTest.add("4");
        queueTest.add("3");
        queueTest.add("2");
        queueTest.add("1");    

        assertEquals("5", queueTest.remove());
        assertEquals("4", queueTest.remove());
        assertEquals("3", queueTest.remove());
        assertEquals("2", queueTest.remove());
        assertEquals("1", queueTest.remove());
    }

    @Test(expected = NoSuchElementException.class)
    public void testRemoveError() {
        queueTest.remove();
    }

    @Test
    public void testPeek() {
        assertEquals(null, queueTest.peek());
        queueTest.add("5");
        assertNotEquals(null, queueTest.peek());
        queueTest.remove();
        assertEquals(null, queueTest.peek());
    }

    @Test
    public void testPoll() {
        assertEquals(null, queueTest.poll());
        queueTest.add("5");
        assertEquals("5", queueTest.poll());
        assertEquals(null, queueTest.poll());
    }

}
\$\endgroup\$
1
\$\begingroup\$

Compared to your array implementation of Stack (Stack), there are some discrepancies:
1: Your Stack resizes its inner array when it is full, your Queue throws an exception. That's weird. I would expect a Queue to resize as well.

2: Your Stack has a peek() method that throw an exception if the Stack is empty. That's good. Your Queue also has a peek() method, but it returns null instead of throwing.
However, the queue does have a method that throws, but it has a different name: element(). This is very confusing. If two similar classes both have the same method, you might want to be consistent.

I'd say peek() should throw. If someone wants to peek, they should check if the collection is empty. Why have a method that returns null?
It is possible that the queue contains the value null. What if I call peek() and it returns null? What does that mean? Was the queue empty or did it contain the value null? I wouldn't know the difference.

I don't care much for a linked list implementation. Stack and Queue should be implemented with arrays anyway.

\$\endgroup\$
  • \$\begingroup\$ For this implementation I was attempting to use the interface from oracle: link. This is why the array does not resize since that is not what the interface was expecting to do. \$\endgroup\$ – user3610520 Aug 30 '16 at 12:47
  • \$\begingroup\$ @user3610520 I see. That makes sense. But I think the Java collections library is a bit messed up. Queue is an interface when it should be a class, and LinkedList implements Queue. That's weird. \$\endgroup\$ – Dennis_E Aug 30 '16 at 15:01

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.