数据结构 - 随机队列

我目前正在研究普林斯顿算法第一部分的队列作业。其中一个分配是实现随机队列。这是一个关于使用不同数据结构的实现和权衡的问题。

问题：

随机队列类似于堆栈或队列，不同之处在于从数据结构中的项中统一随机选择删除的项。创建实现以下 API 的通用数据类型 RandomizedQueue：

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
}

这里的要点是实现取消排队操作和迭代器，因为取消排队会删除并返回一个随机元素，并且迭代器会以随机顺序迭代队列。

1. 阵列实现：

我考虑的主要实现是数组实现。这将与数组队列的实现相同，只是随机性。

查询 1.1：对于取消排队操作，我只需从数组的大小中随机选择一个数字并返回该项目，然后将数组中的最后一个项目移动到返回项目的位置。

但是，此方法会更改队列的顺序。在这种情况下，这并不重要，因为我是按随机顺序排队的。但是，我想知道是否有一种时间/内存有效的方法可以从数组中取消随机元素的排队，同时保持队列的顺序，而无需创建新数组并将所有数据传输到它。

// 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.在这种情况下，我了解如何有效地执行取消排队操作：返回一个随机节点并更改相邻节点的引用。

但是，我对如何返回一个以随机顺序返回节点的迭代器感到困惑，而不必创建一个以随机顺序附加节点的全新队列。

此外，除了可读性和易于实现之外，在数组上使用这样的数据结构还有什么好处？

这篇文章有点长。我很感激你们花时间阅读我的问题并帮助我。谢谢！