如何在固定时间O(1)内清空循环数组队列

Question

我正在尝试找到一种方法来实现一种高效的clear，以便在固定时间内清除循环数组队列。

我尝试了Array.fill()并用null值填充了数组，但它仍然需要遍历数组，这意味着O(n)。

Answer 1

我想说，这个问题的答案在一定程度上取决于你的需求，以及什么是常量操作。

1. 一种方法是创建一个具有固定大小(即O(1))的新数组，并丢弃对旧数组的引用，然后将指针重置为它们的初始值。
2. 另一种方法可能是初始化一个与当前存储元素的数组大小相同的新数组，并丢弃对旧数组的引用。这可能是constant time operation.
3. The的第三种方法，也就是用户Jordan在您问题的评论部分建议的方法。只需移动head和tail指针即可。但是，请注意，这不会清除对数组中(可能是重量级的)对象的引用，这可能会导致应用程序中的内存泄漏，因为仍然存储在其中的对象不能被垃圾回收。

查看ArrayDeque (基本上只是一个循环数组队列)的clear操作的实现，您可以看到它通过以下两个操作使用O(n)方法：(1)清空元素，(2)重置指针。

/**
 * Removes all of the elements from this deque.
 * The deque will be empty after this call returns.
 */
public void clear() {
    circularClear(elements, head, tail);
    head = tail = 0;
}

/**
 * Nulls out slots starting at array index i, upto index end.
 * Condition i == end means "empty" - nothing to do.
 */
private static void circularClear(Object[] es, int i, int end) {
    // assert 0 <= i && i < es.length;
    // assert 0 <= end && end < es.length;
    for (int to = (i <= end) ? end : es.length;
         ; i = 0, to = end) {
        for (; i < to; i++) es[i] = null;
        if (to == end) break;
    }
}