9

我正在寻找 Java 解决方案，但任何一般性的答案也可以。

Vector/ArrayList 对于追加和检索是 O(1)，但对于 prepend 是 O(n)。

LinkedList（在 Java 中实现为双向链表）对于追加和前置是 O(1)，但对于检索是 O(n)。

对于上述所有内容，双端队列 (ArrayDeque) 为 O(1)，但无法检索任意索引处的元素。

在我看来，满足上述要求的数据结构内部有 2 个可增长列表（一个用于前置，一个用于附加），并且还存储一个偏移量以确定在检索期间从何处获取元素。

4

6 回答 6

9

您正在寻找一个双端队列。正如您所指出的，这是在 C++ STL 中以您想要的方式实现的，即您可以对其进行索引，但在 Java 中则不行。您可以通过使用两个数组并存储“零”所在的位置来从标准组件中推出自己的组件。如果你最终从零开始移动很长一段路，这可能会浪费内存，但如果你走得太远，你可以变基并允许双端队列爬入一个新数组。

一个更优雅的解决方案，在管理两个数组时不需要太多花哨的东西，就是将一个循环数组强加到一个预先分配的数组上。这将需要实现 push_front、push_back 和调整其后面的数组的大小，但调整大小等的条件会更清晰。

于 2009-06-12T04:15:15.410 回答
5

可以实现双端队列（双端队列）以在 O(1) 时间内提供所有这些操作，尽管并非所有实现都这样做。我从来没有使用过 Java 的 ArrayDeque，所以我以为你在开玩笑说它不支持随机访问，但你说得对——作为一个“纯”双端队列，它只允许在末端轻松访问。我明白为什么，但这确实很烦人......

对我来说，实现超快双端队列的理想方法是使用循环缓冲区，特别是因为您只对在前后添加删除感兴趣。我没有立即意识到 Java 中的一个，但我已经在 Objective-C 中编写了一个作为开源框架的一部分。欢迎您按原样使用代码或作为实现您自己的模式的模式。

这是代码和相关文档的WebSVN 门户。真正的内容在CHAbstractCircularBufferCollection.m文件中 — 查找和方法。甚至还定义了一个自定义枚举器（Java 中的“迭代器”）。基本的循环缓冲区逻辑相当简单，并在以下 3 个集中式宏中捕获：appendObject:prependObject:#define

#define transformIndex(index) ((headIndex + index) % arrayCapacity)
#define incrementIndex(index) (index = (index + 1) % arrayCapacity)
#define decrementIndex(index) (index = ((index) ? index : arrayCapacity) - 1)

正如您在该方法中所见，objectAtIndex:访问双端队列中的第 N 个元素所需要做的就是array[transformIndex(N)]. 请注意，我tailIndex总是指向最后一个存储元素之外的一个插槽，因此如果headIndex == tailIndex，则数组已满，如果大小为 0，则数组为空。

希望有帮助。我很抱歉发布非 Java 代码，但问题作者确实说一般答案是可以接受的。

于 2009-06-12T05:25:55.553 回答
3

如果您将附加到 Vector/ArrayList 视为 O(1) - 它确实不是，但在实践中可能足够接近 -
（编辑 - 澄清 - 附加可能是摊销常数时间，也就是说 - 平均而言，加法将是 O(1)，但在尖峰时可能会更糟。根据上下文和所涉及的确切常量，这种行为可能是致命的）。

（这不是 Java，而是一些虚构的语言......）。

一个将被称为“前进”的向量。第二个向量将被称为“Backwards”。

当被要求附加 - Forward.Append()。

当被要求添加 - Backwards.Append()。

当被要求查询时-

if ( Index < Backwards.Size() )
{
    return Backwards[ Backwards.Size() - Index - 1 ]
}
else
{
    return Forward[ Index - Backwards.Size() ]
}

（并检查索引是否超出范围）。

于 2009-06-12T04:24:39.380 回答
2

你的想法可能会奏效。如果这些是您需要支持的唯一操作，那么您只需要两个向量（称为头和尾）。前置，你追加到头部，追加，你追加到尾部。访问一个元素，如果索引小于head.Length，则返回head[head.Length-1-index]，否则返回tail[index-head.Length]。所有这些操作显然都是 O(1)。

于 2009-06-12T04:14:27.860 回答
1

这是一个支持 O(1) 附加、前置、第一个、最后一个和大小的数据结构。我们可以轻松地添加其他方法，AbstractList<A>例如deleteupdate

import java.util.ArrayList;

public class FastAppendArrayList<A> {
    private ArrayList<A> appends = new ArrayList<A>();
    private ArrayList<A> prepends = new ArrayList<A>();

    public void append(A element) {
        appends.add(element);
    }

    public void prepend(A element) {
        prepends.add(element);
    }

    public A get(int index) {
        int i = prepends.size() - index;
        return i >= 0 ? prepends.get(i) : appends.get(index + prepends.size());
    }

    public int size() {
        return prepends.size() + appends.size();
    }

    public A first() {
        return prepends.isEmpty() ? appends.get(0) : prepends.get(prepends.size());
    }

    public A last() {
        return appends.isEmpty() ? prepends.get(0) : appends.get(prepends.size());
    }
于 2016-02-05T19:11:18.797 回答
0

你想要的是一个deque像 STL 一样的双端队列 ( )，因为 Java出于某种原因ArrayDeque缺少它。get()这里有一些很好的建议和实现链接：

于 2009-06-12T04:30:41.987 回答