我读到这里，从接受的答案是一个std ::双端队列具有以下特点
1- Random access - constant O(1)
2- Insertion or removal of elements at the end or beginning - amortized constant O(1)
3- Insertion or removal of elements - linear O(n)
我的问题是关于第2点。双端队列如何在末尾有摊销的常数插入？
我了解到，std::vector最后插入的a具有摊销后的恒定时间复杂度。这是因为向量是连续的并且是动态数组。因此，当最后一个内存用完push_back时，它将分配一个全新的内存块，将现有项目从旧位置复制到新位置，然后从旧位置删除项目。我了解此操作为摊销常数。这如何适用于双端队列？如何将双端队列的顶部和底部的插入摊销为常数。我的印象是它应该是常数O（1）。我知道双端队列由内存块组成。
双端队列的通常实现基本上是指向固定大小节点的指针的向量。
分配固定大小的节点显然具有恒定的复杂性，因此这很容易处理-您只需分摊在该节点中的项目数上分配单个节点的成本，即可获得每个项目的恒定复杂性。
指针的向量部分（稍微）比较有趣。当我们分配足够的固定大小节点以使指针的向量已满时，我们需要增加向量的大小。像一样std::vector，我们需要将其内容复制到新分配的向量中，因此其增长必须遵循几何（而不是算术）过程。这意味着我们有更多要复制的指针，而复制的频率越来越低，因此用于复制指针的总时间保持不变。
附带说明：“向量”部分通常被视为循环缓冲区，因此，如果您将双端队列用作队列，则不断地将一端添加到另一端并从另一端删除不会导致重新分配矢量， -只是意味着移动头和尾指针，以跟踪在给定时间哪个指针处于“活动”状态。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句