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.

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)