java - 有没有办法为 ArrayDeque 实现 O(1) 时间复杂度的检索 (get())？

Question

我正在尝试将 ArrayDeque 用于一个应该对 addfront、addback 和检索具有 O(1) 时间复杂度的类。我只能想到使用 toArray() 进行检索，不幸的是 O(n)。有没有办法为 ArrayDeque 实现 O(1) 的检索方法？

Answer 1

不。

我查看了 的源代码ArrayDeque，没有任何地方可以通过索引访问任意数组元素的方法。为了使操作在 O(1) 中执行，这将是必需的。

不过，实现您自己的满足您要求的类应该不会太难。搜索“循环缓冲区”。如果您的数组溢出，请将整个内容复制到一个双倍大小的新数组中。当然，这不能在常数时间内完成，但添加仍将在摊销常数时间内完成，与 for 相同ArrayDeque。

我假设get()您的意思是通过从前面或从后面计算的队列中的位置/索引来检查（不删除）元素。

编辑

我想另一种方法是使用数组并找到一种使 addfront 恒定时间的方法，但我不确定如何

这是一个简单的实现。请根据您的需要进一步开发。这些想法是使用循环缓冲区并在旧数组太小时复制到新数组。我相信ArrayDeque使用相同的想法。

public class MyArrayDeque<E> {

    private Object[] elements;
    
    // Index to first element.
    private int front = 0;
    // Index to first free space after last element.
    // back == front means queue is empty (not full).
    private int back = 0;
    
    public MyArrayDeque(int initialCapacity) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("Initial capacity must not be negative");
        }
        // There’s always at least 1 free space, so add 1 to have room for initialCapacity elements
        elements = new Object[initialCapacity + 1];
    }

    public void addFront(E elem) {
        checkCapacity();
    
        if (front == 0) {
            front = elements.length - 1;
        } else {
            front--;
        }
        
        elements[front] = elem;
    }

    public void addBack(E elem) {
        checkCapacity();
        
        elements[back] = elem;

        if (back == elements.length - 1) {
            back = 0;
        } else {
            back++;
        }
    }

    // Makes sure the queue has room for one more element.
    private void checkCapacity() {
        boolean needToExpand;
        if (front == 0) {
            needToExpand = back == elements.length - 1;
        } else {
            needToExpand = back == front - 1;
        }
        if (needToExpand) {
            Object[] newElements = new Object[elements.length * 2];
            if (front <= back) {
                int size = back - front;
                System.arraycopy(elements, front, newElements, 0, size);
                front = 0;
                back = size;
            } else {
                int numberOfElementsToCopyFirst = elements.length - front;
                System.arraycopy(elements, front, newElements, 0, numberOfElementsToCopyFirst);
                System.arraycopy(elements, 0, newElements, numberOfElementsToCopyFirst, back);
                front = 0;
                back = numberOfElementsToCopyFirst + back;
            }
            elements = newElements;
        }
    }

    /** Gets the ith element counted from the front without removing it. */
    public E get(int i) {
        int index = front + i;
        if (index >= elements.length) {
            index -= elements.length;
        }
        boolean outOfRange;
        if (front <= back) {
            outOfRange = index < front || index >= back;
        } else {
            outOfRange = index >= back && index < front;
        }
        if (outOfRange) {
            throw new ArrayIndexOutOfBoundsException(i);
        }
        return getInternal(index);
    }

    @SuppressWarnings("unchecked")
    private E getInternal(int index) {
        return (E) elements[index];
    }

}

对于一个简单的演示：

    MyArrayDeque<String> queue = new MyArrayDeque<>(1);
    
    queue.addFront("First element added");
    queue.addBack("Added at back");
    queue.addFront("Added at front");
    
    System.out.println(queue.get(1));

输出是：

添加的第一个元素

Answer 2

ArrayDequeAPI 没有提供任何方法来做到这一点。

但是，您可以编写ArrayDeque该 implements的自定义子类get。像这样的东西：

public E get(int i) {
    if (i < 0 || i > size()) {
        throw new ....("out of bounds");
    }
    long pos = this.head + i; 
    if (pos >= this.elements.length) {
        pos -= this.elements.length;
    }
    return this.elements[(int) pos];
}

注意：此代码尚未编译/调试。使用风险自负！

这对APIO(1)中现有操作的性能没有影响。ArrayDeque

---

更新

以上内容不能作为标准ArrayDeque类的子类，因为它正在访问的字段是包私有的。但是，您可以复制原始类并将上述方法添加到副本中。

（只需确保从 OpenJDK 代码库复制代码，并满足 GPLv2 要求。）

Answer 3

您可以使用额外的结构来实现它，因此空间复杂度将变为 O(2n)，这可能不是很重要。我可以建议的方法是使用 HashMap 并在那里存储您放入队列的 Object 的索引和链接。此外，您需要跟踪可用的第一个和最后一个索引。每次您必须按索引访问元素时 - 您必须根据起始索引计算移位。当然，每次从队列中添加或删除元素时，您都必须注意更新开始和结束索引。唯一的缺点 - 从中​​间移除可能需要 O(n)，这对于队列情况可能并不重要。这是使用附加结构时对象状态的示例：

indexMap: {}
startIndex:0
endIndex:0

--> add an element to the head 
newCalculatedIndex = startIndex == endIndex ? startIndex : startIndex -1; 
//newCalculatedIndex = 0 
indexMap: {(0,'A')}
startIndex:0
endIndex:0

--> add an element to the head 
//newCalculatedIndex = 0-1 = -1
indexMap: {(-1,'B'), (0,'A')}
startIndex:-1
endIndex:0

--> add an element to the tail 
newCalculatedIndex = startIndex == endIndex ? endIndex : endIndex + 1; 
//newCalculatedIndex = 0 + 1 = 1
indexMap: {(-1,'B'), (0,'A'), (1,'C')}
startIndex:-1
endIndex:1

--> Access element with index 2:
calculatedIndex = -1 + 2 = 1 -> indexMap.get(1) returns 'C'