3
\$\begingroup\$

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

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

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.

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

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)
\$\endgroup\$

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.