随机删除的java FIFO队列
实现一种数据类型，支持插入项、删除最近添加的项和删除随机项。每个操作的预期摊销时间应为常数，并且应使用与数据结构中的项目数成比例的空间（最多）
例如：123456->；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;
}
}
# 1 楼答案
这个问题的关键在于，您没有从队列中删除随机项，而是创建了一个排除随机项的队列。您的程序中应该有一个函数，该函数接受队列作为输入，并执行以下操作：