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] = 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) = k and queue[0] = x:
            queue.pop()
        queue.append(i)
        if i >= k - 1:
            res.append(seq[queue[0]])
    return res