queue structure

date: 2021-03-26 excerpt: queue structure(キュー構造)について

tag: キュー algorithm data structure データ構造 queue

queue structure(キュー構造)について

概要

最初に入ったものを最初に出す
- “first-in, first-out” and "last-in, first-out"とう自由に設計できる
pythonのdequeはFIFOだけでなくlistだと計算量の視点で厳しいものであってもO(1)で追加・削除できる
- 右に追加するappendだけでなくappendleftもある
- 右から取り出すpopだけでなくpopleftもある

pythonでの使用例

>>> from collections import deque
>>> queue = deque(["Eric", "John", "Michael"])
>>> queue.append("Terry")           # Terry arrives
>>> queue.append("Graham")          # Graham arrives
>>> queue.popleft()                 # The first to arrive now leaves
'Eric'
>>> queue.popleft()                 # The second to arrive now leaves
'John'
>>> queue                           # Remaining queue in order of arrival
deque(['Michael', 'Terry', 'Graham'])

listとqueの速度差

10**5オーダーの操作で先頭から末尾への追加でおおよそ1000倍の時間差がある
高速なデータ管理であるならばqueを選択するべき
colab

例; 左から右へデータをコピーするときに検査が必要な時、取り出しと追加を現実的な時間で行える

問題

AtCoder Regular Contest 108; B - Abbreviate Fox

解説

不定回数の置換操作を最初に思いつくが、最適ではない
最適な操作は左から右へデータをコピーする中での検査と考えるとわかりやすい

解答

import collections

N=int(input())
S=input()
right = collections.deque(S)
left = collections.deque([None, None, None])

while right:
    left.append(right.popleft())

    if left[-3] == "f" and left[-2] == "o" and left[-1] == "x":
        for i in range(3):
            left.pop()

print(len([x for x in  left if x]))

例; 複雑な大量のシーケンシャルな操作を行う

問題
ZONeエナジープログラミングコンテスト “HELLO SPACE”; D - 宇宙人からのメッセージ

解説
listオブジェクトを選択してしまうと、追加と削除の計算量で厳しい状態となる

解答

from collections import deque
s = deque()
rev = False
for i in input():
    if i == 'R':
        rev = not rev
    elif rev:
        if s and s[0] == i:
            s.popleft()
        else:
            s.appendleft(i)
    else:
        if s and s[-1] == i:
            s.pop()
        else:
            s.append(i)
if rev:
    s = reversed(s)
print("".join(s))

参考

5. Data Structures