Python编程中3个常用的数据结构和算法(3)

deque(maxlen=N)创建了一个固定长度的队列。当有新记录加入而队列已满时会自动移除最老的那条记录。例如：

>>> q = deque(maxlen=3) 
>>> q.append(1) 
>>> q.append(2) 
>>> q.append(3) 
>>> q 
deque([1, 2, 3], maxlen=3) 
>>> q.append(4) 
>>> q 
deque([2, 3, 4], maxlen=3) 
>>> q.append(5) 
>>> q 
deque([3, 4, 5], maxlen=3) 

尽管可以在列表上手动完成这样的操作(append、del)，但队列这种解决方案要优雅得多，运行速度也快得多。

更普遍的是，当需要一个简单的队列结构时，deque可祝你一臂之力。如果不指定队列的大小，也就得到了一个无界限的队列，可以在两端执行添加和弹出操作，例如：

>>> q = deque() 
>>> q.append(1) 
>>> q.append(2) 
>>> q.append(3) 
>>> q 
deque([1, 2, 3]) 
>>> q.appendleft(4) 
>>> q 
deque([4, 1, 2, 3]) 
>>> q.pop() 
3 
>>> q 
deque([4, 1, 2]) 
>>> q.popleft() 
4 

从队列两端添加或弹出元素的复杂度都是O(1)。这和列表不同，当从列表的头部插入或移除元素时，列表的复杂度为O(N)。

【编辑推荐】

1. Stack Overflow 2019开发者调查报告发布，Python或成赢？
2. Fedora 提出统一流程，弃用上千 Python 2 软件包更可控
3. Python并发：线程和锁
4. 百道Python面试题实现，搞定Python编程就靠它
5. 你爱 “Python”的身体，还是“R”的灵魂？

（编辑：ASP站长网）