Implementation of a Resizing Array Queue

Question

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[1];
 private int head;
 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];
 int curr = head;
 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);
 head = 0;
 tail = N-1;
 }
 if (isEmpty()) {
 head = tail = 0;
 } else if (tail == a.length-1) {
 tail = 0;
 } else {
 tail++;
 }
 a[tail] = element;
 N++;
 }
 public E dequeue() {
 if (isEmpty())
 throw new RuntimeException();
 E element = a[head];
 a[head] = null;
 N--;
 if (head == a.length-1) {
 head = 0;
 } else {
 head++;
 }
 if (N == a.length/4) {
 resize(a.length/2);
 head = 0;
 tail = N-1;
 }
 return element;
 }
 @Override
 public Iterator<E> iterator() {
 return new ArrayIterator();
 }
 private class ArrayIterator implements Iterator<E> {
 int curr = head;
 @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";
 return String.format(formatStr, this.head, this.tail, Arrays.toString(this.a));
 }
}

Answer 1

Advice 1

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

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.

Advice 2

private int N;

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

Advice 3

private void resize(int cap) {
 E[] temp = (E[]) new Object[cap];
 int curr = head;
 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.head = 0;
 this.tail = size;
}

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

Advice 4

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 head;
 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);
 }
 E element = array[head];
 head = (head + 1) & (array.length - 1);
 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.head = 0;
 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[0].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[0].trim().toLowerCase().equals("push")) {
 queue.enqueue(tokens[1].trim());
 }
 }
 }
 }
}

Hope that helps.

• albertjorlando: Thank you, I didn't consider bit operations or modular arithmetic. This definitely yields a cleaner solution.

Answer 2

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[1];
 ^
 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)