双端队列实现选项
我需要构建自己的双端队列，因为我编程的环境没有这样的东西。我发现自己在如何实现它的两个选择之间左右为难：
- 我可以管理一个可增长的指向保存数据的数组的指针数组。问题是，如何确定每个辅助数组的大小？
- 我可以拥有一个定期增长的大型缓冲区，并在其顶部构建一个循环队列。在达到一定大小之后，这似乎很糟糕，因为大量分配变得更难以有效地完成。
有什么想法吗？
I need to build my own deque as the environment I program in has no such thing. I find my self torn between two choices as to how to implement it:
- I can manage a growable array of pointers to arrays which hold the data. The question is, how do I determine the size of each array secondary?
- I can have one large buffer that I periodically grow and essentially build a circular queue on top of it. This seems bad after a certain size as large allocations get harder to efficiently fulfill.
Any ideas?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
对于您的第一个选项，您可以在分配它们时简单地将每个数组的大小从之前的数组的大小增加一倍，也许达到由您对应用程序或内存限制的了解确定的某个上限。
第二个你似乎已经明白了。
为什么不只是一个简单的双向链表呢？您需要快速随机访问吗？
For your first option, you could simply double the size of each array from the one before as you allocate them, perhaps up to some upper bound determined by something you know about your application or memory constraints.
The second you seem to have figured out.
Why not just a simple doubly-linked list? Do you need fast random access?
另一种方法可以是向量列表（固定大小）。将列表作为第一个 DS 的好处是您可以在头部和尾部以及之间添加元素。具有固定大小向量的好处是您可以通过添加/删除行的时间为常数来模拟二维数组。现在假设您想在头上添加。您应该在列表的头部（ const time ）添加一个节点，然后在固定大小向量的最后添加该条目。因此，当出队已经有数据时，请考虑头部的任何条目，您将在第一行的最后一列插入。如果行中有可用空间，则任何在头部的进一步插入都将发生在第一行倒数第二个未填充的列处。否则重复相同的步骤。
末尾的正常插入通常发生在列表向量的末尾，其中插入是从向量的开头发生的。
One more way could be have lists of vectors( fixed size). Benefit of lists as first DS is you can add elements at head and tail and in between as well. The benefit of having fixed size vector is you can simulate two-dimention array with addition / deletion of row is constant time. Now suppose you want to add on head. You should add one node in list at head ( const time ), then add the entry at the last of the fixed size vector. So think of any entry at head when the dequeue is already having data, you are inserting at the last column of the first row. Any further insertion at head will happen at second last unfilled column of first row if there is space available in the row. other wise repeat the same step.
Normal insertions at the end will happen usually as end of the list's vector where insertions are happening from start of the vector.
我会结合你的两个选项 - 多个较小的缓冲区，并使每个“末端”指向另一个，本质上成为一个更大的圆形数组。这样您就不需要经常分配缓冲区。至于辅助缓冲区的大小，我认为 Collin 的建议是一个很好的建议 - 随使用而增加大小。
I would do a combination of your two options- multiple smaller buffers and have each "end" point to the other, essentially becoming a larger circular array. That way you shouldn't need to allocate buffers nearly as often. As to the size of the secondary buffers, I think Collin's suggestion is a good one- increase the size as you go.