[python] 데크(deque)란?

데크(deque)의 개념 

• 큐(queue)
  • 선입선출(FIFO) 방식
• 데크(deque)
  • 양방향 큐
  • 앞, 뒤 양쪽 방향에서 element 추가 제거 가능
  • append와 pop이 압도적으로 빠름
  • 컨테이너(container)의 양끝 엘리먼트(element)에 접근하여 삽입 또는 제거의 경우, 일반적인 리스트(list)는 O(n) 소요, 데크(deque)는 O(1) 소요

사용법 

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

# 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) 언제,왜 사용해야할까? 

• 데크(deque)는 스택처럼 사용할 수도 있고, 큐(queue)처럼 사용할 수도 있음
• 시작과 끝 점의 값을 넣고 빼는 데 최적화된 연산 속도 제공
• push/pop이 빈번한 알고리즘에서 월등한 속도!

 

---

참고자료

https://chaewonkong.github.io/posts/python-deque.html