python如何构建队列数据结构

在Python中，可以通过多种方式构建队列数据结构。队列是一种先进先出（First In, First Out, FIFO）的数据结构，主要有两种常见的实现方式：使用列表（list）或者使用collections模块中的deque（双端队列）。

以下是使用列表构建队列的一个简单示例：

class Queue:
    def __init__(self):
        self.items = []
        
    def is_empty(self):
        return len(self.items) == 0
    
    def enqueue(self, item):
        self.items.insert(0, item)  # 注意这里的插入位置在列表的开头
    
    def dequeue(self):
        if not self.is_empty():
            return self.items.pop()  # 移除并返回列表末尾的元素
        else:
            return None
    
    def size(self):
        return len(self.items)
    
    def peek(self):
        if not self.is_empty():
            return self.items[-1]  # 查看队列的最后一个元素，但不移除
        else:
            return None

使用collections模块中的deque来构建队列，相比于列表，deque在两端的添加和删除操作都更为高效，因为列表是基于数组实现的，而在列表开头插入元素需要移动后面的元素，而deque是基于双端队列的数据结构，设计上支持两端的快速增删操作。

以下是使用deque构建队列的示例：

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()
        
    def is_empty(self):
        return len(self.items) == 0
    
    def enqueue(self, item):
        self.items.append(item)  # 在队列末尾添加元素
    
    def dequeue(self):
        if not self.is_empty():
            return self.items.popleft()  # 移除并返回队列开头的元素
        else:
            return None
    
    def size(self):
        return len(self.items)
    
    def peek(self):
        if not self.is_empty():
            return self.items[0]  # 查看队列的第一个元素，但不移除
        else:
            return None

在这个使用deque的实现中，我们可以看到`append`方法用于在队列末尾添加元素，`popleft`方法用于移除并返回队列开头的元素。这些操作的时间复杂度都是O(1)，即常数时间复杂度，这是deque相比列表在处理队列操作时的优势所在。