3.2.3 队列的链式存储结构

教材导航 · 第3章

原书定位

印刷页P78起,对应PDF第90页。下文为目视整理的知识提要;完整内容见原书对照。

链式队列是带队头与队尾指针的单链表。入队在尾部连接新结点,出队在头部摘除结点,均可 O(1)O(1)。

带头结点时空队满足 front==rear 且头结点后继为空。若删除的是最后一个数据结点,还必须令 rear=front;无头结点时最后一次出队后头尾都应为空。初始化和销毁须与是否保留头结点一致。

图3.8 不带头结点的链式队列

图3.8 不带头结点的链式队列,原书P78。

图3.9 带头结点链式队列的空队与非空队

图3.9 带头结点链式队列的空队与非空队,原书P79。

对应练习

3.2 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P78,PDF第90页

原书对照,原书P79,PDF第91页

原书对照,原书P80,PDF第92页