<think>我们根据提供的引用内容，可以看到双端队列（Deque）的基本实现方法。 引用中提供了多个版本的代码，但核心操作是一致的： - add_front(item): 在队头添加元素，通常使用列表的insert(0, item)方法。 - add_rear(item): 在队尾添加元素，通常使用列表的append(item)方法。 - remove_front(): 从队头删除元素，使用pop(0)方法。 - remove_rear(): 从队尾删除元素，使用pop()方法（不指定索引则弹出最后一个元素）。 但是，我们需要注意性能问题。在Python列表中，在头部插入和删除（insert(0, item)和pop(0)）的时间复杂度为O(n)，而在尾部插入和删除（append(item)和pop()）的时间复杂度为O(1)。因此，如果对性能有较高要求，我们可以考虑使用collections.deque，它是使用双向链表实现的，两端的操作都是O(1)。但这里要求自己实现，所以我们按照列表实现。 另外，引用[4]中使用了私有属性self.__items，这是一种封装思想，但根据需求，我们可以选择是否封装。这里我们按照常规实现，使用普通列表属性即可。 根据上述分析，我们实现一个Deque类，包含以下方法： - __init__: 初始化一个空列表 - is_empty: 判断队列是否为空 - add_front: 在队头添加元素（使用insert(0, item)） - add_rear: 在队尾添加元素（使用append(item)） - remove_front: 从队头删除元素（使用pop(0)） - remove_rear: 从队尾删除元素（使用pop()，注意弹出最后一个元素） - size: 返回队列大小（列表长度） 注意：在remove操作时，如果队列为空，调用pop会引发异常。我们可以先判断是否为空，但引用中的实现没有处理，我们这里也先不处理异常（用户应确保队列非空时调用）。 下面给出代码实现： </think> ### Python实现双端队列Deque类 以下是双端队列（Deque）抽象数据类型的完整Python实现，包含`add_front`、`add_rear`、remove_front`和`remove_rear`方法的具体代码： ```python class Deque: """双端队列实现""" def __init__(self): """初始化空队列""" self.items = [] def is_empty(self) -> bool: """检查队列是否为空""" return len(self.items) == 0 def add_front(self, item) -> None: """在队头添加元素 时间复杂度: $O(n)$ (因列表需移动所有元素) """ self.items.insert(0, item) def add_rear(self, item) -> None: """在队尾添加元素 时间复杂度: $O(1)$ """ self.items.append(item) def remove_front(self): """从队头删除元素 时间复杂度: $O(n)$ 返回: 被删除的元素 """ if self.is_empty(): raise IndexError("从空队列删除元素") return self.items.pop(0) def remove_rear(self): """从队尾删除元素 时间复杂度: $O(1)$ 返回: 被删除的元素 """ if self.is_empty(): raise IndexError("从空队列删除元素") return self.items.pop() def size(self) -> int: """返回队列大小""" return len(self.items) def __str__(self) -> str: """返回队列的字符串表示""" return f"Deque: {self.items}" # 测试示例 if __name__ == "__main__": dq = Deque() # 添加元素 dq.add_front(2) # 队头: [2] dq.add_front(1) # 队头: [1, 2] dq.add_rear(3) # 队尾: [1, 2, 3] dq.add_rear(4) # 队尾: [1, 2, 3, 4] print(dq) # 输出: Deque: [1, 2, 3, 4] print("队列大小:", dq.size()) # 输出: 4 # 删除元素 print("删除队头:", dq.remove_front()) # 输出: 1 → [2, 3, 4] print("删除队尾:", dq.remove_rear()) # 输出: 4 → [2, 3] print(dq) # 输出: Deque: [2, 3] ``` ### 关键方法说明 1. **`add_front(item)`** - 使用`list.insert(0, item)`在列表头部插入元素 - 时间复杂度: $O(n)$ (需移动所有元素)[^1] 2. **`add_rear(item)`** - 使用`list.append(item)`在列表尾部插入元素 - 时间复杂度: $O(1)$[^2] 3. **`remove_front()`** - 使用`list.pop(0)`删除并返回队头元素 - 时间复杂度: $O(n)$[^3] 4. **`remove_rear()`** - 使用`list.pop()`删除并返回队尾元素 - 时间复杂度: $O(1)$[^4] ### 性能优化提示 对于高频操作场景，建议使用Python标准库的`collections.deque`，其两端操作均为$O(1)$时间复杂度： ```python from collections import deque dq = deque() dq.appendleft(1) # 前端添加 dq.append(2) # 后端添加 dq.popleft() # 前端删除 dq.pop() # 后端删除 ```