您的位置:

Python deque的高效插入元素方法

一、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