3.2.4 双端队列

教材导航 · 第3章

原书定位

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

双端队列 deque 允许在两端插入与删除。输入受限时只允许一端插入,两端都能删除;输出受限时两端都能插入,只允许一端删除。

判断输出序列时,应画出每次从哪端入队、哪端出队,并保持队内先后关系。若只有一端同时承担插入、删除,则包含栈的行为;普通队列也可视作双端队列进一步限制后的情形。两种受限双端队列能够生成的排列集合不同。

图3.10 双端队列

图3.10 双端队列,原书P80。

图3.11 输出受限的双端队列

图3.11 输出受限的双端队列,原书P80。

图3.12 输入受限的双端队列

图3.12 输入受限的双端队列,原书P80。

对应练习

3.2 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

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

原书对照,原书P81,PDF第93页