(Python) Deque

파이썬에는 List라는 데이터를 담을 수 있는 자료형이 존재한다.

하지만 다양한 알고리즘 문제를 풀이하다보면, List 대신 Deque를 사용하는 경우가 있는데 과연 Deque란 무엇이고, 왜 이것을 사용하는걸까?

 

Deque란?

Deque는 Double-ended queue의 줄임말로써 큐의 앞과 뒤, 즉 양방향으로 삽입과 삭제가 가능한 큐이다.

Deque 사용하기

Deque 자료형은 collection에서 불러와야하기 때문에 다음과 같은 선언문이 필요하다.

from collections import deque

 

이후에 다음과 같이 선언하여 하나의 새로운 Deque를 만들 수 있다.

arr = deque()

Deque 메소드

Deque에도 List와 마찬가지로 내부의 데이터들을 관리하기 위한 다양한 메소드들이 존재한다.

메소드 이름	기능
append(x)	값 x를 Deque의 오른쪽(마지막)에 넣어준다.
appendleft(x)	값 x를 Deque의 왼쪽(처음)에 넣어준다.
clear()	Deque 안의 모든 데이터를 지워준다.
copy()	Deque의 얕은 복사본을 만들어준다.
count(x)	값 x가 Deque 내에 몇 개 존재하는지 세어준다.
extend(iterable)	iterable 객체를 Deque의 오른쪽(마지막)에 넣어준다.
extendleft(iterable)	iterable 객체를 Deque의 왼쪽(처음)에 넣어준다.
index(x[, start[, stop]])	Deque내에서 첫번째로 일치하는 값 x의 위치(인덱스)를 반환한다. 존재하지 않는다면 ValueError를 발생시킨다.
insert(i, x)	Deque의 특정한 인덱스 i에 값 x를 넣어준다. Deque의 maxlen이 설정된 경우, 이를 초과하는 위치에 값을 넣으려한다면 IndexError를 발생시킨다.
pop()	Deque의 오른쪽(마지막)에 위치한 값을 삭제시키고 해당 값을 반환한다. Element가 존재하지 않는다면, IndexError를 발생시킨다.
popleft()	Deque의 왼쪽(처음)에 위치한 값을 삭제시키고 해당 값을 반환한다. Element가 존재하지 않는다면, IndexError를 발생시킨다.
remove(value)	Deque에서 특정한 value가 첫번째로 등장하는 경우에 그 값을 삭제한다. 특정 value가 존재하지 않는다면, ValueError를 발생시킨다.
reverse()	Deque내의 값들을 역순으로 정렬한다.
rotate(n=1)	Deque안의 요소들을 n의 값만큼 오른쪽으로 회전시켜준다. 만약 n의 값이 음수라면 왼쪽으로 회전시킨다.
maxlen	deque([], maxlen)의 형식으로 해당 deque의 최대 크기를 지정할 수 있다.

Deque와 List의 차이점

그렇다면 왜 List 대신에 Deque를 사용하는 것일까?

List는 데이터 삽입과 삭제에 log(N), 선형 시간이 소요된다.

하지만 이와 다르게 Deque에서는 데이터 삽입과 삭제에 log(1), 상수 시간만이 소요된다.

pop(), push() 등의 연산이 자주 사용되는 문제 풀이 시에는 Deque를 사용하는 것이 성능면에서 유리하기 때문에 List보단 Deque를 자주 사용하는 것이다.

또한 Deque는 Stack과 Queue의 성질을 모두 가지고 있기 때문에, Stack과 Queue로 동시에 사용할 수 있다는 장점 또한 존재한다.

관련 문제

https://www.acmicpc.net/problem/2164

2164번: 카드2