はじめに
Pythonで使えるキューを理解して、AtCoderの問題で使いこなせるように解説していきます。
実際にAtCoderの問題でキューを使ったサンプルコードも紹介します。
キューとは
そもそもキューとは、レジに並んだ行列のように、先に入れたものが先に使われるデータ構造です。先に入れたものを先に使うことをFIFO(First In First Out)と呼びます。
一方で、スタックは最後に入れたものを先に使うデータ構造です。こちらはLIFO(Last In First Out)と呼びます。
Pythonのキュー
Pythonでキューを扱う場合には、以下の2つがあげられます。
queue.Queue
collections.deque
queue.Queue
は一般的なキューです。
collections.deque
は、スタックとキューを一般化したもので、両端キュー(double-ended queue)と呼ばれます。両端キューなので、どちらの側へのappend
もpop
もO(1)
で実行できます。
複数のスレッドで使うような場合はqueue.Queue
を利用するのがいいみたいですが、AtCoderで使う場合はcollections.deque
でいいと思います。


collections.deque
collections.deque
の使い方について紹介します。
キューの作成
deque
でキューを作成します。
from collections import deque
d = deque()
listからキューへの変換もできます。
from collections import deque
li = [1, 2, 3, 4]
d = deque(li)
追加
append
とappendleft
で両端への要素の追加をします。
O(1)
で実行できます。
>>> from collections import deque
>>> d = deque([1, 2])
>>> d.append(3)
>>> d.appendleft(4)
>>> d
deque([4, 1, 2, 3])
取り出し
pop
とpopleft
で両端から要素を取り出します。
O(1)
で実行できます。
>>> from collections import deque
>>> d = deque([1, 2, 3, 4])
>>> d.pop()
4
>>> d.popleft()
1
反転
reverse
で反転できます。
>>> from collections import deque
>>> d = deque([1, 2, 3, 4])
>>> d.reverse()
>>> d
deque([4, 3, 2, 1])
AtCoderのサンプル問題
ABC066 C問題

空の数列bに対して、別の数列aの要素を末尾に追加と反転する操作を繰り返してできる数列bを求める問題です。
要素を末尾と先頭で交互に追加していき、最後に要素数で反転するかどうか判定しています。
from collections import deque
n = int(input())
A = list(map(int, input().split()))
b = deque()
for i in range(n):
if i % 2 == 0:
b.append(A[i])
else:
b.appendleft(A[i])
if n % 2 == 1:
b.reverse()
print(*b)
ABC158 D問題

与えられたクエリに従って文字列を作成していく問題です。
反転と要素を先頭か末尾に追加する操作があるのでdeque
を活用します。反転は毎回操作するとTLEになってしまうので、反転しているかどうかをbool型でもっておきます。
from collections import deque
s = input()
q = int(input())
query = []
for _ in range(q):
query.append(list(input().split()))
que = deque(s)
reverse_flag = False
for i in range(q):
if query[i][0] == '1':
reverse_flag = not reverse_flag
else:
if query[i][1] == '1' and reverse_flag:
que.append(query[i][2])
elif query[i][1] == '1':
que.appendleft(query[i][2])
elif query[i][1] == '2' and reverse_flag:
que.appendleft(query[i][2])
else:
que.append(query[i][2])
if reverse_flag:
que.reverse()
print(''.join(que))