在队列中，我们仅能删除头部元素或在尾部添加元素。双向队列（double‑ended queue）提供了更高的灵活性，允许在头部和尾部执行元素的添加或删除操作。
一、双向队列常用操作
- 队首入队（push_front）：在双向队列的头部添加一个元素。
- 队首出队（pop_front）：删除双向队列头部的元素。
- 队尾入队（push_back）：在双向队列的尾部添加一个元素。
- 队尾出队（pop_back）：删除双向队列尾部的元素。
- 访问队首元素（peek_front）：获取双向队列头部的元素，但不删除它。
- 访问队尾元素（peek_back）：获取双向队列尾部的元素，但不删除它。
- 获取队列长度（size）：返回双向队列中元素的个数。
- 判断队列是否为空（isEmpty）：如果双向队列为空，则返回true，否则返回false。
from collections import deque
# 初始化双向队列
deque: deque[int] = deque()
# 元素入队
deque.append(2)
# 添加至队尾
deque.append(5)
deque.append(4)
deque.appendleft(3)
# 添加至队首
deque.appendleft(1)
# 访问元素
front: int = deque[0]
# 队首元素
rear: int = deque[-1]
# 队尾元素
# 元素出队
pop_front: int = deque.popleft()
# 队首元素出队
pop_rear: int = deque.pop()
# 队尾元素出队
# 获取双向队列的长度
size: int = len(deque)
# 判断双向队列是否为空
is_empty: bool = len(deque) == 0二、双向队列实现 *
1.基于双向链表的实现
回顾上一节内容，我们使用普通单向链表来实现队列，因为它可以方便地删除头节点（对应出队操作）和在尾节点后添加新节点（对应入队操作）。
对于双向队列而言，头部和尾部都可以执行入队和出队操作。换句话说，双向队列需要实现另一个对称方向的操作。为此，我们采用“双向链表”作为双向队列的底层数据结构。
将双向链表的头节点和尾节点视为双向队列的队首和队尾，同时实现在两端添加和删除节点的功能。
# 双向链表节点定义
class DListNode:
def __init__(self, val=0, prev=None, next=None):
self.val = val
self.prev = prev
self.next = next
# 双向队列类定义
class LinkedListDeque:
def __init__(self):
self.front = None
self.rear = None
self.size = 0
def push(self, val, is_front=True):
new_node = DListNode(val)
if self.size == 0:
self.front = self.rear = new_node
elif is_front:
new_node.next = self.front
self.front.prev = new_node
self.front = new_node
else:
new_node.prev = self.rear
self.rear.next = new_node
self.rear = new_node
self.size += 1
def pop(self, is_front=True):
if self.size == 0:
raise IndexError("双向队列为空")
if self.size == 1:
val = self.front.val
self.front = self.rear = None
elif is_front:
val = self.front.val
self.front = self.front.next
self.front.prev = None
else:
val = self.rear.val
self.rear = self.rear.prev
self.rear.next = None
self.size -= 1
return val
def peek_front(self):
if self.size == 0:
raise IndexError("双向队列为空")
return self.front.val
def peek_back(self):
if self.size == 0:
raise IndexError("双向队列为空")
return self.rear.val
def size(self):
return self.size
def is_empty(self):
return self.size == 0
# 示例代码
if __name__ == "__main__":
deque = LinkedListDeque()
deque.push(1)
deque.push(2, is_front=False)
print(deque.peek_front())
print(deque.peek_back())
print(deque.pop())
print(deque.pop(is_front=False))2.基于数组的实现
class ArrayDeque:
def __init__(self, capacity):
self.capacity = capacity
self.array = [None] * capacity
self.front = 0
self.rear = 0
self.size = 0
def is_full(self):
return self.size == self.capacity
def is_empty(self):
return self.size == 0
def push_front(self, item):
if self.is_full():
raise IndexError("队列已满")
self.front = (self.front - 1 + self.capacity) % self.capacity
self.array[self.front] = item
self.size += 1
def push_back(self, item):
if self.is_full():
raise IndexError("队列已满")
self.array[self.rear] = item
self.rear = (self.rear + 1) % self.capacity
self.size += 1
def pop_front(self):
if self.is_empty():
raise IndexError("队列已空")
item = self.array[self.front]
self.front = (self.front + 1) % self.capacity
self.size -= 1
return item
def pop_back(self):
if self.is_empty():
raise IndexError("队列已空")
self.rear = (self.rear - 1 + self.capacity) % self.capacity
item = self.array[self.rear]
self.size -= 1
return item
def peek_front(self):
if self.is_empty():
raise IndexError("队列已空")
return self.array[self.front]
def peek_back(self):
if self.is_empty():
raise IndexError("队列已空")
return self.array[self.rear - 1 + self.capacity] % self.capacity
def get_size(self):
return self.size