Pythonでキューやスタックを実現する際に利用できるcollectionsモジュールのdequeについて解説します。
Contents
キュー（queue）とスタック（stack）
dequeの定義や使い方の説明の前にキュー(queue)とスタック(stack)について簡単に説明しておきます。キューやスタックについてご存じの方は読み飛ばしていただいて結構です。
キューとスタックは、データ格納と取り出しに関するデータ構造の一種となっています。それぞれの概要をまとめると以下のようになります。また、キューとスタックの概要図も示します。
| 名称 | 内容 |
|---|---|
| キュー（queue） | 先入れ先出し（FIFO: First In First Out）で管理するデータ構造 |
| スタック（stack） | 後入れ先出し（LIFO: Last In First Out）で管理するデータ構造 |
キューは最初に入れたデータから順に取りだすデータ構造で、よく先頭の人から順番に対応される待ち行列の話で説明がされます。上記図でいうと①→②の順で入れたデータは、①→②の順でデータが取り出されます。先入れ先出しであることからFIFO(First In First Out)と言います。
一方で、スタックはキューとは逆で最後に入れたデータから順に取り出すデータ構造です。上記図でいうと①→②の順で入れたデータは②→①の順で取り出されます。後入れ先出しであることからLIFO(Last In First Out)と言います。
キューやスタックといったデータ構造をPythonで実現しようとする場合、list型のinsertやpopを利用した実現を考えることができます。しかし、list型は追加・削除で要素の移動が伴う可能性があるため、処理が非効率となる可能性があります。
効率的にキューやスタックを実現するためにPythonのcollectionsモジュールにはdequeが使用できます。
本記事では、dequeを用いたキューやスタックの実現方法について紹介します。
deque（collectionsモジュール）
キューやスタックの実装を例にdequeの使い方を紹介していきます。dequeという名称は、「double ended queue（両端キュー）」からきていて、デックと言います。
dequeは内部的には二重のリンクリストとして実現されています。イメージの図にしてみると以下のようになります。
各要素は、要素同士の双方向のリンクを持っていて相互に参照することができます。そのため、要素へのアクセスは先頭 or 末尾からリンクをたどってアクセスします。
メソッドとしては以下のようなメソッドが用意されています。
| メソッド名 | 概要 |
|---|---|
| append(x) | xを末尾に追加する |
| appendleft(x) | xを先頭に追加する |
| pop() | 末尾から値を取得し、削除する |
| popleft() | 先頭から値を取得し、削除する |
| clear() | 全ての値を削除する |
図と対応させてみてもらうと分かりやすいかと思いますが、データを追加する場合はappend、データを取り出すときがpopです。なお、先頭の場合はappendleft、popleftのようにleftがつきます。図のように先頭が左という考え方になります。
dequeは、前後のリンクを持っている構造上、先頭や末尾へのアクセスや追加／削除は早いですが、データの中央に近づくほどアクセスに時間がかかってしまうのが特徴があります。
以降では、dequeを用いたキュー（queue）とスタック（stack）の実装例を紹介していきますが、上の図のようなイメージを持ってもらうと理解がしやすいかと思います。
dequeによるキュー（queue）操作
キュー(queue)の操作をdequeを使用して実現するには以下のようにします。
import collections # dequeの作成 data = collections.deque() # データの追加 data.append(10) data.append(20) data.append(30) data.append(40) # 先頭からのデータ取り出し print(data) print(data.popleft()) print(data) print(data.popleft()) print(data)
【実行結果】 deque([10, 20, 30, 40]) 10 deque([20, 30, 40]) 20 deque([30, 40])
dequeを使用するためにcollectionsモジュールのインポートが必要です。collections.deque()でdequeのインスタンスを生成して使用します。
キューは、先入れ先出しのFIFO(First In First Out)ですので、データの追加は末尾にデータを追加するappendメソッドを使用し、データを取り出すには先頭からデータを取り出すpopleftメソッドを使用します。
このようにdequeを使用するとキューの操作を簡単に実現することができます。
dequeによるスタック（stack）操作
スタック(stack)の操作をdequeを使用して実現するには以下のようにします。
import collections # dequeの作成 data = collections.deque() # データの追加 data.append(10) data.append(20) data.append(30) data.append(40) # 末尾からのデータ取り出し print(data) print(data.pop()) print(data) print(data.pop()) print(data)
【実行結果】 deque([10, 20, 30, 40]) 40 deque([10, 20, 30]) 30 deque([10, 20])
キューの例と同様に、dequeを使用するためにはまずcollectionsモジュールのインポートが必要で、collections.deque()でdequeのインスタンスを生成して使用します。
スタックは、後入れ先出しのLIFO(Last In Last Out)ですので、データの追加は末尾にデータを追加するappendメソッドを使用し、データを取り出すには末尾から取り出すpopメソッドを使用します。
このようにdequeを使用するとスタックの操作を簡単に実現することができます。
dequeの使用に関する注意点
dequeには、上記で紹介してきたようなappend、pop等の操作の他に、insert、remove、index等のメソッドをサポートしています。
しかし、dequeは構造上、先頭や末尾への操作は非常に高速ですが、それ以外の操作はdequeは不得意です。
そのため、insert、remove、indexなどの操作を頻繁に使用するプログラムの場合はリストの方が適したデータ構造です。
要素数がそれほど多くない場合には、リストでもdequeでもそれほど処理速度の差はないため、多くのアプリケーションではリストで問題ないかもしれません。しかし、適切なデータ構造を選択するというのはプログラマとして重要な観点なのでよく検討してdequeを活用するようにしてください。
まとめ
Pythonでキューやスタックを実現する際に利用できるcollectionsモジュールのdequeについて解説しました。
dequeは「double ended queue（両端キュー）」のことで、各種メソッドが用意されているため、キューやスタックの操作が簡単に実現できることが分かるかと思います。
dequeは構造上、先頭や末尾への操作は非常に高速ですが、それ以外の操作はdequeは不得意という特徴があります。途中のデータに頻繁にアクセスすることが必要な場合にはリストのが適していますので、dequeの使用が妥当であるかは想定する操作によりよく検討してみてください。
dequeの公式ドキュメントはこちらを参照してください。
上記で紹介しているソースコードについてはgithubにて公開しています。参考にしていただければと思います。
