c++ - 双端队列实现选项

Question

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

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

有任何想法吗？

Answer 1

对于您的第一个选项，您可以在分配它们时将每个数组的大小简单地增加一倍，可能达到某个上限，该上限取决于您对应用程序或内存限制的了解。

第二个你似乎已经想通了。

为什么不只是一个简单的双向链表？您需要快速随机访问吗？

Answer 2

另一种方法可能是拥有向量列表（固定大小）。列表作为第一个 DS 的好处是您可以在头部和尾部以及它们之间添加元素。具有固定大小向量的好处是您可以模拟二维数组，其中行的添加/删除是恒定时间。现在假设你想添加头部。您应该在头部（ const time ）的列表中添加一个节点，然后在固定大小向量的最后添加条目。因此，当出队已经有数据时，请考虑前面的任何条目，您将插入第一行的最后一列。如果行中有可用空间，则任何进一步的插入都将发生在第一行的倒数第二个未填充列。否则重复相同的步骤。末尾的正常插入通常发生在列表向量的末尾，其中插入从向量的开头发生。

Answer 3

我会结合你的两个选项 - 多个较小的缓冲区并让每个“结束”指向另一个，基本上成为一个更大的圆形数组。这样你就不需要经常分配缓冲区了。至于二级缓冲区的大小，我认为 Collin 的建议是一个很好的建议——随你增加大小。