知识卡片
端点布局决定队列弹出成本
原书队列 Push 改头指针为 O(1),Pop 却需要走到单链尾部并记住前驱,通常为 O(n)。若维护头尾并从头删除、尾部追加,可让两端操作都避免全链扫描;这属于可选的实现改进,不是原例已实现。额外 size 必须与每次增删同步,才能可靠表示空队列。
书末要求尝试用双向链表改善队列;该练习没有给出完成代码或测量结果。判断改进应看是否避免查尾前驱,并计入额外指针维护。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- 05.7.1 Go 语言实现队列 · 查看原书依据
- return t.Value, true } temp := t for (t.Next) != nil { temp = t t = t.Next } v := (temp.Next).Value temp.Next = nil size-- return v, true }
- 05.12 练习 · 查看原书依据
你觉得如果使用双向链表的话是否能改善 queue.go 程序中的代码呢?试着用双向链表代替单向链表实现一个队列。
参考来源
- 位置:《精通 Go(Mastering Go 中文版)》05.7.1 Go 语言实现队列,spine095(book-sources;extracted/精通 Go(Mastering Go 中文版)/_epub-src/05.7.1.html)。
- 结论依据:Pop 查尾循环以及 Push、Pop 对 size 的维护形成直接依据。
- 原始内容:- return t.Value, true } temp := t for (t.Next) != nil { temp = t t = t.Next } v := (temp.Next).Value temp.Next = nil size-- return v, true }
- 补充位置:spine105《05.12 练习》;extracted/精通 Go(Mastering Go 中文版)/_epub-src/05.12.html。
- 补充原始内容:你觉得如果使用双向链表的话是否能改善 queue.go 程序中的代码呢?试着用双向链表代替单向链表实现一个队列。