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