데크(deque)

데크(deque)의 개념

• 보통 큐(queue)는 선입선출(FIFO) 방식으로 작동한다.
• 반면, 양방향 큐가 있는데 그것이 바로 데크(deque)다.
  • 앞, 뒤 양쪽 방향에서 엘리먼트(element)를 추가하거나 제거할 수 있다.
  • 데크는 양 끝 엘리먼트의 append와 pop이 압도적으로 빠르다.
• 덱(Deque)은 어떤 쪽으로 입력하고 어떤 쪽으로 출력하느냐에 따라서 스택(Stack)으로 사용할 수도 있고, 큐(Queue)로도 사용할 수 있다.
• 시간 복잡도 : 일반적인 리스트(list)가 이러한 연산에 O(n)이 소요되는 데 반해, 데크(deque)는 O(1)로 접근 가능

데크(deque) 사용법

• 데크는 다음처럼 임포트(import)해 사용한다.

from collections import deque
deq = deque()

# Add element to the start
deq.appendleft(10)

# Add element to the end
deq.append(0)

# Pop element from the start
deq.popleft()

# Pop element from the end
deq.pop()
데크(deque)에 존재하는 메서드(method)는 대략 다음과 같다.

• 기본 메소드
  • deque.append(value) : value를 데크의 오른쪽 끝에 삽입한다.
  • deque.appendleft(value) : value를 데크의 왼쪽 끝에 삽입한다.
  • deque.pop() : 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
  • deque.popleft() : 데크의 왼쪽 끝 엘리먼트를 가져오는 동 - 시에 데크에서 삭제한다.
  • deque.remove(value) : item을 데크에서 찾아 삭제한다.
• 참고 메소드
  • deque.extend(array) : 주어진 배열(array)을 순환하면서 데크의 오른쪽에 추가한다.
  • deque.extendleft(array) : 주어진 배열(array)을 순환하면서 데크의 왼쪽에 추가한다.
  • deque.rotate(num) : 데크를 num만큼 회전한다(양수면 오른쪽, 음수면 왼쪽).
• 참고 메소드 예시 : rotate()

# Contain 1, 2, 3, 4, 5 in deq
deq = deque([1, 2, 3, 4, 5])

deq.rotate(1)
print(deq)
# deque([5, 1, 2, 3, 4])

deq.rotate(-1)
print(deq)
# deque([1, 2, 3, 4, 5])

데크는 언제 (유용하게) 사용하나?

• 시작점의 값을 넣고 빼거나, 끝 점의 값을 넣고 빼는 데 최적화된 연산 속도를 제공한다.
• 즉, 대부분의 경우에 데크(deque)는 리스트(list)보다 월등한 옵션이다.
  = 데크는 특히 push/pop 연산이 빈번한 알고리즘에서 리스트보다 월등한 속도를 자랑한다.

References

• Python - 데크(deque) 언제, 왜 사용해야 하는가?