Python双端列dequeの実現

前言
二重端列dequeは、任意の端から要素を追加および削除することをサポートしています。ここで、スタックとキューは、両端の列の退化した形であり、それらの入出力は、ある端に制限されている。
基本的な使い方
まず、容器のcollection.deque関数の基本的な使い方を見てみます。具体的なコードは以下の通りです。

import collections

c = collections.deque('abcdefg')
print("      ：", c)
print("       ：", len(c))
print("   ：", c[0])
print("   ：", c[-1])

運転後の効果は以下の通りです。

塗りつぶし
二重端列なので、このキューは任意の端から要素を追加または削除することをサポートしています。以下、両端の追加と削除をそれぞれ実現します。具体的なコードは以下の通りです。

import collections

c = collections.deque()
#          
c.extend("abcdefg")
#  （  ）  
c.append('h')
print(c)
#    （  ）  
c.extendleft('i')
print(c)
#    
c.pop()
print(c)
#    
c.popleft()
print(c)
#    
c.remove('c')
print(c)

運転後の効果は以下の通りです。

リスト配列を使うのと同じように、appedによって追加され、デフォルトのappedは右端から追加されます。先端から追加したいなら、extendleft()関数が使えます。また、削除はpop()関数を使って右端(末尾)から削除し、popleft()は左端から削除します。任意に削除すると、remove()を直接使うことができます。
スレッドの安全
二重端列はスレッドが安全であり、実際のアプリケーションでは、異なるスレッドで同時に両端からキューの内容を消費することができる。具体的なコードは以下の通りです。

import collections
import threading
import time

def getItem(lor, method):
    while True:
        try:
            next = method()
        except IndexError:
            break
        else:
            print("{0}:{1}".format(lor, next))
            time.sleep(0.1)
    print('{0}:None'.format(lor))
    return

c = collections.deque("abcdefg")
t1 = threading.Thread(target=getItem, args=('Left', c.popleft))
t2 = threading.Thread(target=getItem, args=('Right', c.popleft))
t1.start()
t2.start()
t1.join()
t2.join()

運転後の効果は以下の通りです。

上のコードでは、2つのスレッドが交互に要素を削除します。重複した要素が削除されていないことが分かります。
回転
デュアルエンド行列dequeのもう一つの有用な態様は、任意の方向に回転することができ、いくつかの要素をスキップすることである。
例えば、deque双端列を右に回転（正回転値を使用して）すると、右端から要素を取り、左端に移動します。同じように、左に回転（負の値）すると、左端から元素を右端に移動します。
私たちは端のコードを見ればよく分かります。

import collections

a = collections.deque("abcdefg")
b = collections.deque("abcdefg")
c = collections.deque("abcdefg")
print(a)
b.rotate(2)
print(b)
c.rotate(-2)
print(c)

運転後の効果は以下の通りです。

bの前の2文字が前に移動されるのが見えます。cの前の2文字は後ろに移動されます。
ダブルエンドのキューサイズを制限する
実際の二重端キュー動作では、このサイズを超えないように二重端キューdequeの例の最大長を設定することができる。この動作は，長さが不確定な流れの中で最後のn個の要素を検索するのに非常に有用である。
まずコードを見てみます。

import collections
import random

c1 = collections.deque(maxlen=5)
c2 = collections.deque(maxlen=3)

for i in range(8):
    r = random.randint(1, 100)
    print(r)
    c1.append(r)
    c2.append(r)
print(c1)
print(c2)

運転後の効果は以下の通りです。

上のコードから分かるように、二重端列の最大長さはいくらデータを追加しても長さは変わらないです。また、余分に追加したデータは、一番前（左端）の値を順番に入れ替えます。
ここでPython双端列dequeの実現に関する記事を紹介します。Python双端列dequeの内容については以前の文章を検索してください。または下記の関連記事を引き続きご覧ください。これからもよろしくお願いします。