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