파이썬 알고리즘 인터뷰 - 데크, 우선순위 큐

데크

이중 연결 리스트로 구현한 데크 구조

• 더블 엔디드 큐의 줄임말로, 글자 그대로 양쪽 끝을 모두 추출할 수 있는, 큐를 일반화한 형태의 추상 자료형(ADT)이다.
• 스택과 큐의 특징 모두 가지고 있으며 이중 연결 리스트로 구현하는 편이 가장 잘 어울린다.
• 이중 연결 리스트로 구성시 양쪽으로 head, tail 포인터를 갖고 있다가 아이템이 추가될 때마다 앞쪽 또는 뒤쪽으로 연결시켜 준다.
• 파이썬의 경우, 데크 자료형을 collections 모듈에서 deque라는 이름으로 지원한다.

import collections
a = collections.deque()
type(a)
# <class 'collections.deque'>
# collection.deque도 이중 연결 리스트로 구현되어 있다

 

우선순위 큐

 

• 큐 또는 스택과 유사하지만 추가로 각 요소의 우선순위와 연관되어 있다.
• 어떠한 특정 조건에 따라 우선순위가 가장 높은 요소가 추출되는 자료형이다.
• 다익스트라 알고리즘, 힙 자료구조에 사용된다.

 

Priority Queue vs heapq

파이썬에서 우선순위 큐는 queue 모듈의 PriorityQueue 클래스를 이용해 사용할 수 있다. 하지만 우선순위 큐는 힙을 사용해 주로 구현하며 파이썬의 PriorityQueue조차 내부적으로는 heapq를 사용하도록 구현되어 있다.

#cpython/Lib/queue.py
class PriorityQueue(Queue):
  ...
  def _put(self, item):
    heappush(self.queue, item)
  def _get(self):
    return heappop(self.queue)

 

이 코드에서 보듯 PriorityQueue의_put(), _get()은 heapq 모듈의 heappop(), heappush() 그대로 이용하므로 동일하지만 차이점이 존재한다.

PriorityQueue의 경우 스레드 세이프가 있지만 heapq모듈의 경우 스레드 세이프가 보장되지 않는다.

 

💡 스레드 세이프란?(Thread Safe)

멀티 스레드 프로그래밍에서 일반적으로 어떤 삼후나 변수, 혹은 객체가 여러 스레드로부터 동시에 접근이 이루어져도 프로그램 실행에 문제없음을 뜻하는 것