我正要过去thispost 并指出 deque 在顶部和底部提供高效的插入。但是这post这里指出除后面之外的双端队列的时间复杂度是 O(n)。我认为如果双端队列具有有效的顶部和底部插入，它将具有 O(1) 而向量应该仅在底部插入具有 O(1) 。如果有人能澄清这一点，我将不胜感激
C++98，第 23.2.1 节（模板类双端队列）
“双端队列...支持在开头或结尾处进行恒定时间插入和擦除操作；在中间插入和擦除需要线性时间。也就是说，双端队列特别针对在开头和结尾处推入和弹出元素进行了优化.与向量一样，存储管理是自动处理的。”
所以是的：O(1) 在两端插入。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
