파이썬 - collections.deque

collections.deque

deque는 앞과 뒤에서 데이터를 처리할 수 있는 양방향 자료형으로, 스택(stack)처럼 써도 되고 큐(queue)처럼 써도 된다. collections.deque 모듈은 deque 자료형을 생성하는 모듈이다.

deque는 '데크'라 읽는다.

문제

다음과 같이 시계방향으로 1~5가 적힌 다이얼이 있으며 현재 가리키는 눈금은 1이다.

[1, 2, 3, 4, 5]

이 다이얼을 오른쪽으로 2칸 돌려 가리키는 눈금이 4가 되도록 하려면 어떻게 해야 할까?

[4, 5, 1, 2, 3]

풀이

리스트를 n만큼 회전하는 문제는 알고리즘 문제에서 자주 등장한다. 파이썬에서는 collections.deque 모듈을 사용하면 간단하게 이 문제를 해결할 수 있다.

>>> from collections import deque
>>> a = [1, 2, 3, 4, 5]
>>> q = deque(a)
>>> q.rotate(2)  #시계방향 회전은 양수, 그 반대는 음수
>>> result = list(q)
>>> result
[4, 5, 1, 2, 3]

deque(a)로 deque 객체를 만든 후 rotate() 함수를 사용하여 2만큼 오른쪽으로 회전하면 첫 값이 4를 가리키게 된다. 마찬가지로 왼쪽으로 2만큼 회전하여 3을 가리키려면 2 대신 -2를 입력하면 된다.

알아두면 좋아요list와 비슷한 deque

deque의 사용법을 잠시 살펴보자.

>>> from collections import deque
>>> d = deque([1,2,3,4,5])
>>> d.append(6)
>>> d
deque([1, 2, 3, 4, 5, 6])
>>> d.appendleft(0)
>>> d
deque([0, 1, 2, 3, 4, 5, 6])
>>> d.pop()
6
>>> d
deque([0, 1, 2, 3, 4, 5])
>>> d.popleft()
0
>>> d
deque([1, 2, 3, 4, 5])
>>>

이 예제를 보면 알겠지만 deque는 list와 매우 비슷하다. 스택과 큐로 사용할 수 있는 메서드도 대부분 일치한다. 다만, deque에는 다음과 같은 메서드가 더 있다.

• appendleft(x): 데크 왼쪽에 x 추가
• popleft(): 데크 왼쪽에서 요소를 제거

예를 들어 리스트에서는 첫 번째 요소를 삭제할 때 pop(0)을 사용하지만, deque는 popleft()를 사용한다. 아울러 리스트를 사용하면 deque를 쓰는 것과 마찬가지 효과를 낼 수 있지만 deque를 사용하면 스택, 큐 작업 시 다음과 같은 장점이 있으니 참고하자.

• deque는 list보다 속도가 빠르다. pop(0)와 같은 메서드를 수행할 때 리스트라면 O(N) 연산을 수행하지만, deque는 O(1) 연산을 수행하기 때문이다.
• 스레드 환경에서 안전하다.