자료구조 스택과 큐 (2)- 덱(Deque)

"덱(Double-Ended Queue,Deque)"
“덱(Deque)은 양방향에서 삽입/삭제 연산이 이루어지는 자료구조 이다.”

deque는 python의 list와 비슷하다.
엥?
list랑 유사하면 list 쓰면되지 왜 deque라는 자료구조가 있는걸까?

이는,시간복잡도 차이가 나기 때문에
효율적인 데이터 삽입/삭제 연산을 하기 위해서 이다.

가령,list는,맨 앞 원소(idx 0번)를 삭제할 때
삭제연산 후 나머지 원소들의 재배열이 일어난다.
이 재배열의 연산은 약 O(N)의 시간이 걸린다.
원소 수가 무지하게 많은 list의 경우 시간이 더 걸릴 것이다.

반면,
deque는 stack과 queue 성질을 합쳐 놓은 자료구조라 생각하면된다.
선입선출(FIFO)의 성질을 가지며,
rear에서 원소 삽입/front에서 원소 삭제가 일어나는 양방향의 queue.
후입선출(LIFO)의 성질을 가지며
top이란 위치에서 원소 삽입/삭제가 일어나는 단방향의 stack.
이 둘의 성질을 합친 deque는,
양방향 각각에서 삽입/삭제 연산이 가능한 자료구조이다.

게다가,
앞서 list의 삭제 연산 시간복잡도보다 훨씬 빠른
양 방향 끝부분의 원소 삭제/삽입 연산의 시간복잡도는 O(1)이다.

아래는 python 자체 패키지 collections에서 import한 deque이다.

from collections import deque #deque import
dq = deque('data') #선언 및 "d/a/t/a" 원소 삽입
for elem in dq: #deque 안에 있는 원소 대문자로 출력
    print(elem.upper(), end ='')
print()
dq.append('r') #맨 끝 원소 삽입 (append)
dq.appendleft('k') #맨 앞 원소 삽입 (appendleft)
print(dq) #deque 출력
dq.pop() #맨 끝 원소 삭제 (pop)
dq.popleft() #맨 앞 원소 삭제 (popleft)
print(dq[-1]) #맨 뒤 원소 출력
print('x' in dq) #탐색  
dq.extend('structure') #맨 끝 원소 추가 (extend)
dq.extendleft(reversed('python')) #맨 앞 원소 추가 (extendleft)
print(dq) #덱 출력

#실행결과
DATA
deque(['k', 'd', 'a', 't', 'a', 'r'])
a
False
deque(['p', 'y', 't', 'h', 'o', 'n', 'd', 'a', 't', 'a', 's', 't', 'r', 'u', 'c', 't', 'u', 'r', 'e'])

+ 이외에도 여러가지 함수들이 있다.

• 자료구조
• 이론