Java Implementation of Random Array Queue

Question

4.3.37 Random queue. A random array queue is a collection that supports the following API:

Write a class RandomQueue that implements this API. Hint : Use a resizing array. To remove an item, swap one at a random position (indexed 0 through n-1) with the one at the last position (index n-1). Then, remove and return the last item, as in ResizingArrayStack. Write a client that prints a deck of cards in random order using RandomQueue.

Implementing Steps

In this solution, the implementation also follows the pattern of Queue, First In First Out (FIFO). The only difference is swapping the first item with a random item in the same queue before pop out that item.

Here goes the steps:

1. Create a resizing array queue.
2. Create a item swap method.
3. Rewrite the dequeue with that item swap method.

Code Example

/******************************************************************************
 *  Compilation:  javac RandomArrayQueue.java
 *  Execution:    java RandomArrayQueue
 *
 ******************************************************************************/

import java.util.NoSuchElementException;
import java.util.Iterator;

class RandomArrayQueue<Item> implements Iterable<Item> {
    private int size;
    private Item[] items;
    private int first;
    private int last;

    private void resize(int capacity) {
        assert capacity >= size;
        Item[] temp = (Item[]) new Object[capacity];
        for (int i = 0; i < size; i++) {
            temp[i] = items[(first + i) % items.length];
        }

        items = temp;

        first = 0;
        last  = size;
    }

    public RandomArrayQueue() {
        this(2);
    }

    public RandomArrayQueue(int capacity) {
        items = (Item[])new Object[capacity];
        size = 0;
        first = 0;
        last = 0;
    }

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

    public void enqueue(Item item) {
        if (size == items.length) {
            resize(items.length * 2);
        }

        items[last++] = item;

        if (last == items.length) {
            last = 0;
        }

        size++;
    }

    public Item dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue underflow");
        }

        Item item = items[first];
        items[first] = null;
        size--;
        first++;

        if (first == items.length) {
            first = 0;
        }

        if (size > 0 && size == items.length / 4) {
            resize(items.length / 2);
        }

        return item;
    }

    private void swap(int left, int right) {
        Item temp = items[right];
        items[right] = items[left];
        items[left] = temp;
    }

    public Item randomDequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue underflow");
        }

        int index;
        if (last > first) {
            index = (int) (Math.random() * (last - first));
        } else {
            int length = last + items.length - first;
            index = (first + (int) (Math.random() * length)) % items.length;
        }

        swap(first + index, first);
        return dequeue();
    }

    public Item sample() {
        if (isEmpty())
            throw new java.util.NoSuchElementException();

        int index = (int) (Math.random() * size);
        return items[index];
    }

    public int size() {
        return size;
    }

    public Iterator<Item> iterator() {
        return new ArrayIterator();
    }

    private class ArrayIterator implements Iterator<Item> {
        private int i = 0;
        public boolean hasNext()  {
            return i < size;
        }
        public void remove()      {
            throw new UnsupportedOperationException();
        }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = items[(i + first) % items.length];
            i++;

            return item;
        }
    }

    public String toString() {
        StringBuilder str = new StringBuilder();
        for (Item item : this) {
            str.append(item);
            str.append(' ');
        }
        return str.toString();
    }

    public String debug() {
        StringBuilder str = new StringBuilder();
        for (Item item : items) {
            str.append(item);
            str.append(' ');
        }
        return str.toString();
    }

    public static void main(String[] args) {
        RandomArrayQueue<String> queue = new RandomArrayQueue<String>();
        queue.enqueue("a");
        queue.enqueue("b");
        queue.enqueue("c");
        queue.enqueue("d");
        queue.enqueue("e");
        queue.enqueue("f");
        queue.enqueue("g");

        System.out.println("Debug Queue: " + queue.debug());

        System.out.println("Random Dequeue: " + queue.randomDequeue());
        System.out.println("Debug Queue: " + queue.debug());

        System.out.println("dequeue: " + queue.dequeue());
        System.out.println("dequeue: " + queue.dequeue());
        System.out.println("Debug Queue: " + queue.debug());

        queue.enqueue("h");
        queue.enqueue("i");
        System.out.println("enqueue: h");
        System.out.println("enqueue: i" );

        System.out.println("Debug Queue: " + queue.debug());
        System.out.println("Print Queue: " + queue.toString());

    }
}

Output

-> java RandomArrayQueue
Debug Queue: a b c d e f g null
Random Dequeue: d
Debug Queue: null b c a e f g null
dequeue: b
dequeue: c
Debug Queue: null null null a e f g null
enqueue: h
enqueue: i
Debug Queue: i null null a e f g h
Print Queue: a e f g h i

To compare the difference between Random Dequeue and Dequeue, the original dequeue method is kept as dequeue and the Random Dequeue method name is randomDequeue.

From the first 4 lines, you can see the Random Dequeue didn't return a, but d. And the a was placed to the positon of d.