问题标签 [deque]

我需要构建自己的双端队列，因为我编程的环境没有这样的东西。关于如何实现它，我发现自己在两种选择之间徘徊：

• 我可以管理一个可增长的指向包含数据的数组的指针数组。问题是，如何确定每个辅助数组的大小？
• 我可以拥有一个定期增长的大型缓冲区，并在其上构建一个循环队列。这在一定大小之后似乎很糟糕，因为大分配变得更难有效地实现。

有任何想法吗？

我想知道是否有人知道如何锁定数据库，然后将等待的作业出队。所以我在数据库中有一个哈希表，并且我将数据存储在数据库中，多个用户同时发送请求以编辑该数据，但数据需要在所有用户之间保持不变，并且只有一个用户可以访问/编辑一次。

谢谢一堆=）

为什么ArrayLists 通常不实现为双端，这将支持在前面和后面的快速分期插入？

使用后者比使用前者有什么缺点吗？

（我不只是在谈论 Java——我还没有看到双端数组列表是任何其他语言的默认设置，但 Java 只是一个很好的例子。）

*编辑：我最初称它们为“数组双端队列”，但这是我的误解；我说的不是队列，而是双端数组列表。

我试图理解为什么 Java 的 ArrayDeque 比 Java 的 LinkedList 更好，因为它们都实现了 Deque 接口。

我几乎看不到有人在他们的代码中使用 ArrayDeque。如果有人对 ArrayDeque 的实现方式有更多的了解，那将会很有帮助。

如果我理解它，我会更有信心使用它。我无法清楚地理解 JDK 实现管理头尾引用的方式。

我最近开始研究如何在 Python 中实现各种数据结构，以使我的代码更高效。在调查列表和双端队列的工作方式时，我发现当我想要转移和取消转移时，我可以获得好处，将列表中的 O(n) 时间减少到双端队列中的 O(1)（列表被实现为具有每次在前面插入东西时都要完全复制，等等......）。我似乎找不到的是如何实现双端队列的细节，以及它的缺点与列表的细节。有人可以在这两个问题上启发我吗？

我正在查看 STL 容器并试图弄清楚它们到底是什么（即使用的数据结构），而双端队列阻止了我：我起初以为它是一个双链表，它允许从两端插入和删除恒定时间，但我对运算符 []承诺在恒定时间内完成感到困扰。在链表中，任意访问应该是 O(n)，对吧？

如果它是一个动态数组，它怎么能在恒定时间内添加元素呢？应该提到的是，可能会发生重新分配，并且 O(1) 是摊销成本，就像 vector 一样。

所以我想知道这个结构是什么，它允许在恒定时间内任意访问，同时永远不需要移动到一个新的更大的地方。

我知道一般准则是在 uitableviewcell 中离开屏幕时将单元格出列。

当您将 uitableview 用作表单并且其中可能有不同类型的 uitableviewcells 时，我认为此建议/指南会放宽。

例如标签/文本字段、标签/uiswitch、标签/标签/uidatepicker。

就我而言，这样的表格视图仅限于 4-5 个单元格。

我们是否需要担心基于表单（4-5 个单元格）的表格视图的出队？

当面对一个包含不同类型单元格的表格视图时，你们会怎么做？

如何在 windbg 中找到 STL 双端队列容器的元素计数？

似乎 !stl 扩展不支持双端队列。我试过研究数据结构的内部结构，但没有找到一个明显的元素计数成员变量。

我有一个不可重现问题的内存转储，所以记录不是我的选择。

标准说，如果数据结构具有随机访问权限，那么std::binary_search(...)这两个相关函数std::lower_bound(...)和std::upper_bound(...)是 O(log n)。因此，鉴于此，我假设这些算法具有 O(log n) 性能std::deque（假设其内容由用户保持排序）。

但是，似乎 的内部表示std::deque很棘手（它被分成块），所以我想知道： O(log n) 搜索的要求是否适用于std::deque.

我已经实现了一个简单的统计引擎，使用双端队列返回滚动均值和方差，以提供数据队列。

双端队列由与滚动值数量相等的条目数构成。

当一个新值到达时，最旧的值会从前面弹出，新的值会被推到后面。

我需要确保它不会在内存中增长，因为它预计会作为后台任务运行很长时间。

双端队列是否在使用中的堆上分配？有没有可以用来修复其大小的标志？

我在 RHEL 5.3 上使用 G++ 4.1.2