知识卡片
双端队列支持两端进出
需要在序列两端进出数据时,可用无容量上限的deque(),例如appendleft(x)在左侧加入,popleft()取走左端。两端添加与弹出的常见复杂度为O(1),列表头部插入或删除则需要移动元素,通常为O(N)。这不表示deque所有位置访问都同样高效,也不保证某个实际程序必然更快。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
从队列两端添加或弹出元素的复杂度都是O(1)。这和列表不同,当从列表的头部插入或移除元素时,列表的复杂度为O(N)。
参考来源
- 位置:《Python Cookbook(第3版)中文版》1.3 保存最后N个元素(spine9;extracted/Python Cookbook(第3版)中文版/_epub-src/OEBPS/Text/part0007.xhtml;u005-ch01-005)。
- 结论依据:已完整读取本条的问题、代码与讨论;以实际结构及边界解释,不声称运行原代码或当前版本测试通过。
- 原始内容:从队列两端添加或弹出元素的复杂度都是O(1)。这和列表不同,当从列表的头部插入或移除元素时,列表的复杂度为O(N)。