[Python]collections.deque用法和双向队列实现,Pythoncollectionsdeque,以及

发表时间:2021-05-11

一,概述

deque 是Python标准库 collections 中的一个类,是 double-ended queue的缩写,实现了两端都可以操作的队列,相当于双端队列。类似于 list,与list不同的是,deque实现拥有更低的时间和空间复杂度。

二,内置方法

1,添加元素
from collections import deque

dq = deque(maxlen=3)  # 创建固定长度的队列
# append(x) 在队列右端(尾部)添加x,和普通的列表append方法一样
dq.append(1)
dq.append(2)
dq.append(3)
print(dq)  # deque([1, 2, 3], maxlen=3)

dq.append(4)  # 当新记录加入队列且队列已满,会自动从另一端移除首条记录
print(dq)  # deque([2, 3, 4], maxlen=3)  左端 1 被移除

dq.appendleft(5)  # appendleft(x) 在队列左端(头部)添加x
print(dq)  # deque([5, 2, 3], maxlen=3)  右端 4 被移除

除了和list 一样append,还有extend添加一组元素

dq = deque()  # 不指定maxlen,得到无界限的队列

# extend(x) 在队列右端(尾部)添加一组元素,和list的extend方法一样
dq.extend([1, 2, 3, 4, 5])  # deque([1, 2, 3, 4, 5])

# extendleft(x) 在队列左端(头部)添加一组元素,
dq.extendleft(['a', 'b', 'c'])
print(dq)  # deque(['c', 'b', 'a', 1, 2, 3, 4, 5])   注意插入顺序!!!
2,移除元素
dq = deque()
dq.extend([1, 2, 3, 4, 5])
dq.extendleft(['a', 'b', 'c'])
# pop() 从双端队列右端(尾部)删除一个值,并将该值作为返回值返回。
dq.pop()
print(dq)  # deque(['c', 'b', 'a', 1, 2, 3, 4])
# popleft() 从双端队列右端(尾部)删除一个值,并将该值作为返回值返回。
dq.popleft()
print(dq)  # deque(['b', 'a', 1, 2, 3, 4])
3,循环移动

rotate(n) 向右循环移动 n 步,如果 n 是负数,就向左循环n 步。

dq = deque()
dq.extend([1, 2, 3, 4, 5])
dq.extendleft(['a', 'b', 'c'])

# rotate(n) 向右循环移动 n 步。
dq.rotate(1)
print(dq)  # deque([5, 'c', 'b', 'a', 1, 2, 3, 4])

# 如果 n 是负数,就向左循环n 步
dq.rotate(-2)
print(dq)  # deque(['b', 'a', 1, 2, 3, 4, 5, 'c'])

如果deque不是空的,向右循环移动一步就等价于 d.appendleft(d.pop()) , 向左循环一步就等价于 d.append(d.popleft()) 。

4,与list相同的其他方法

insert(i, x) 在位置 i 插入 x ;
reverse() 将deque逆序排列;
index(x[, start[, stop]]) 返回 x 在 deque 中的位置(在索引 start 之后,索引 stop 之前)。 返回第一个匹配项;
remove(value) 移除找到的第一个 value;
count(x) 计算 deque 中元素等于 x 的个数
clear() 移除所有元素,使其长度为0.

三,应用

1,实现类似于 Linux 的 tail,返回文件最后N行
def tail(filename, n=2):
    with open(filename) as f:
        return deque(f, n)


if __name__ == '__main__':
    for line in tail('E:\\data\\somefile.txt'):
        print(line, end='')

在这里插入图片描述
输出结果:
9 第九行
10 第十行 Python

2,《Pythion Cookbook》的例子

对文本中行进行匹配,当发现有匹配行时就输出当前匹配行以及其前N行文本

def search(lines, pattern, history=5):
    previous_lines = deque(maxlen=history)
    for line in lines:
        if pattern in line:
            for lline in previous_lines:
                print(lline, end='')
            print(line, end='')
            print()
        previous_lines.append(line)

if __name__ == '__main__':
    with open('E:\\data\\somefile.txt') as f:
        search(f, 'Python', 2)

输出结果:
4 第四行
5 第五行
6 第六行 Python

8 第八行
9 第九行
10 第十行 Python

四,实现双向队列

下面使用列表实现顺序双端队列。

class SequenceDoubleQueue(object):

    def __init__(self, maxlen=None):
        self._items = list()
        self._len = maxlen

    def is_empty(self):
        """判断是否为空"""
        return not len(self._items)

    def append_front(self, item):
        """
        在队头添加元素
        若超过固定长度,移除尾部一个元素,再添加
        """
        if len(self._items) == self._len:
            self._items.pop()
            self._items.insert(0, item)
        else:
            self._items.insert(0, item)

    def append_rear(self, item):
        """
        在队尾添加元素
        若超过固定长度,移除头部一个元素,再添加
        """
        if len(self._items) == self._len:
            self._items.pop(0)
            self._items.append(item)
        else:
            self._items.append(item)

    def pop_front(self):
        """
        移除头部第一个元素,并返回该元素
        :return:
        """
        return self._items.pop(0)

    def pop_rear(self):
        """
        移除尾部第一个元素,并返回该元素
        :return:
        """
        return self._items.pop()

    def size(self):
        """
        返回队列长度
        """
        return len(self._items)

    def __repr__(self):
        """
        格式化输出
        """
        if self.is_empty():
            print('双端队列为空')
            return None
        else:
            return ','.join([str(x) for x in self._items])

if __name__ == '__main__':
    dq = SequenceDoubleQueue(maxlen=5)
    dq.append_rear(1)
    dq.append_rear(2)
    dq.append_rear(3)
    dq.append_rear(4)
    dq.append_rear(5)
    print(dq)
    dq.append_front('a')
    dq.append_front('b')
    print(dq)
    dq.pop_rear()
    print(dq)
    dq.pop_front()
    print(dq)

输出结果:
1,2,3,4,5
b,a,1,2,3
b,a,1,2
a,1,2

参考

《Python Cookbook》第三版
https://docs.python.org/zh-cn/3/library/collections.html#collections.deque

文章来源互联网,如有侵权,请联系管理员删除。邮箱:417803890@qq.com / QQ:417803890

微配音

Python Free

邮箱:417803890@qq.com
QQ:417803890

皖ICP备19001818号-4
© 2019 copyright www.pythonf.cn - All rights reserved

微信扫一扫关注公众号:

联系方式

Python Free