Python Language
Dequeモジュール

構文

• dq = deque（）＃空の両端キューを作成します。
• dq = deque（iterable）＃いくつかの要素を持つ両端キューを作成します。
• dque.append（object）＃オブジェクトを両端キューの右側に追加する
• dque.appendleft（object）＃オブジェクトを両端キューの左側に追加します。
• dq.pop（） - > object＃最も右のオブジェクトを削除して返します
• dq.popleft（） - > object＃左端のオブジェクトを削除して返します
• dque.extend（iterable）＃両端キューの右側にいくつかの要素を追加します
• dque.extendleft（iterable）＃いくつかの要素を両端キューの左側に追加します

パラメーター

備考

使用している基本deque

このクラスで有用な主なメソッドは、 popleftとappendleft

from collections import deque

d = deque([1, 2, 3])
p = d.popleft()        # p = 1, d = deque([2, 3])
d.appendleft(5)        # d = deque([5, 2, 3])

デュークサイズを制限する

両端キューを作成する際にmaxlenパラメータを使用して、両端キューのサイズを制限する：

from collections import deque
d = deque(maxlen=3)  # only holds 3 items
d.append(1)  # deque([1])
d.append(2)  # deque([1, 2])
d.append(3)  # deque([1, 2, 3])
d.append(4)  # deque([2, 3, 4]) (1 is removed because its maxlen is 3)

両端キューで使用可能なメソッド

空の両端キューを作成する：

dl = deque()  # deque([]) creating empty deque

いくつかの要素でdequeを作成する：

dl = deque([1, 2, 3, 4])  # deque([1, 2, 3, 4])

dequeに要素を追加する：

dl.append(5)  # deque([1, 2, 3, 4, 5])

デキューの要素の左側を追加する：

dl.appendleft(0)  # deque([0, 1, 2, 3, 4, 5])

dequeに要素のリストを追加する：

dl.extend([6, 7])  # deque([0, 1, 2, 3, 4, 5, 6, 7])

左から要素のリストを追加する：

dl.extendleft([-2, -1])  # deque([-1, -2, 0, 1, 2, 3, 4, 5, 6, 7])

.pop()要素を使用すると、自然に右側から項目が削除されます。

dl.pop()  # 7 => deque([-1, -2, 0, 1, 2, 3, 4, 5, 6])

.popleft()要素を使用してアイテムを左側から削除する：

dl.popleft()  # -1 deque([-2, 0, 1, 2, 3, 4, 5, 6])

その値で要素を削除する：

dl.remove(1)  # deque([-2, 0, 2, 3, 4, 5, 6])

両端キューの要素の順序を逆にする：

dl.reverse()  # deque([6, 5, 4, 3, 2, 0, -2])

幅広い検索

Dequeは、高速のキュー操作を持つ唯一のPythonデータ構造です。 （注queue.Queue 、それがスレッド間通信のためのものなので、通常は適していない。）キューの基本的なユースケースは、 幅優先探索 。

from collections import deque

def bfs(graph, root):
    distances = {}
    distances[root] = 0
    q = deque([root])
    while q:
        # The oldest seen (but not yet visited) node will be the left most one.
        current = q.popleft()
        for neighbor in graph[current]:
            if neighbor not in distances:
                distances[neighbor] = distances[current] + 1
                # When we see a new node, we add it to the right side of the queue.
                q.append(neighbor)
    return distances

単純な有向グラフがあるとします：

graph = {1:[2,3], 2:[4], 3:[4,5], 4:[3,5], 5:[]}

出発点からの距離を見つけることができます：

>>> bfs(graph, 1)
{1: 0, 2: 1, 3: 1, 4: 2, 5: 2}

>>> bfs(graph, 3)
{3: 0, 4: 1, 5: 1}