deque如何具有摊余常数时间复杂度

I read here https://stackoverflow.com/questions/22306949/does-deque-provide-o1-complexity-when-inserting-on-top从接受的答案来看， std::deque 具有以下特征

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最后插入的时间复杂度为摊余常量。这是因为向量是连续的并且是动态数组。所以当它的内存不足时push_back最后，它将分配一个全新的内存块，将现有项目从旧位置复制到新位置，然后从旧位置删除项目。我理解的这个操作是摊销常数。这如何应用于双端队列？双端队列顶部和底部的插入如何摊销为常数。我的印象是它应该是常数 O(1)。我知道双端队列是由内存块组成的。

双端队列的通常实现基本上是指向固定大小节点的指针向量。

分配固定大小的节点显然具有恒定的复杂性，因此这很容易处理 - 您只需在该节点中的项目数量上分摊分配单个节点的成本即可为每个节点获得恒定的复杂性。

指针向量部分（稍微）更有趣。当我们分配足够的固定大小节点使得指针向量已满时，我们需要增加向量的大小。喜欢std::vector，我们需要将其内容复制到新分配的向量中，因此它的增长必须遵循几何（而不是算术）级数。这意味着我们有更多的指针需要复制，并且复制的频率越来越低，因此用于复制指针的总时间保持不变。

附带说明：“向量”部分通常被视为循环缓冲区，因此如果您将双端队列用作队列，不断向一端添加并从另一端删除不会导致重新分配向量 - - 它只是意味着移动头指针和尾指针，以跟踪哪些指针在给定时间是“活动的”。