While implementing a randomized queue class for the Princeton Algorithms course, I needed to maintain sequential array keys with non-null values. According to the requirements of the program, I could only use a limited subset of Java standard utilities.

At first, I thought about using iteration to reset the array keys, but that would not allow the performance requirements of the program to be met. The program required that the dequeue and enqueue operations work in constant time but using iteration would mean that they would happen in logarithmic or linear time.

Of course, as with most things, the solution below is simple (but perhaps not easy to come up with on the fly). When dequeue() is called, a random key is picked (via a random number generator), the item for the random key is saved to a variable, the item for the max key is moved to the random key, the item for the max key is set to null, and finally the item for the random key is returned. This is accomplished with just a few operations rather than linear time. Below is a snippet of the method and a full repository with tests is also available.. This code will only work if you don’t care about the order in which the array is maintained.

public String dequeue() {
    // find the keys
    int maxKey = arrayCount - 1;
    int randomKey = randomArrayIndex(arrayCount--);

    // save the entry for the random key
    String string = storage[randomKey];

    // move the max key entry to the random key
    storage[randomKey] = storage[maxKey];

    // remove the entry for the max key
    storage[maxKey] = null;
    return string;
}