3.1.1. 両端キュー¶

両端キューとは¶

末尾と先頭に対するデータの追加・削除を高速に行うことができるデータ構造のこと。

実装¶

概要¶

Pythonには連結リストで実装された collections.deque があり、これを利用できる。

計算量¶

操作	メソッド	計算量
末尾に追加	`append`	\(\mathcal{O}(1)\)
先頭に追加	`appendleft`	\(\mathcal{O}(1)\)
末尾を削除	`pop`	\(\mathcal{O}(1)\)
先頭を削除	`popleft`	\(\mathcal{O}(1)\)
末尾を参照	`q[-1]`	\(\mathcal{O}(1)\)
先頭を参照	`q[0]`	\(\mathcal{O}(1)\)
要素数を取得	`len(q)`	\(\mathcal{O}(1)\)

使用例¶

[1]:

from collections import deque

q = deque()
q.append(1)
q.append(2)
q.append(3)
q.append(4)
print(q.pop())
print(q[-1])
print(q.popleft())
print(q[0])
print(len(q))