10장. 데크, 우선순위 큐

✅ 데크

데크는 더블 엔디드 큐(Double Ended Queue)의 줄임말로, 글자 그대로 양쪽 끝을 모두 추출할 수 있는, 큐를 일반화한 형태의 추상 자료형이다.

• 양쪽에서 삭제와 삽입을 모두 처리 가능

• 스택과 큐의 특징을 모두 갖고 있다.

• 이 추상자료형의 구현은 배열이나 연결 리스트 모두 가능하지만, 특별히 다음과 같이 이중 연결리스트로 구현하는 편이 가장 잘 어울린다.

• 파이썬은 데크 자료형을 collections 모듈에서 deque라는 이름으로 지원한다.
• 리스트의 pop(0) 는 O(n)에 실행되는데 반해(n부터 0까지 조회해야 하므로), deque의 popleft()는 O(1)에 실행가능하다.
• 파이썬에서 큐의 경우에는 deque로 구현하는 것이 좋다.
 

문제 리스트

✅ 우선순위 큐

우선순위 큐는 큐 또는 스택과 같은 추상자료형과 유사하지만 추가로 각 요소의 ‘우선순위’와 연관되어 있다.

• 특정 조건에 따라 우선순위가 가장 높은 요소가 추출되는 자료형

문제 리스트