[파이썬] deque

파이썬을 이용해서 BFS를 풀면 주로 사용하게 되는 자료구조가 Deque다. 사용하기야 자주 사용하지만 생각보다 deque을 잘 모르고 사용한다는 생각이 들어서 정리를 하기로 했다.

deque 정의

큐의 앞, 뒤에서 삽입, 삭제가 가능한 큐 (double-ended queue의 줄임말)

deque 메소드

collections 파일에 deque가 포함되어 있다. 따라서 deque 자료구조를 사용하기 위해서는 아래와 같이 선언해줘야 한다.

from collections import deque

append(x): 큐의 뒤로 삽입

from collections import deque

queue= deque()
queue.append('b')
# queue = ['b']

queue.append('c')
# queue = ['b', 'c']

appendleft(x): 큐의 앞으로 삽입

from collections import deque

queue = deque()
queue.append('b')
# queue = ['b']

queue.append('c')
# queue = ['b', 'c']

queue.appendleft('a')
# queue = ['a', 'b', 'c']

clear: 큐의 모든 요소를 삭제함.

from collections import deque

queue = deque()
queue.append('b')
# queue = ['b']

queue.append('c')
# queue = ['b', 'c']

queue.appendleft('a')
# queue = ['a', 'b', 'c']

queue.clear()
# queue = []

copy: 얕은 복사

from collections import deque

queue = deque()
queue.append('b')
# queue = ['b']

copied_queue = queue.copy()
# copied_queue = ['b']

count(x): 큐에서 x와 같은 값의 개수

from collections import deque

queue = deque()
queue.append('b')
# queue = ['b']

queue.append('a')
# queue = ['b', 'a']

queue.appendleft('a')
# queue = ['a', 'b', 'a']

print(queue.count('a')
# 2

extend(iterable): iterable한 값을 파라미터로 넣으면 해당 값들이 하나씩 큐의 오른쪽에 붙음

from collections import deque

queue = deque()
queue.append('b')
# queue = ['b']

queue.extend('lft')
# queue = ['b', 'l', 'f', 't']

queue.append('lft')
# queue = ['b', 'l', 'f', 't', 'lft']

extendleft(iterable): iterable한 값을 파라미터로 넣으면 해당 값들이 하나씩 큐의 왼쪽에 붙음

(아래는 파이썬 공식문서에서의 extendleft에 대한 원문과 파파고 해석)
Extend the left side of the deque by appending elements from iterable. Note, the series of left appends results in reversing the order of elements in the iterable argument.
해당 요소에서 요소를 추가하여 데크의 왼쪽을 확장합니다. 왼쪽의 연속은 반복 가능한 인수의 요소 순서를 뒤집는 결과를 추가합니다.

from collections import deque

queue = deque()
queue.append('b')
# queue = ['b']

queue.extendleft('lft')
# queue = ['t', 'f', 'l', 'b']

queue.appendleft('lft')
# queue = ['lft', 't', 'f', 'l', 'b']

index(x[, start[, stop]]): 큐(인덱스 시작 후 및 인덱스 중지 전)에서 x의 위치를 반환. 첫 번째 일치를 반환하거나 찾을 수 없는 경우 ValueError 발생.

from collections import deque

queue = deque()
queue.append('b')
# queue = ['b']

queue.extendleft('kny')
# queue = ['y', 'n', 'k', 'b']

# index(x)
print(queue.index('b'))
# 4

# index(x, start: int)
print(queue.index('b', 1))
# 4

# index(x, start: int, stop: int)
print(queue.index('b', 0, 1))
# ValueError: 'b' is not in deque

insert(i, x): i 위치에 x를 삽입

from collections import deque

queue = deque()
queue.append('b')
# queue = ['b']

queue.append('c')
# queue = ['b', 'c']

queue.insert(0, 'a')
# queue = ['a', 'b', 'c']


# queue.maxlen()을 넘어선 위치에 insert를 하고자 하면, IndexError가 발생한다.

pop(): 큐의 맨 오른쪽의 element를 삭제하고 반환. element가 없으면, IndexError가 발생.

from collections import deque

queue = deque()
queue.append('b')
# queue = ['b']

queue.append('c')
# queue = ['b', 'c']

popped = queue.pop()
# popped = 'c'

popleft(): 큐의 맨 왼쪽의 element를 삭제하고 반환. element가 없으면, IndexError가 발생.

from collections import deque

queue = deque()
queue.append('b')
# queue = ['b']

queue.append('c')
# queue = ['b', 'c']

popped_left = queue.popleft()
# popped_left = 'b'

remove(value): 큐에 있는 value 값 중 처음으로 등장한 value를 삭제. 못 찾으면, ValueError가 발생

from collections import deque

queue = deque()
queue.append('b')
# queue = ['b']

queue.append('c')
# queue = ['b', 'c']

queue.append('b')
# queue = ['b', 'c', 'b']

queue.remove('b')
# queue = ['c', 'b']

reverse(): 큐를 제자리에서 반대로 뒤집는다. 반환값은 없음.

from collections import deque

queue = deque()
queue.append('c')
# queue = ['c']

queue.append('b')
# queue = ['c', 'b']

queue.append('a')
# queue = ['c', 'b', 'a']

queue.reverse()
# queue = ['a', 'b', 'c']

rotate(n=1): n만큼 오른쪽으로 회전. n이 음수면, 왼쪽으로 회전, 반환값은 없음.
큐(q)가 비어있지 않다면, q.rotate(1)을 하는 것은 q.appendleft(q.pop())과 같음.
또한, q,rotate(-1)을 하는 것은 q.append(q.popleft())과 같음.

from collections import deque

queue = deque()
queue.append('c')
# queue = ['c']

queue.append('b')
# queue = ['c', 'b']

queue.append('a')
# queue = ['c', 'b', 'a']

queue.rotate(1)
# queue = ['a', 'c', 'b']

queue.rotate(-1)
# queue = ['c', 'b', 'a']

maxlen: 큐 생성 시, 정했던 큐의 최대 크기, 정하지 않았으면 None 반환

# 최대 크기를 정했을 시
from collections import deque

# class collections.deque([iterable[, maxlen]])
# deque(iterable, maxlen: int)
queue = deque('fnd', 3)
print(queue)
# deque(['f', 'n', 'd'], maxlen=3)

queue.append('b')
print(queue)
# deque(['n', 'd', 'b'], maxlen=3)

queue.append('c')
print(queue)
# deque(['d', 'b', 'c'], maxlen=3)

queue.appendleft('a')
print(queue)
# deque(['a', 'd', 'b'], maxlen=3)

print(queue.maxlen)
# 3

# 최대 크기를 정하지 않았을 때
from collections import deque

# class collections.deque([iterable[, maxlen]])
# deque(iterable)
queue = deque('fnd')
print(queue)
# deque(['f', 'n', 'd'])

queue.append('b')
print(queue)
# deque(['f', 'n', 'd', 'b'])

queue.append('c')
print(queue)
# deque(['f', 'n', 'd', 'b', 'c'])

queue.appendleft('a')
print(queue)
# deque(['a', 'f', 'n', 'd', 'b', 'c'])

print(queue.maxlen)
# None

참고사이트

https://docs.python.org/3/library/collections.html#collections.deque