[Python]파이썬, 왜 리스트대신 큐/ 데크 deque 를 쓸까?

 

Python deque 

deque 라는 것은 쉽게 말하자면 파이썬의 list 와 같이 요소들을 한 곳에 담아두는 배열이다. 

파이썬에서 큐 queue는 First In First Out (FIFO) 의 방식으로 작동된다. 덱(데큐)는 큐는 큐이지만 양방향인 queue이다. 양 쪽 방향 모두에서 (앞, 뒤) 요소를 추가/ 제거할 수 있다. 

 

 

 

 

List도 있는데 굳이 deque를 사용하는 이유는 ? 

간략하게 말하자면 List 보다 deque의 속도가 훨씬 빠르기 때문이다. list는 O(n) 의 속도, deque는 O(1)의 속도이다. 

 

요기 표에서 보다시피 O(1)의 속도가 가 - 장 좋은 best 속도이다. 그게 바로 deque ! 연산이 많을수록 안쓸 이유가 없다. 처음 deque알고리즘을 풀어보며 왜 리스트와 같은데 굳이 이걸 import를 해와서 귀찮게 쓸까 ? 생각했는데 찾아보니 위와같은 속도 , 성능면에서의 장점때문이었다. 

 

특히 append/ remove / push / pop 연산이 자주 일어나는 알고리즘에서 장점을 부각시킬 수 있다. Deque는 스택(stack)으로도, Queue(큐)로도 사용할 수 있다. 

 

결론 : Deque 은 아주 성능좋은 편리한 LIST-LIKE 매서드다 ! 

 

2022.9.14 내용 추가

Deque은 max length 를 지정해줄 수 있다. (아래에 코딩 테스트에서 사용할 수 있는 법을 첨부)

 

 

Deque를 쓰는 방법 

먼저 import 를 해주고 변수 = deque() 을 선언함으로써 해당 deque 를 사용할 수 있다. 

from collections import deque


a = deque()
print(a)

 

 

 

Deque 매서드들 ( List와 비교해보기 ! ) 

q = deque()
매서드	설명	List 매서드와 일치 여부
q.append(item)	오른쪽 끝에 삽입	O (List에도 해당 매서드 존재)
q.appendleft(item)	왼쪽 끝에 삽입	X
q.pop()	가장 오른쪽의 요소 반환 및 삭제	O
q.popleft()	가장 왼쪽의 요소 반환 및 삭제	X
q.extend(array)	주어진 array 배열을 순환하며 q의 오른쪽에 추가	O
q.extendleft(array)	주어진 array 배열을 순환하며 q의 왼쪽에 추가	X
q.remove(item)	해당 item q에서 찾아 삭제	O
q.rotate(숫자)	해당 숫자만큼 회전 (양수 : 시계방향, 음수 : 반시계 방향)	X

 

 

 

예시를 보며 더 쉽게 이해해보기

from collections import deque

q = deque([1,2,3])
print('%-25s' %'original q =',q)

q.append(4)
print('%-25s' %'after append(4) = ',q)
q.appendleft(0)
print('%-25s' %'after appendleft(0) =',q,'\n')

q.pop()
print('%-25s' %'after pop() =',q)
q.popleft()
print('%-25s' %'after popleft() =',q,'\n')

arr1 = [10,11,12]
q.extend(arr1)
print('%-25s' %'after extend(arr) =',q)

arr2 = [-2,-1,0]
q.extendleft(arr2)
print('%-25s' %'after extendleft(arr2) =',q,'\n')

q.remove(-2)
q.remove(-1)
print('%-25s' %'after remove -1,-2 =', q)

q.rotate(1)
print('%-25s' %'after rotate(1) =',q)
q.rotate(2)
print('%-25s' %'after rotate(2) =',q)
q.rotate(-3)
print('%-25s' %'after rotate(-4) =', q)

 

 

 

 

Max length을 정할 수 있는 Deque ! 

from collections import deque

def solution(n, a):
    cache = deque(maxlen=n)
	.
    .
    .

위와 같이 deque를 처음 선언할 때 최대 길이값을 설정해 놓을 수 있다. 일반 [] 리스트일 경우에는 길이에 맞춰 pop 또는 remove를 해주어야하는데 deque은 이 기능으로 편리하게 사용 가능하다. 

 

 

 

---

 

 

 

실제 Queue 를 사용한 알고리즘 문제 풀이 

https://codingpractices.tistory.com/49

[백준] 2623번 음악 프로그램 / 위상 정렬 알고리즘

 

2018 KAKAO BLIND RECRUITMENT 해시 문제에서 Deque의 maxlength 를 활용할 수 있다. 

https://school.programmers.co.kr/learn/courses/30/lessons/17680

프로그래머스