知识卡片

普通读书笔记卡 · 5654.d.1.a.1.c.1.e

双端队列开放两端操作

理解等级:中级

双端队列允许在头尾两端加入和删除元素,因此可按使用方式表现为栈或普通队列,也能支持两种抽象之外的端点维护。

双向链表用前后链接支持两端删除;环形数组通过front、size和模运算定位两端。增加自由度也增加需要检查的空、满和索引变化,不能只在peek中检查空却让pop继续修改计数。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      双向队列需要实现另一个对称方向 的操作。为此,我们采用“双向链表”作为双向队列的底层数据结构。 如图5‑8 所示,我们将双向链表的头节点和尾节点视为双向队列的队首和队尾,同时实现在两端添加和删除 节点的功能。 图5‑8

    参考来源

    - 位置:《Hello 算法--Go版本》第05章《栈与队列》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/3.html;spine 2,归一字符[6591,6700)) - 结论依据:实际deque定义/两种实现及端点操作,保持抽象与边界相连。 - 原始内容:双向队列需要实现另一个对称方向 的操作。为此,我们采用“双向链表”作为双向队列的底层数据结构。 如图5‑8 所示,我们将双向链表的头节点和尾节点视为双向队列的队首和队尾,同时实现在两端添加和删除 节点的功能。 图5‑8