[Python] Collections - deque | 개념, 메소드, list와의 차이

알고리즘 문제를 풀다보면 자주 사용하는 Collections 라이브러리의 deque 클래스에 대해 알아보자 !

 

 

1. Deque란?

양방향에서 큐를 처리할 수 있는 자료구조

 

queue(큐)는 FIFO(First in, First out), 즉 먼저 들어간 원소가 먼저 나오는 선입선출 자료구조이다. deque는 양방향 큐의 구조이기에 앞, 뒤 양쪽 방향에서 element 추가/제거가 가능한 유용한 자료구조이다.

 

 

2. deque의 메소드(Method)

 

- append(x)

: deque 오른쪽에 x를 추가

 

from collections import deque

d = deque('abc') # deque 생성

d.append(1) 

print(list(d)) # list형으로 출력
# ['a','b','c',1]

 

- appendleft()

: deque 왼쪽에 x를 추가

 

from collections import deque

d = deque('abc') # deque 생성

d.appendleft(1) 

print(list(d)) # list형으로 출력
#[1, 'a', 'b', 'c']

 

- pop()

: 데크의 오른쪽 끝에 있는 요소를 삭제하고 반환하며 그 전에 남아있는 요소가 없다면 IndexError 발생

 

from collections import deque

d = deque('abc') # deque 생성

d.pop()

print(list(d))
# ['a','b']

 

- popleft()

: 데크의 왼쪽 끝에 있는 요소를 삭제하고 반환하며 그 전에 남아있는 요소가 없다면 IndexError 발생

 

from collections import deque

d = deque([1,2,3]) # deque 생성

d.popleft()

print(list(d))
# [2,3]

 

- extend()

: iterable argument의 element를 추가하여 데크의 오른쪽을 확장

 

from collections import deque

d = deque([1,2,3]) # deque 생성

d.extend([4,5])

print(list(d))
# [1,2,3,4,5]

 

append와 extend가 헷갈릴 수 있는 데 extend()는 iterable argument(list, set, string, bytes, dictionary..)의 요소만 추가할 수 있다. 

 

즉, 다음과 같은 코드는 error가 발생한다.

 

from collections import deque

d = deque([1,2,3]) # deque 생성

d.extend(4)

print(list(d))
# TypeError: 'int' object is not iterable

 

- extendleft()

: iterable argument의 element를 추가하여 데크의 오른쪽을 확장, 이 때 추가한 요소는 예시와 같이 반대 순서로 삽입된다. 

 

from collections import deque

d = deque([1,2,3]) # deque 생성

d.extendleft([4,5])

print(list(d))
# [5, 4, 1, 2, 3]

 

- rotate(n)

: n>0의 경우 deque의 요소를 n칸씩 오른쪽으로 이동시킨다. n<0의 경우 반대 방향으로 절대값만큼 이동한다.

 

from collections import deque

d = deque(['a','b','c','d','e']) # deque 생성

d.rotate(1) # ['e', 'a', 'b', 'c', 'd']

from collections import deque

d = deque(['a','b','c','d','e']) # deque 생성

d.rotate(2) # ['d', 'e', 'a', 'b', 'c']

from collections import deque

d = deque(['a','b','c','d','e']) # deque 생성

d.rotate(-1) # ['b', 'c', 'd', 'e', 'a']

 

3. list와 deque의 차이점

 

데이터양이 많을수록 list보다 연산속도 면에서 효율적인 deque을 사용하는 것이 좋을 것 같다. 

 

 

 

 

※ docs.python.org 의 collections - deque를 참고하였습니다.