双端队列与优先级队列

双端队列（Deque）

双端队列（Double-Ended Queue，简称Deque）是一种允许在两端都进行插入和删除操作的队列。

双端队列的分类

• 输入受限的双端队列：只允许在一端进行插入，两端都可以删除
• 输出受限的双端队列：只允许在一端进行删除，两端都可以插入
• 一般双端队列：两端都可以插入和删除

双端队列与栈、队列的关系

• 如果限制双端队列只能在一端插入和删除，就退化为栈
• 如果限制双端队列只能在一端插入、另一端删除，就退化为普通队列

优先级队列

优先级队列（Priority Queue）是一种特殊的队列，每个元素都有一个优先级，出队时总是优先级最高的元素先出队，而不是按照入队的顺序。

优先级队列通常用堆（Heap）来实现，入队和出队操作的时间复杂度为 $O(\log n)$。

上一章节链式队列链式队列的存储结构与基本操作实现。

下一章节经典应用队列在广度优先搜索、缓冲区管理、任务调度等场景中的应用。