はじめに
Pythonで使えるキューを理解して、AtCoderの問題で使いこなせるように解説していきます。
実際にAtCoderの問題でキューを使ったサンプルコードも紹介します。
キューとは
そもそもキューとは、レジに並んだ行列のように、先に入れたものが先に使われるデータ構造です。先に入れたものを先に使うことをFIFO(First In First Out)と呼びます。
一方で、スタックは最後に入れたものを先に使うデータ構造です。こちらはLIFO(Last In First Out)と呼びます。
Pythonのキュー
Pythonでキューを扱う場合には、以下の2つがあげられます。
queue.Queuecollections.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))
