【Python】collectionsライブラリを活用しよう_3. deque

はじめに

こんにちは。孔子の80代目子孫兼AS部DS2課の孔です。collectionsライブラリを活用しよう第３弾！今回はdeque（「デック」と読みます）の紹介です。

第１弾のnamedtuple、第２弾のOrderedDictはそれぞれtupleとdictの拡張版であることは名前から推測することができますが、今回のdequeは何の拡張版なのか名前だけ見ると明瞭ではありませんね。

dequeはlistの拡張版となります。dequeは簡単に説明すると、「キュー + スタック」と言えます。それではキューとスタックとは何か？を先にみてみましょう！

Queue（キュー）とは？

キューは、「先入れ先出し」方式（FIFO: First In, First Out）でデータを出し入れするデータ構造です。以下の絵を見てください。

上記のようなキューがあった場合、データを取り出す順番は「1, 2, 7, 4」になり、後から投入されたデータは「4」の後ろに溜まっていき、「4」が取り出されたら次々と取り出すことができます。

（ちなみに、データをキューに入れることを「エンキュー（Enqueue）」といい、出すことを「デキュー（Dequeue）」（dequeではありません！！）と言います。）

つまり、溜まっているデータの中で最も先に入ったデータが先に出される（先入れ先出し）構造になります。これがキューになります。Pythonではキューを標準ライブラリで提供しています。以下は簡単なキューの使い方です。

import queue
　
q = queue.Queue(maxsize=4)  # 要素が３つまで入るキューを生成する
　
for i in range(3):
    q.put(i)  # キューにデータを投入する
　
q.qsize()  # 3, キューに溜まった要素の数を返す
q.full()  # True, maxsize == q.qsize()のため
　
for _ in range(3):
    q.get()  # 0, 1, 2の順番で取得
　
q.empty()  # True, キューに溜まった要素がなければTrue, なければFalse

Stack（スタック）とは？

キューが「先入れ先出し」方式だったことに対して、スタックは「後入れ先出し」方式（LIFO: Last In, First Out）でデータを出し入れします。出す順番がキューの逆だと思うと楽ですね。

一般的にLIFO方式のキューをスタックと呼びますが、PythonではLifoQueueというデータ構造名で実装されています。Queue同様、queueライブラリから使用することができます。使い方はQueueと変わりません。

import queue
　
q = queue.LifoQueue(maxsize=3)  # 要素が３つまで入るキューを生成する
　
for i in range(3):
    q.put(i)  # キューにデータを投入する
　
q.qsize()  # 3, キューに溜まった要素の数を返す
q.full()  # True, maxsize == q.qsize()のため
　
for _ in range(3):
    q.get()  # 2, 1, 0の順番で取得
　
q.empty()  # True, キューに溜まった要素がなければTrue, なければFalse

deque: Queue + Stack

それでは、dequeをみてみましょう。dequeという名前は「double-ended queue」の略語になります。キューの先頭、スタックの末尾という両方の末端（double-ended）からデータを出し入れできるための名前になります。わかりやすくするため、以下の図を見てください。

両方の末端どこからもデータを投入することができ、どこからもデータを取り出すことができます。これがdequeとなります。Pythonでdequeは以下のように利用できます。

from collections import deque
　
dq = deque('bcd')
dq  # deque(['b', 'c', 'd'])
　
dq.append('e')  # 右側に'e'を追加
dq.appendleft('a')  # 左側に'a'を追加
dq  # deque(['a', 'b', 'c', 'd', 'e'])
　
dq.pop()  # e, 右側の要素を取得
dq.popleft()  # a, 左側の要素を取得
　
dq.rotate(1)  # deque(['d', 'b', 'c']), 右回りに要素を回転
dq.rotate(-1)  # deque(['b', 'c', 'd']), 左回りに要素を回転
　
dq[1]  # 'c', インデックス指定で値取得

基本的に、dequeで実現できる操作自体はlistを使っても実装することができます。ただし、listはappendleftされた際（list.insert(0, element)）にリストに入ってる全ての要素のインデックスを貼り直す必要があり、リストのサイズが大きくなればなるほどappendleft処理が遅くなります。

このようなパフォーマンスを考慮して実装されたのがdequeで、dequeのサイズにほぼ影響なくappend, appendleft処理ができるのがdequeのメリットとなります。