[자료구조] collections module - deque

 

1. deque

덱은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태이다. 두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생 시킬 수 있다. 큐와 스택을 합친 형태로 생각할 수 있다.

Deque

파이썬에서는 collections 모듈을 이용하여 deque를 사용할 수 있다.
import collections
dq = collections.deque() 로 생성

from collections import deque
dq = deque() 로 생성

list와 동일하게 append(), pop()을 사용할 수 있으며 추가적으로 appendleft(), popleft()도 사용할 수 있다.
list.pop(0)이나 list.insert(0, number) 을 이용하면 기본 기능을 이용해서도 구현할 수 있지만
list의 경우 맨 앞에 삽입과 삭제시 나머지 항목들을 이동하는 연산때문에 상당히 많은 시간이 소모된다.

이런 느낌으로 이해하면 쉽다.

 

2. append(x)

list.append(x)와 마찬가지로 x를 deque의 오른쪽에 추가(삽입)해준다.

 

3. appendleft(x)

deque의 왼쪽에 추가(삽입)해준다.

 

4. extend(iterable)

list.extend(iterable)과 마찬가지로 iterable argument(list, str, tuple...)를 오른쪽에 elements를 추가(삽입)해주는 메소드이다.

5. extendleft(iterable)

마찬가지로 왼쪽에서 데이터를 추가해주는 메소드이다.

6. pop()

list.pop()과 같이 오른쪽(마지막)에서 부터 차례대로 제거와 반환(remove and return)을 하는 메소드이다.

 

7. popleft()

pop()의 반대로, 왼쪽(앞쪽)에서 부터 차례대로 제거와 반환(remove and return)을 하는 메소드이다.

8. rotate(n)

collections.deque.rotate(n)은 요소들을 n값 만큼 회전 해주는 메소드이다. n의 값이 음수이면 왼쪽으로 회전하고, n의 값이 양수이면 오른쪽으로 회전한다