В настоящее время я работаю над алгоритмами Принстона, часть I. Одним из назначений является реализация рандомизированной очереди. Это вопрос, связанный с реализацией и компромиссом использования разных структур данных.
Вопрос:
Рандомизированная очередь похожа на стек или очередь, за исключением того, что удаленный элемент выбирается равномерно случайным образом из элементов в структуре данных. Создайте общий тип данных RandomizedQueue, который реализует следующий 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
}
Ловушка здесь заключается в реализации операции dequeue и итератора, поскольку dequeue удаляет и возвращает случайный элемент, и итератор выполняет итерацию по очереди в случайном порядке.
1. Реализация массива:
Первичная реализация, которую я рассматривал, представляет собой реализацию массива. Это будет идентично реализации очереди массивов, кроме случайности.
Запрос 1.1: Для операции dequeue я просто произвольно выбираю число из размера массива и возвращаю этот элемент, а затем перемещаю последний элемент в массиве в позицию возвращаемого элемента.
Однако этот подход изменяет порядок очереди. В этом случае это не имеет значения, поскольку я дежурирую в случайном порядке. Тем не менее, мне было интересно, есть ли время/память эффективный способ удаления из случайного элемента из массива при сохранении порядка очереди без необходимости создания нового массива и переноса всех данных на него.
// 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;
}
Запрос 1.2: для того, чтобы итератор выполнял требование случайного возврата элементов, я создаю новый массив со всеми индексами очереди, затем перетасовываю массив с помощью операции Knuth shuffle и возвращаю элементы в этих конкретных индексах в очереди. Однако это связано с созданием нового массива, равного длине очереди. Опять же, я уверен, что мне не хватает более эффективного метода.
2. Внедрение внутреннего класса
Вторая реализация включает в себя класс внутренних узлов.
public class RandomizedQueue<Item> {
private static class Node<Item> {
Item item;
Node<Item> next;
Node<Item> previous;
}
}
Запрос 2.1. В этом случае я понимаю, как эффективно выполнять операцию dequeue: вернуть случайный узел и изменить ссылки для соседних узлов.
Однако я смущен тем, как вернуть итератор, который возвращает узлы в случайном порядке, без необходимости создавать целую новую очередь с узлами, прикрепленными в случайном порядке.
Кроме того, каковы преимущества использования такой структуры данных над массивом, отличной от читаемости и простоты реализации?
Этот пост длинный. Я ценю, что вы, ребята, нашли время, чтобы прочитать мой вопрос и помочь мне. Благодарю!
