[자료구조] 2-4. 덱(deque)

덱

덱(deque)는 double - ended - queue의 줄임말로, 앞뒤로 빼고, 넣는 것이 가능한 자료구조이다.

큐와 스택을 합친 자료구조라고 볼 수도 있다.

파이썬에서는 collections 라는 모듈에서 쉽게 사용할 수 있다.

덱은 머리든, 꼬리든, 양옆으로 데이터를 넣고 뺄 수 있다.

리스트와 비슷해보이는 연산들이 있지만, 들여다보면 차이가 존재한다.

리스트는 맨 앞 데이터를 빼면, 뒤에 있는 데이터들이 다 앞으로 당겨져서 시간복잡도가 O(n)이 된다.

덱은 이중 연결리스트 기반으로 구현되어, 맨 앞 데이터를 빼더라도 시간복잡도가 O(1)이다.

 

덱의 연산

• appendleft(): 앞쪽으로 데이터 enqueue
• popleft(): 앞쪽에서 데이터 dequeue
• append(data): 뒤쪽으로 데이터 enqueue
• pop(): 뒤쪽에서 데이터 dequeue

덱 라이브러리에서 추가로 제공하는 연산들

• remove(data): 특정 데이터 삭제(같은 항목이 있으면 왼쪽에 있는 것부터 사라진다.)
• clear(): 덱 비우기(모든 데이터 삭제)
• extend(iterable 데이터): 덱 뒤쪽에 iterable 데이터를 붙일 수 있다. extendleft를 이용하면 앞쪽에 붙일 수 있다.
• rotate(정수): 입력된 수만큼 꼬리의 데이터를 pop하여 순차적으로 appendleft한다.(n칸씩 회전시킨다.)
• reverse(): 안에 있는 데이터들의 순서를 뒤집는다.

덱 사용예시

from collections import deque
 
dq = deque()
 
dq.append(3)     #[3]
dq.appendleft(4)    #[4, 3]
dq.appendleft(7)    #[7, 4, 3]
dq.append(4)        #[7, 4, 3, 4]
 
dq.remove(4)        #[7, 3, 4]
 
a = [9, 8, 7]
 
dq.extend(a)        #[7, 3, 4, 9, 8, 7]
 
dq.rotate(2)        #[8, 7, 7, 3, 4, 9]
 
dq.reverse()        #[9, 4, 3, 7, 7, 8]