I am currently working on Princeton's Algorithms Part I. One of the assignments is to implement a randomized queue. This is a question regarding the implementation and tradeoffs of using different data structures.
Question:
A randomized queue is similar to a stack or queue, except that the item removed is chosen uniformly at random from items in the data structure. Create a generic data type RandomizedQueue that implements the following API:
public class RandomizedQueue<Item> implements Iterable<Item> {
public RandomizedQueue() // construct an empty randomized queue
public boolean isEmpty() // is the queue empty?
public int size() // return the number of items on the queue
public void enqueue(Item item) // add the item
public Item dequeue() // remove and return a random item
public Item sample() // return (but do not remove) a random item
public Iterator<Item> iterator() // return an independent iterator over items in random order
public static void main(String[] args) // unit testing
}
The catch here is to implement the dequeue operation and the iterator since the dequeue removes and returns a random element and the iterator iterates over the queue in a random order.
1. Array Implementation:
The primary implementation I was considering is an array implementation. This will be identical to the implementation of an an array queue except the randomness.
Query 1.1: For the dequeue operation, I simply select a number randomly from the size of the array and return that item, and then move the last item in the array to the position of the returned item.
However, this approach changes the order of the queue. In this case it does not matter since I am dequeuing in random order. However, I was wondering if there was an time/memory efficient way to dequeue a random element from the array while preserving the order of the queue without having to create a new array and transfer all the data to it.
// Current code for dequeue - changes the order of the array after dequeue
private int[] queue; // array queue
private int N; // number of items in the queue
public Item dequeue() {
if (isEmpty()) throw NoSuchElementException("Queue is empty");
int randomIndex = StdRandom.uniform(N);
Item temp = queue[randomIndex]
if (randomIndex == N - 1) {
queue[randomIndex] = null; // to avoid loitering
} else {
queue[randomIndex] = queue[N - 1];
queue[randomIndex] = null;
}
// code to resize array
N--;
return temp;
}
Query 1.2: For the iterator to meet the requirement of returning elements randomly, I create a new array with all the indices of the queue, then shuffle the array with a Knuth shuffle operation and return the elements at those particular indices in the queue. However, this involves creating a new array equal to the length of the queue. Again, I am sure I am missing a more efficient method.
2. Inner Class Implementation
The second implementation involves an inner node class.
public class RandomizedQueue<Item> {
private static class Node<Item> {
Item item;
Node<Item> next;
Node<Item> previous;
}
}
Query 2.1. In this case I understand how to perform the dequeue operation efficiently: Return a random node and change the references for the adjacent nodes.
However, I am confounded by how to return a iterator that returns the nodes in random order without having to create a whole new queue with nodes attached in random order.
Further, what are the benefits of using such a data structure over an array, other than readability and ease of implementation?
This post is kind of long. I appreciate that you guys have taken the time to read my question and help me out. Thanks!
