dequeとは
dequeはdouble-ended queueの略で、日本語だと両端キューとか言われる。普通queueと言ったらFIFO(First-In First Out)のデータ構造で、先に入れたデータを先に出すことしかできないものを指す。dequeはこのFIFO操作をqueueの両側に適用できるようにしたもの。つまり、FIFOとLIFO両方の操作が効率的に実行できるという特性を持つ。
使用例
上記のAtCoderコンテストの問題でdequeをうまく利用できる。
使用例はこんな感じ
from collections import deque
def main():
N = int(input())
A = deque([N])
S = list(input())
for i in range(N - 1, -1, -1):
if S[i] == "L":
A.append(i)
else:
A.appendleft(i)
A = [str(n) for n in A]
print(" ".join(A))
if __name__ == "__main__":
main()
Pythonであればcollectionsパッケージからdequeモジュールをインポートして使うことができる。11行目のappendメソッドや13行目のappendLeftメソッドのようにdequeの両端に効率的に要素を追加することができる。もちろんdequeじゃなくてlistの末尾や先頭に要素を追加することもできるが、listにそれらの操作をするとそのlistの長さに比例した時間がかかってしまうところを、dequeであれば先頭・末尾への追加ならば定数時間で実行できるという大きなメリットを持つ。これにより、要素の追加にかかる計算量をO(n)からO(1)に減らすことができ、処理全体の計算量を大きく抑えることができる。