데크(Deque), 우선순위 큐(Priority Queue)

 

데크(Deque)	우선순위 큐(Priority Queue)
스택과 큐의 특징을 모두 가지고 있는 복합 자료형으로 양쪽에서 삭제와 삽입을 모두 처리할 수 있음 이중 연결 리스트(가장 좋음), 배열, 연결 리스트로 구현 가능	어떤 특정 조건에 따라 우선 순위가 가장 높은 요소가 추출되는 자료형 -> 정렬 알고리즘을 기반으로 함 ex. 가장 큰 값을 추출하는 최댓값 추출
기본 리스트 자료형의 경우, 맨 뒤쪽 원소를 기준으로 삽입, 삭제를 수행하기 때문에 연산 리스트에 포함된 데이터의 수에 따라 시간 복잡도가 O(N)임 * append(), pop() deque에서는 리스트 자료형과 다르게 인덱싱, 슬라이싱 등의 기능은 사용할 수 없지만 연속적으로 나열된 데이터의 시작 혹은 끝부분에 데이터 삽입 및 삭제 시 매우 효과적임 * popleft() : 첫번째 원소 제거 시 사용 * pop() : 마지막 원소 제거 시 사용 * appendleft(x) : 첫번째 인덱스에 원소 x를 삽입 * append(x) : 마지막 인덱스에 원소 x를 삽입	queue 모듈의 PriorityQueue(이또한 내부적으로는 heapq를 사용함)클래스를 사용할 수 있으나 주로 heap 사용하여 주로 구현함. *heapq는 다익스트라 최단 경로 알고리즘을 포함하여 우선순위 큐 기능을 구현할 때 사용함 *heapq.heappush() : 힙에 원소 삽입 *heapq.heappop() : 힙에서 원소를 꺼냄 파이썬에서는 최대 힙(max heap)을 제공하지 않음