[Algorithm] 덱(데크)

Deque(덱/데크)

• 양방향 큐 (스택처럼도 이용 가능)
• 앞, 뒤 양쪽 방향에서 data 추가 가능 -> append, pop 보다 성능이 좋음
• append, pop 은 O(n) 이 소요되고, deque 는 O(1) 이 소요됨
• list 보다 월등한 성능을 보임 -> 시간초과가 나는 경우 deque 를 사용해 보자!

덱 사용

from collections import deque
deq = deque([1, 2, 3, 4, 5])

deq.appendleft(10)
deq.append(0)
deq.popleft()
deq.pop()
deq.rotate(1)  # deque([5, 1, 2, 3, 4])
deq.rotate(-1)  # deque([1, 2, 3, 4, 5])

덱 명령

• deque.append(x) : 오른쪽 끝 삽입
• deque.appendleft(x) : 왼쪽 끝 삽입
• deque.pop() : 오른쪽 끝 pop
• deque.popleft() : 왼쪽 끝 pop
• deque.extend(array) : array 를 오른쪽 끝에 추가
• deque.extendleft(array) : array 를 왼쪽 끝에 추가
• deque.remove(x) : x 를 찾아서 제거
• deque.rotate(num) : 데크를 num만큼 회전(양수면 오른쪽, 음수면 왼쪽)

BFS/DFS 를 deque 로 구현함