它应该是有效的 - 在开始/结束时添加 - 在开始/结束时删除 - 支持随机访问
问问题
495 次
4 回答
4
使用循环缓冲区。空间不足时将尺寸加倍。这将在每个操作的开始/结束时执行插入/删除以及在 O(1) 时间内执行随机访问（摊销）。
在 C++ 中， std::deque 可以在开始/结束时插入/删除以及在 O(1) 中进行随机访问。
于 2012-07-12T20:53:44.450 回答
3
手指树。欣策，拉尔夫；Paterson, Ross (2006)，“手指树：一种简单的通用数据结构”，函数式编程杂志 16 (2): 197–217。
- O(1)访问添加/删除到开始/结束。
- O(log n)随机访问。
看起来有点像：
于 2012-07-12T20:45:34.520 回答
1
Chris Okasaki 的纯功能随机访问列表。类似于 Hinze 的手指树。
于 2012-07-12T20:50:27.293 回答
0
这听起来有点像一个家庭作业问题，所以在澄清之前避免用勺子喂食。
看看一些抽象数据类型。从那里您可以决定哪种数据类型适合您的要求并选择适当的数据结构实现。
于 2012-07-12T20:46:26.923 回答