Python步步飞升之collections.deque
1. 前言
Python内置四种基本container：list, dict, set, tuple，collections模块为其补充。deque为collections中一个容器。一言以蔽之，是为双端队列.
2. deque定义
deque发音为“deck”，是“double-ended queue”的缩写，意为“双端队列”，用于生成堆和队列。
deque提供线程安全的，有效利用内存的 append 和 pop 方法可以从队列前后两个方向操作数据，时间复杂度为O(1)。
list也拥有类似的操作方法 pop(0) 和 insert(0, value), 但是效率没有deque高，时间复杂度为O(n)，因为操作之后list的长度和所有元素下标都要做修改。
class collections.deque([iterable[, maxlen]])
从iterable中拿去数据，从左到右初始化这些数据，通过自身 append() 方法添加数据，最终生成deque实例;
当iterable没有提供，即生成一个空deque;
maxlen 代表dqeue元素最大长度。
>>> d = deque([1,2,3,4]);
>>> d
deque([1, 2, 3, 4])
>>> d = deque([1,2,3,4],3);
>>> d
deque([2, 3, 4], maxlen=3) # 指定最大长度为3，则append(4)的时候挤掉元素“1”
3. Mark一些该类常用方法和特点
3.1 append(x)和appendleft(x)
后和前添加元素，如果超出maxlen会挤掉相反方向元素
>>> d
deque([2, 3, 4], maxlen=3)
>>> d.append(5)
>>> d
deque([3, 4, 5], maxlen=3)
>>> d.appendleft(2)
>>> d
deque([2, 3, 4], maxlen=3)
3.2 extend(iterable)和extendleft(iterable)
后和前添加iterable中元素
>>> d
deque([1, 2])
>>> d.extend([3,4])
>>> d
deque([1, 2, 3, 4])
>>> d.extendleft([-1,0])
>>> d
deque([0, -1, 1, 2, 3, 4]
3.3 insert(i, x)
在i位置插入x元素，如果超出maxlen，会抛出“IndexError”
>>> d
deque([0, -1, 1, 2, 3, 4])
>>> d.insert(0, -2)
>>> d
deque([-2, 0, -1, 1, 2, 3, 4])
>>> d
deque([1, 2, 3], maxlen=3)
>>> d.insert(0, 0)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
IndexError: deque already at its maximum size
3.4 pop()和popleft()
后和前删除元素，如果没有元素，会抛出“IndexError”
>>> d = deque([1,2,3], 3)
>>> d.pop()
3
>>> d
deque([1, 2], maxlen=3)
>>> d.popleft()
1
>>> d
deque([2], maxlen=3)
>>> d.pop()
2
>>> d
deque([], maxlen=3)
>>> d.pop()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
IndexError: pop from an empty deque
3.5 remove(value)
删除指定值的第一个元素，如果没有找到，会抛出“IndexError”
>>> d = deque('1223')
>>> d
deque(['1', '2', '2', '3'])
>>> d.remove('2')
>>> d
deque(['1', '2', '3'])
>>> d.remove('5')
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ValueError: deque.remove(x): x not in deque
3.6 reverse()
反deque中元素原顺序
>>> d
deque(['1', '2', '3'])
>>> d.reverse()
>>> d
deque(['3', '2', '1'])
3.7 rotate(n)
旋转n个位置，n为负则向左旋转。
>>> d
deque(['3', '2', '1'])
>>> d.rotate(1)
>>> d
deque(['1', '3', '2'])
>>> d.rotate(-1)
>>> d
deque(['3', '2', '1'])
3.8 maxlen属性
返回deque的maxlen属性值
>>> d
deque(['3', '2', '1'])
>>> d.maxlen
>>> d = deque([1,2], 3)
>>> d.maxlen
3
4. 简单应用
从文件中读取最后N行数据，类似于linux的“tail”命令
def tail(filename, n=10):
'文件中读取最后N行数据'
with open(filename) as f:
return deque(f, n)
>>> dq = tail('C:\\Users\\kigao\\Documents\\employee.csv', 1);
>>> dq
deque(['Danna,16,CFO,Finance Dept\n'], maxlen=1)
其中employee.csv文件内容为
Kian,18,CEO,R&D Dept
Danna,16,CFO,Finance Dept
5. 结语
如有疑问，欢迎留言共同探讨。
