跳转至

双向队列

在队列中,我们仅能删除头部元素或在尾部添加元素。如下图所示,双向队列(double-ended queue)提供了更高的灵活性,允许在头部和尾部执行元素的添加或删除操作。

双向队列的操作

双向队列常用操作

双向队列的常用操作如下表所示,具体的方法名称需要根据所使用的编程语言来确定。

表   双向队列操作效率

方法名 描述 时间复杂度
push_first() 将元素添加至队首 \(O(1)\)
push_last() 将元素添加至队尾 \(O(1)\)
pop_first() 删除队首元素 \(O(1)\)
pop_last() 删除队尾元素 \(O(1)\)
peek_first() 访问队首元素 \(O(1)\)
peek_last() 访问队尾元素 \(O(1)\)

同样地,我们可以直接使用编程语言中已实现的双向队列类:

deque_operations
可视化运行

@tutor deque_operations_tutor

双向队列实现 *

双向队列的实现与队列类似,可以选择链表或数组作为底层数据结构。

基于双向链表的实现

回顾上一节内容,我们使用普通单向链表来实现队列,因为它可以方便地删除头节点(对应出队操作)和在尾节点后添加新节点(对应入队操作)。

对于双向队列而言,头部和尾部都可以执行入队和出队操作。换句话说,双向队列需要实现另一个对称方向的操作。为此,我们采用“双向链表”作为双向队列的底层数据结构。

如下图所示,我们将双向链表的头节点和尾节点视为双向队列的队首和队尾,同时实现在两端添加和删除节点的功能。

基于链表实现双向队列的入队出队操作

linkedlist_deque_push_last

linkedlist_deque_push_first

linkedlist_deque_pop_last

linkedlist_deque_pop_first

实现代码如下所示:

[file]{linkedlist_deque}-[class]{linked_list_deque}-[func]{}

基于数组的实现

如下图所示,与基于数组实现队列类似,我们也可以使用环形数组来实现双向队列。

基于数组实现双向队列的入队出队操作

array_deque_push_last

array_deque_push_first

array_deque_pop_last

array_deque_pop_first

在队列的实现基础上,仅需增加“队首入队”和“队尾出队”的方法:

[file]{array_deque}-[class]{array_deque}-[func]{}

双向队列应用

双向队列兼具栈与队列的逻辑,因此它可以实现这两者的所有应用场景,同时提供更高的自由度。

我们知道,软件的“撤销”功能通常使用栈来实现:系统将每次更改操作 push 到栈中,然后通过 pop 实现撤销。然而,考虑到系统资源的限制,软件通常会限制撤销的步数(例如仅允许保存 \(50\) 步)。当栈的长度超过 \(50\) 时,软件需要在栈底(队首)执行删除操作。但栈无法实现该功能,此时就需要使用双向队列来替代栈。请注意,“撤销”的核心逻辑仍然遵循栈的先入后出原则,只是双向队列能够更加灵活地实现一些额外逻辑。