데크(Deque)

데크(Deque)란?

• 큐(queue)는 선입선출(FIFO) 방식으로 작동
• 그에 반면 양방향 큐가 있는데 바로 Deque
• 앞, 뒤 양쪽 방향에서 엘리먼트를 추가 혹은 삭제할 수 있음
• 데크는 양 끝 엘리먼트의 append 와 pop이 빠른 장점이 있다
• 컨테이너의 양 끝 엘리먼트에 접근하여 삽입 또는 제거를 할 경우, 일반적인 리스트가 이러한 연산에 O(n)이 소요되는데 반해, 데크(Deque)는 O(1)로 접근 가능하다

데크 사용법

• 아래와 같이 데크를 임포트 하여 사용한다

from collections import deque

deq = deque()

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

# 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만큼 회전한다(양수면 오른쪽, 음수면 왼쪽).

rotate

# item list
deq = deque([1,2,3,4,5])

def.ratate(1)
print(deq)

# deque([5, 1, 2, 3, 4])

def.ratate(-1)
print(deq)

# deque([1, 2, 3, 4, 5])

Deque 언제 쓰는것이 좋을까?

• 데크는 스택처럼 사용할 수도 있고, 큐 처럼 사용할 수도 있다
• 시작점의 값을 넣고 빼거나, 끝 점의 값을 넣고 뺄때 최적화된 연산 속도를 제공하기때문에 데크는 리스트보다 효율적이다
• 특히 push와 pop 연산이 빈번한 알고리즘이라면 리스트보다 뛰어난 속도를 보여주기때문에 데크를 사용하면 좋다