一、deque概述
deque,全名double-ended queue(双端队列),是Python标准库collections中的一个数据类型。与普通的list相比,deque在插入和删除元素时具有更高的性能,尤其是在频繁地在队列两端插入和删除元素时。deque既可以从左边入队、出队,也可以从右边入队、出队,故命名为双端队列。
deque的底层是由一个双向链表实现的,每个节点维护双向指针,从而能够在O(1)时间内实现双端插入和删除操作。此外,deque也支持像list一样的随机访问操作,并且可以在队列任意位置插入和删除元素(时间复杂度为O(N))。
二、deque的高效插入元素方法
由于deque底层是由双向链表实现的,故在队列两端插入和删除元素时具有O(1)的时间复杂度。在队列中间插入元素时,由于要遍历到待插入位置,故时间复杂度为O(N)。但是,如果已经知道待插入元素的位置,也可以实现O(1)时间内的插入操作,这就是deque的高效插入元素方法。
deque提供了一个方法叫做rotate,它可以旋转队列。rotate接收一个参数k,表示把队列中k个元素从左边移到右边(k>0),或从右边移到左边(k<0),也可以通过k%len(queue)来对k进行调整,保证k在0~len(queue)范围内。
rotate方法可以用于实现deque的高效插入元素操作,具体方法如下:
from collections import deque def insert_elem(queue, index, elem): if index >= 0: queue.rotate(-index) queue.appendleft(elem) queue.rotate(index) else: queue.rotate(abs(index)) queue.append(elem) queue.rotate(-abs(index))
上述代码中定义了一个名为insert_elem的函数,它接收三个参数:queue代表待操作的deque双端队列,index代表待插入元素的位置,elem代表待插入的元素。如果index>=0,则先将queue从左边旋转index步,将elem插入到最左端(也就是在index位置插入),再将queue从左边旋转回去;如果index<0,则先将queue从右边旋转abs(index)步,将elem插入到最右端(也就是在倒数第index个位置插入),再将queue从右边旋转回去。
三、deque高效插入元素方法的应用场景
deque提供的高效插入元素方法在一些特定场景非常有用,下面列出几个具体的应用场景:
1. 实现成员缓存
当需要维护一个固定大小的缓存时,deque非常适合用来实现。使用双端队列可以同时维护队列的头和尾,当有新元素要加入队列时,如果队列已满,则先将队列头部元素移除,再将新元素插入队列尾部。
from collections import deque class Cache: def __init__(self, size=10): self.size = size self.queue = deque(maxlen=size) def add(self, item): self.queue.append(item)
上述代码定义了一个名为Cache的类,它包含一个队列属性queue,使用双端队列来维护缓存;缓存大小由maxlen指定,默认为10。当缓存已满时,将新元素加入队列尾部,会自动删除队列头部元素。
2. 实现循环队列
循环队列是通过允许队列的首尾相接,使队列在逻辑结构上像一个圆环一样的数据结构。在循环队列中,如果队列已满,则将新元素加入到队列头部,而不是队列尾部;如果队列为空,则队列头和队列尾都指向同一个位置。
from collections import deque class CircularQueue: def __init__(self, size=10): self.size = size self.queue = deque(maxlen=size) def enqueue(self, item): if len(self.queue) < self.queue.maxlen: self.queue.append(item) else: self.queue.rotate(-1) self.queue[-1] = item
上述代码定义了一个名为CircularQueue的类,它维护一个大小为size的deque。当队列未满时,新元素加入队列尾部;当队列已满时,将队列头部元素移动到队列尾部,并将新元素加入队列尾部。
3. 实现滑动窗口
滑动窗口(sliding window)是一种重要的算法思想,它在序列中滑动两个指针,以获取某些特定长度的连续区间数据。deque可以通过其高效的插入和删除元素方法来实现滑动窗口。
from collections import deque def sliding_window(seq, k): queue = deque() res = [] for i, x in enumerate(seq): if i >= k and queue[0] <= i - k: queue.popleft() while queue and seq[queue[-1]] >= x: queue.pop() queue.append(i) if i >= k - 1: res.append(seq[queue[0]]) return res
上述代码中定义了一个名为sliding_window的函数,它接收两个参数:一个序列seq和一个整数k,返回一个列表res。函数首先创建一个空的deque双端队列,用于存储当前滑动窗口的元素下标。在函数中遍历序列seq,如果当前元素下标i大于等于k,而队列头部元素比i-k小,则将其弹出队列。然后,如果队列非空且队列尾部元素对应的seq值大于当前值x,则弹出队列尾部元素。最后,将当前下标i加入队列。如果当前下标i大于等于k-1,则表示当前队列已经滑动到了第一个窗口,将队列头部元素对应的seq值加入到结果列表res中。
四、总结
Python deque提供了高效的插入和删除元素方法,能够很好地满足一些特定场景下数据结构的需求。在实际开发中,需要根据数据结构的使用情况,选择合适的数据类型。同时,对于某些特定场景下高效的操作方法,也需要熟练掌握并加以利用。
完整代码如下:
from collections import deque def insert_elem(queue, index, elem): if index >= 0: queue.rotate(-index) queue.appendleft(elem) queue.rotate(index) else: queue.rotate(abs(index)) queue.append(elem) queue.rotate(-abs(index)) class Cache: def __init__(self, size=10): self.size = size self.queue = deque(maxlen=size) def add(self, item): self.queue.append(item) class CircularQueue: def __init__(self, size=10): self.size = size self.queue = deque(maxlen=size) def enqueue(self, item): if len(self.queue) < self.queue.maxlen: self.queue.append(item) else: self.queue.rotate(-1) self.queue[-1] = item def sliding_window(seq, k): queue = deque() res = [] for i, x in enumerate(seq): if i >= k and queue[0] <= i - k: queue.popleft() while queue and seq[queue[-1]] >= x: queue.pop() queue.append(i) if i >= k - 1: res.append(seq[queue[0]]) return res