知识卡片

操作参考卡 · 5667

双端队列支持两端进出

理解等级:中级

需要在序列两端进出数据时,可用无容量上限的deque(),例如appendleft(x)在左侧加入,popleft()取走左端。两端添加与弹出的常见复杂度为O(1),列表头部插入或删除则需要移动元素,通常为O(N)。这不表示deque所有位置访问都同样高效,也不保证某个实际程序必然更快。

这张卡片看不懂?

已有反馈 · 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)。