数据结构与算法 线性表-双向队列
对于队列，我们仅能在头部删除或在尾部添加元素。然而，「双向队列 Deque」提供了更高的灵活性，允许在头部和尾部执行元素的添加或删除操作。
双向队列常用操作
双向队列的常用操作如下表所示，具体的方法名称需要根据所使用的编程语言来确定。
| 方法名 | 描述 | 时间复杂度 |
|---|---|---|
| pushFirst() | 将元素添加至队首 | O(1) |
| pushLast() | 将元素添加至队尾 | O(1) |
| popFirst() | 删除队首元素 | O(1) |
| popLast() | 删除队尾元素 | O(1) |
| peekFirst() | 访问队首元素 | O(1) |
| peekLast() | 访问队尾元素 | O(1) |
双向队列实现
双向队列的实现与队列类似，可以选择链表或数组作为底层数据结构。
基于双向链表的实现
我们使用普通单向链表来实现队列，因为它可以方便地删除头节点（对应出队操作）和在尾节点后添加新节点（对应入队操作）。
对于双向队列而言，头部和尾部都可以执行入队和出队操作。换句话说，双向队列需要实现另一个对称方向的操作。为此，我们采用「双向链表」作为双向队列的底层数据结构。
我们将双向链表的头节点和尾节点视为双向队列的队首和队尾，同时实现在两端添加和删除节点的功能。
=== “pushLast()”
=== “pushFirst()”
=== “popLast()”
=== “popFirst()”
基于数组的实现
与基于数组实现队列类似，我们也可以使用环形数组来实现双向队列。在队列的实现基础上，仅需增加“队首入队”和“队尾出队”的方法。
=== “pushLast()”
=== “pushFirst()”
=== “popLast()”
=== “popFirst()”
双向队列应用
双向队列兼具栈与队列的逻辑，因此它可以实现这两者的所有应用场景，同时提供更高的自由度。
我们知道，软件的“撤销”功能通常使用栈来实现：系统将每次更改操作 push 到栈中，然后通过 pop 实现撤销。然而，考虑到系统资源的限制，软件通常会限制撤销的步数（例如仅允许保存 50 步）。当栈的长度超过 50 时，软件需要在栈底（即队首）执行删除操作。但栈无法实现该功能，此时就需要使用双向队列来替代栈。请注意，“撤销”的核心逻辑仍然遵循栈的先入后出原则，只是双向队列能够更加灵活地实现一些额外逻辑。