知识卡片

普通读书笔记卡 · 1292.a.3.f · 生成模型:未记录

队列按进入先后取出

理解等级:中级

FIFO队列在尾部接收新项,在头部取出最早仍等待的项;查看头项只读取,不改变排队顺序。这个约束使到达与处理可以分离,同时保留约定的取出次序。

02767初始为5、3,8、9、2依次入队后,先出队的是5、3,剩8、9、2。顺序定义不保证每项被处理得一样快,也不自动给出等待时限;实现可用链表等不同存储,不能从横向排队图推断物理上一定连续。

92与02776实现queue_enqueue直接return list_ins_next(queue,list_tail(queue),data)。空队列的tail为NULL,沿用底层头插空表分支同时建立head/tail;非空则接到旧尾后。没有另行实现查找尾或复制数据。

97把循环队列概括为没有队尾过宽。循环表示或不保存tail字段,不取消队列的逻辑入队端与FIFO取出次序;本文没有给循环队列的实际表示,不能由短段造一个完整环形缓冲实现。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 3 处

    • · 查看原书依据

      首先存入队列的元素将首先被删除。我们可以把队列形象地看成在邮局排队办业务的一队人。事实上,任何一个到过英国的人都知道,你在任何公共场所办事时都必须“排队”。当新人一个一个排到队尾时,队伍也在不停变化。当队伍最前面的人完成服务后,将首先离开,接着是下一个,再下一个……在计算机中,将一个元素放置到队尾,

    • · 查看原书依据

      queue_enqueue调用list_ins_next方法来插入链表尾部指向data的元素(见示例6-4)。 queue_enqueue的运行时复杂度与list_ins_next相同,都是O(1)。

    • · 查看原书依据

      循环队列没有队尾,队列的最后一个元素指向队列的第一个元素,以便队列能够以循环的方式来遍历。

    参考来源

    - 位置:《算法精解:C语言描述》第6章《队列的描述》(spine1238;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1205.html;u087-ch06-007)。 - 结论依据:87全文与02767三态图,精确核对入队/出队次序和只查看不删除的区别,未测试。 - 原始内容:首先存入队列的元素将首先被删除。我们可以把队列形象地看成在邮局排队办业务的一队人。事实上,任何一个到过英国的人都知道,你在任何公共场所办事时都必须“排队”。当新人一个一个排到队尾时,队伍也在不停变化。当队伍最前面的人完成服务后,将首先离开,接着是下一个,再下一个……在计算机中,将一个元素放置到队尾, - 位置:《算法精解:C语言描述》第6章《queue_enqueue》(spine1242;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1209.html;u092-ch06-007)。 - 结论依据:92与02776实现queue_enqueue直接return list_ins_next(queue,list_tail(queue),data)。空队列的tail为NULL,沿用底层头插空表分支同时建立head/tail;非空则接到旧尾后。没有另行实现查找尾或复制数据。 - 原始内容:queue_enqueue调用list_ins_next方法来插入链表尾部指向data的元素(见示例6-4)。 queue_enqueue的运行时复杂度与list_ins_next相同,都是O(1)。 - 位置:《算法精解:C语言描述》第6章《相关主题》(spine1247;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1214.html;u097-ch06-007)。 - 结论依据:97把循环队列概括为没有队尾过宽。循环表示或不保存tail字段,不取消队列的逻辑入队端与FIFO取出次序;本文没有给循环队列的实际表示,不能由短段造一个完整环形缓冲实现。 - 原始内容:循环队列没有队尾,队列的最后一个元素指向队列的第一个元素,以便队列能够以循环的方式来遍历。