# Implementation of a Resizing Array Queue

Below is a problem from Sedgewick's Algorithms and my solution. Any thoughts or suggestions for improvement would be much appreciated.

Develop a class that implements the queue abstraction with a fixed-sized array, and then extend your implementation to use array resizing.

package chapter_1_3_bagsQueuesStacks;

import java.util.Arrays;
import java.util.Iterator;

// Exercise 1.3.14 | pg. 163
public class ArrayQueue<E> implements Iterable<E> {
private E[] a = (E[]) new Object;
private int tail;
private int N;

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

private boolean isFull() {
return N == a.length;
}

public int size() {
return N;
}

private void resize(int cap) {
E[] temp = (E[]) new Object[cap];
for (int i = 0; i < N; i++) {
temp[i] = a[curr];
if (curr == a.length-1) {
curr = 0;
} else {
curr++;
}
}
a = temp;
}

public void enqueue(E element) {
if (isFull()) {
resize(a.length*2);
tail = N-1;
}

if (isEmpty()) {
} else if (tail == a.length-1) {
tail = 0;
} else {
tail++;
}

a[tail] = element;
N++;

}

public E dequeue() {
if (isEmpty())
throw new RuntimeException();

N--;

} else {
}

if (N == a.length/4) {
resize(a.length/2);
tail = N-1;
}

return element;
}

@Override
public Iterator<E> iterator() {
return new ArrayIterator();
}

private class ArrayIterator implements Iterator<E> {

@Override
public boolean hasNext() {
return a[curr] != null;
}

@Override
public E next() {
E element = a[curr++];
return element;
}

}

@Override
public String toString() {
String formatStr = "HEAD: %s - TAIL: %s - %s";
}

}


private E[] a = (E[]) new Object;


I suggest that you start from a larger power of two (say 8), since it is not common to deal with only one element in a data structure. Also, a capacity that is a power of two will allow you to omit remainder operator % and use bit operations instead. Namely, say, index % size is the same as index & (size - 1) whenever size is a power of two.

private int N;


Usually, Java developers start field names with a lower case character. However, I suggest that you rename it to size.

private void resize(int cap) {
E[] temp = (E[]) new Object[cap];
for (int i = 0; i < N; i++) {
temp[i] = a[curr];
if (curr == a.length-1) {
curr = 0;
} else {
curr++;
}
}
a = temp;
}


You can write this as

private void resize(int capacity) {
@SuppressWarnings("unchecked")
E[] newArray = (E[]) new Object[capacity];

for (int i = 0; i < size; ++i) {
newArray[i] = array[(head + i) & (array.length - 1)];
}

this.array = newArray;
this.tail = size;
}


Note how the fields are updated in the method itself. You don't have to repeat yourself when contracting as well.

I suggest you add a modification count in your iterator so that it fails as soon as another thread interferes.

Alternative implementation

package chapter_1_3_bagsQueuesStacks;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Scanner;

public class ArrayQueue<E> implements Iterable<E> {

private static final int MINIMUM_CAPACITY = 4;

@SuppressWarnings("unchecked")
private E[] array = (E[]) new Object[MINIMUM_CAPACITY];
private int tail;
private int size;
private int modificationCount;

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

public int size() {
return size;
}

public void enqueue(E element) {
if (isFull()) {
resize(2 * array.length);
}

array[tail] = element;
tail = (tail + 1) & (array.length - 1);
size++;
modificationCount++;
}

public E dequeue() {
if (isEmpty()) {
throw new RuntimeException("ArrayQueue is empty.");
}

if (size < array.length / 4 && size >= 2 * MINIMUM_CAPACITY) {
resize(array.length / 2);
}

size--;
modificationCount++;
return element;
}

@Override
public Iterator<E> iterator() {
return new ArrayQueueIterator();
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");
String separator = "";

for (int i = 0; i < size; ++i) {
sb.append(separator);
separator = ", ";
sb.append(array[(head + i) & (array.length - 1)]);
}

return sb.append("] capacity = " + array.length).toString();
}

private boolean isFull() {
return size == array.length;
}

private void resize(int capacity) {
@SuppressWarnings("unchecked")
E[] newArray = (E[]) new Object[capacity];

for (int i = 0; i < size; ++i) {
newArray[i] = array[(head + i) & (array.length - 1)];
}

this.array = newArray;
this.tail = size;
}

private final class ArrayQueueIterator implements Iterator<E> {

private int iterated = 0;
private final int expectedModificationException =
ArrayQueue.this.modificationCount;

@Override
public boolean hasNext() {
checkModificationCount();
return iterated < size;
}

@Override
public E next() {
if (!hasNext()) {
throw new NoSuchElementException(
"No more elements to iterate.");
}

return array[(head + iterated++) & (array.length - 1)];
}

private void checkModificationCount() {
if (expectedModificationException !=
ArrayQueue.this.modificationCount) {
throw new ConcurrentModificationException();
}
}
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
ArrayQueue<String> queue = new ArrayQueue<>();

for (int i = 0; i < 16; ++i) {
queue.enqueue("" + i);
}

while (true) {
String command = scanner.nextLine();
String[] tokens = command.split("\\s+");

switch (tokens.length) {
case 1:

switch (tokens.trim().toLowerCase()) {
case "print":
System.out.println(queue);
break;

case "pop":
System.out.println(queue.dequeue());
break;

case "quit":
return;
}

break;

case 2:

if (tokens.trim().toLowerCase().equals("push")) {
queue.enqueue(tokens.trim());
}
}
}
}
}


Hope that helps.

• Thank you, I didn't consider bit operations or modular arithmetic. This definitely yields a cleaner solution. – albertjorlando Sep 20 '17 at 23:20

The code does not compile cleanly. Use @SuppressWarnings("unchecked") if necessary.

$javac -Xlint:unchecked ArrayQueue.java ArrayQueue.java:8: warning: [unchecked] unchecked cast private E[] a = (E[]) new Object; ^ required: E[] found: Object[] where E is a type-variable: E extends Object declared in class ArrayQueue ArrayQueue.java:26: warning: [unchecked] unchecked cast E[] temp = (E[]) new Object[cap]; ^ required: E[] found: Object[] where E is a type-variable: E extends Object declared in class ArrayQueue 2 warnings  This test would crash: public class ArrayQueueTest { public static void main(String[] args) { ArrayQueue<Integer> q = new ArrayQueue<>(); q.enqueue(1); for (Integer n : q) { System.out.println(n); } } }  1 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 1 at ArrayQueue$ArrayIterator.hasNext(ArrayQueue.java:93)
at ArrayQueueTest.main(ArrayQueueTest.java:5)