덱(Deque)

덱(Deque)

스택과 큐의 기능을 모두 가지고 있다.

포인터 변수가 더 많이 필요하기 때문에, 메모리는 상대적으로 더 많이 필요하다.

Python에서 큐(queue)의 기능이 필요할 때, 간단히 덱(deque)을 사용한다.

데이터 삭제와 삽입 모두에서 0(1)의 시간 복잡도가 소요된다.

 

덱의 동작 예시

좌측 삽입4 좌측 삽입3 좌측 삽입2 좌측 삽임1

우측 삽입5 우측 삽입6 우측 삽입7 우측 삽입8

우측 삭제 좌측 삭제 우측 삭제 좌측 삭제

최종 : 3 4 5 6

 

덱의 시간 복잡도

	연산	수행 시간	설명
1	좌측 삽입(Append Left)	O(1)	덱의 가장 왼쪽에 새 데이터 삽입
2	좌측 삭제(Pop Left)	O(1)	덱의 가장 왼쪽에서 데이터 추출
3	우측 삽입(Append Right)	O(1)	덱의 가장 오른쪽에 새 데이터 삽입
4	우측 삭제(Pop Right)	O(1)	덱의 가장 오른쪽에서 데이터 추출

 

 

덱(Deque) 라이브러리

우측 삽입 : append()

좌측 삽입 : appendleft()

우측 추출 : pop()

죄측 추출 : popleft()

 

파이썬에서 덱을 사용하는 경우

파이썬에는 기본적으로 리스트 자료형 큐의 기능을 제공하지 않는다.

가능하면 파이썬에서 제공하는 덱 라이브러리를 사용한다.

큐의 기능이 필요할 때는 덱 라이브러리를 사용하는 것을 추천한다.

삽입과 삭제에 대하여 모두 시간 복잡도 O(1)를 요구된다.