java - 具有随机删除的 FIFO 队列

Question

实现一个数据类型，支持插入一个item，删除最近最少添加的item，随机删除一个item。每个操作都应该花费恒定的预期摊销时间，并且应该(最多)使用与数据结构中的项目数量成比例的空间。

例如。 1 2 3 4 5 6 -> 1 2 4 5 6

我已经实现了如下的队列，但是现在我不知道如何删除一个具有摊销时间的随机项目，我是否应该在每次随机删除第一个之后有一个随机删除像移动数字时重新排列数组在数组中向前插入？这真的是一种不好的做法吗？还是应该使用链表实现队列？但是我的直觉告诉我链表也需要平均 O(n) 才能从链表的头部到达随机节点。

public class RandomQueue<Item> implements Iterable<Item> {
Item[] items;
int N;
int first;
int last;

public RandomQueue() {
    items = (Item[]) new Object[2];
    N = 0;
    first = last = 0;
}

public static void main(String[] args) {
    RandomQueue<Integer> rd = new RandomQueue<>();
}

public boolean isEmpty() {
    return N == 0;
}

public String toString() {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < N; i++) {
        sb.append(items[(first + i) % items.length]).append(" ");
    }
    return sb.toString();
}

private void resize(int length) {
    Item[] temp = (Item[]) new Object[length];
    for (int i = 0; i < N; i++) {
        temp[i] = items[(first + i) % items.length];
    }
    items = temp;
    first = 0;
    last = N;
}

public void enqueue(Item item) {
    if (N == items.length)
        resize(items.length * 2);
    items[last++] = item;
    if (last == items.length)
        last = 0;
    N++;
}

public Item dequeue() {
    if (isEmpty())
        throw new NoSuchElementException("Queue is empty");
    Item first = items[first];
    items[first] = null;
    N--;

    if (first == items.length)
        first = 0;
    else
        first++;
    if (N > 0 && N == items.length / 4)
        resize(items.length / 2);
    return first;
}
}

Answer 1

这个问题的关键是您不是从队列中删除一个随机项目，而是创建一个排除随机项目的队列。您的程序中应该有一个函数接受队列作为输入并执行以下操作:

1. 创建第二个队列以排除随机删除的项目。
2. 生成一个小于或等于第一个队列总长度的随机数。
3. 创建一个循环，从第一个队列中删除项目并将它们添加到第二个队列。
4. 如果循环中的计数器等于随机数，则不要将其添加到第二个队列。
5. 删除第一个队列并返回第二个队列。