[python] deque 사용해보기

오늘은 이전부터 많이 사용해왔지만 popleft()만 활요해왔던 deque 객체에 대해 정리해보려고 한다.

보통 deque는 코딩테스트 시에 파이썬에서 기본적으로 제공하는 리스트를 큐로 사용하는 것보다 효율적이여서 사용할 것이다.

효율적이라고 말할 수 있는 대표적인 이유는 원소를 팝할 때이다.

기존적으로 큐라는 자료구조는 FIFO이기 때문에 리스트를 큐로 사용한다면 원소를 팝할 때 list.pop(0)메소드를 사용할 것이다.

여기서 list.pop(0)은 시간복잡도가 O(n)이라는 것을 알아야한다.

위 그림과 같이 pop(0)을 실행하면 그 후에 뒤에 있던 값들이 한 칸씩 당겨지면서 앞 칸을 채우는 작업이 이루어진다.

그래서 pop(0)은 시간복잡도가 O(n)이다.

하지만, deque로 큐를 만들고 popkleft()를 사용하면 시간복잡도가 O(1)이다.

여기서 우리는 deque의 효율성을 얻을 수 있는 것이다.

 

그러면 지금부터 deque 객체에 대해 자세히 알아보자.

deque 객체는 파이썬 표준 라이브러리 중 collections 모듈에 있는 객체 중 하나이다.

deque 객체는 다음과 같은 메서드를 지원한다:

 

1) append(x)

데크의 오른쪽에 x를 추가한다.

from collections import deque

queue = deque()
queue.append(1)
queue.append(2)

print(queue)
#결과: deque([1, 2])

 

 

2) appendleft(x)

데크의 왼쪽에 x를 추가한다.

from collections import deque

queue = deque()
queue.append(1)
queue.append(2)

print(queue)
#결과: deque([1, 2])

queue.appendleft(3)
print(queue)
#결과: deque([3, 1, 2])

 

 

3) clear()

데크에서 모든 요소를 제거하고 길이가 0인 상태로 만든다.

from collections import deque

queue = deque()
queue.append(1)
queue.append(2)

print(queue)
#결과: deque([1, 2])

queue.clear()
print(queue)
#결과: deque([])

 

 

5) count(x)

데크 안에서 x와 같은 요소의 수를 반환해준다.

from collections import deque

queue = deque()
queue.append(1)
queue.append(2)
queue.append(2)
queue.append(2)

print(queue)
#결과: deque([1, 2, 2, 2])

print(queue.count(2))
#결과: 3

 

 

 

6) insert(i, x)

x를 데크의 i 위치에 삽입한다.

여기서 i는 index번호를 의미한다.

만약에 삽입후 제한된 길이의 데크가 maxlen 이상으로 커지면 IndexError가 발생시킨다.

from collections import deque

queue = deque()
queue.append(1)
queue.append(2)
queue.append(2)
queue.append(2)

print(queue)
#결과: deque([1, 2, 2, 2])

queue.insert(1, 3)
print(queue)
#결과: deque([1, 3, 2, 2, 2])
#인덱스번호 1에 3이 들어간 것을 확인할 수 있음.

 

 

7) pop()

데크의 맨 오른쪽에서 요소를 제거하고 해당 요소를 반환한다. 데크가 비어있다면 IndexError를 발생시킨다.

from collections import deque

queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)

pop_value = queue.pop()
print(pop_value, queue)
#결과: 4, deque([1, 2, 3])

 

 

8) popleft()

데크의 맨 왼쪽에서 요소를 제거하고 해당 요소를 반환한다. 데크가 비어있다면 IndexError를 발생시킨다.

from collections import deque

queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)

pop_value = queue.popleft()
print(pop_value, queue)
#결과: 1, deque([2, 3, 4])

 

 

9) remove(value)

데크 안에 있는 요소 중 value와 같은 값 중에서 첫 번째 요소를 제거한다.

value와 같은 값이 데크에 없다면 ValueError를 발생시킨다.

from collections import deque

queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(2)

queue.remove(2)
print(queue)
# 결과: deque([1, 3, 2])
# 데크 안에서 2개의 2 중에서 먼저 있는(더 왼쪽에 있는)2를 제거

 

 

10) reverse()

데크의 요소들을 제자리에서 순서를 뒤집고 None을 반환한다.

from collections import deque

queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)

print(queue)
# 출력: deque([1, 2, 3, 4])

queue.reverse()
print(queue)
# 출력: deque([4, 3, 2, 1])

 

 

위에서 알아 본 10가지의 메소드 이외에도 다양한 메소드가 존재한다.

더 자세히 알고싶다면 아래 링크를 확인하면 될 것같다.

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

collections — 컨테이너 데이터형 — Python 3.9.6 문서