deque

문제를 풀다가 deque라는 것을 봤는데 스택과 큐의 기능을 한번에 한다고 하니 매우 유용할 것 같다 ! 한번 알아보자 ..

 

deque

데크 디큐 덱 뎈.... 그냥 덱 이라고 부르겠다. 덱은 출입구가 양쪽에 있어서 스택과 큐의 기능을 동시에 가진다. 덱은 다음과 같이 선언하거나, 변환한다. 코드를 보면 알 수 있듯, 기존에 선언된 리스트를 덱으로 변환하는 것도 가능하다. 

from collections import deque

truck = [7, 4, 5, 6]
truck = deque(truck) # 덱으로 변환
onthebridge = deque([0] * bridge_length) # 덱으로 초기화

장점

덱은 리스트보다 속도가 빠르다. pop(0)을 할 때 리스트는 O(N)인데, 덱은 앞뒤 모두 접근하기에 O(1)이 된다.

append(), pop()

append는 스택처럼 오른쪽 끝에 원소를 추가하고, pop은 큐처럼 오른쪽 끝의 원소를 삭제한다.

appendleft(), popleft()

반대로, 왼쪽에 대해서 값을 입력하고 빼고 싶다면 appendleft, popleft를 사용한다.

extend(), extendleft()

덱을 확장할 땐 extend를 쓰는데, 오른쪽으로 확장할 땐 extend(), 왼쪽으로 확장할 땐 extendleft()이다.

rotate()

덱을 쓰면 리스트를 쉽게 회전시킬 수 있다.

from collections import deque

example = [1, 2, 3, 4, 5]
dq = deque(example)
dq.rotate(2)  # 2라고 쓰면 양수이므로 시계방향으로 2번 회전한다.

결과 : 4 5 1 2 3

만약 -2라고 하면 반시계로 2번 회전하는 것이므로 3 4 5 1 2 가 되는 것이다.

번외

추가로, 리스트처럼 insert, remove, reverse가 가능하다. 처음부터 덱을 쓰는 게 확실히 더 다양성이 높아지는 것 같다.