[자료구조] Deque(덱,데크, Double-ended-queue)

Deque(덱,데크)이란?

덱(deque)은 double-ended queue의 줄임말이다.

후단(rear)으로만 데이터를 삽입했던 기존 선형 큐, 원형 큐와 달리 큐의 앞(front)과 뒤(rear)에서 모두 삽입과 삭제가 가능한 큐를 말한다.

Deque는 언제 사용하는가?

데크(deque)는 스택처럼 사용할 수도 있고, 큐 처럼 사용할 수도 있다. 스택과 큐의 장점을 모두 채택하였기 때문에 데이터를 넣고 빼는 것이 List 자료형에 비해 효율적이고, 속도도 빠르다. queue라이브러리를 이용하는 것보다 간단하다. 따라서 데크는 특히 push/pop 연산이 빈번한 알고리즘에서 리스트보다 월등한 속도를 자랑한다.

 

Deque 사용하기

from collections import deque

deque 자료구조는 collections 모듈을 import 하면 사용할 수 있다.

 

Deque 함수 설명

eque.append(item): item을 데크의 오른쪽 끝에 삽입

deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입

deque.pop(): 데크의 오른쪽 끝 값을 가져오고 데크에서 삭제

deque.popleft(): 데크의 왼쪽 끝 값을 가져오고 데크에서 삭제

deque.extend(array): 주어진 리스트를 순환하면서 데크의 오른쪽에 추가

deque.extendleft(array): 주어진 리스트를 순환하면서 데크의 왼쪽에 추가

deque.remove(item): 데크에서 item을 찾아 삭제

deque.rotate(num): 데크를 num만큼 회전(양수면 오른쪽 / 음수면 왼쪽)

 

Deque 사용하기

 

from collections import deque

deq = deque([3]) # 3이 있는 deque 생성
print(deq)
deq.appendleft(10)
deq.append(0)

print(deq)  # deque([10, 3, 0])
print(deq.popleft())
print(deq.pop())
print(deq)  # deque([5, 1, 2, 3, 4])

처음 deque에 3을 넣은 상태로 생성하였다.

그리고 appendleft()를 사용하여 왼쪽에 10, append()를 사용하여 오른쪽에 0을 추가하였다

그리고 popleft()를 사용하여 오른쪽 10을 꺼내오고, pop()을 사용하여 오른쪽 0을 꺼내왔다.

 

코드 결과

from collections import deque

deq = deque([1, 2, 3, 4, 5])
print(deq)
deq.rotate(1)
print("오른쪽으로 회전:",deq) # deque([5, 1, 2, 3, 4])

deq.rotate(-1)
print("왼쪽으로 회전:",deq) # deque([1, 2, 3, 4, 5])

[1,2,3,4,5]가 들어가있는 deque를 생성하였다.

그리고 rotate(1)을 사용하여 오른쪽으로 1 회전 한 결과를 확인하고, roate(-1)을 사용하여 왼쪽으로 1 회전한 결과를 출력하였다.