[자료구조] Queue vs priority queue

 

 

오늘은 Queue와 priority queue를 알아보겠습니다. 

 

큐(Queue)

 

큐는말 그대로 줄을 서는 것과 같습니다. 예를 들어, 은행에 가서 번호표를 뽑고, 번호 순서대로 창구에서 업무를 보는 것을 생각해보세요. 먼저 온 사람이 먼저 업무를 보는 '선입선출(FIFO: First-In-First-Out)' 원칙을 따릅니다. 이렇게 줄을 선 순서대로 처리하는 구조가 바로 큐입니다.

 

우선순위 큐(Priority Queue)

 

우선순위 큐는 이름에서 알 수 있듯이, 각각의 항목이 어떤 '우선순위'를 가지고 있고, 이 우선순위에 따라 처리됩니다. 응급실을 예로 들어보겠습니다. 응급실에는 많은 환자들이 있지만, 모든 환자가 동일한 치료를 받는 것은 아닙니다. 중상을 입은 환자는 가벼운 상처를 입은 환자보다 먼저 치료를 받습니다. 이처럼 누가 먼저 왔는지가 아니라 '긴급성'이라는 우선순위에 따라 누가 먼저 처리될지가 결정되는 것이 우선순위 큐입니다.

 

---

 

컴퓨터 과학에서도 이 개념은 비슷합니다. 큐는 정해진 순서대로 데이터를 처리하지만, 우선순위 큐는 각 데이터 항목에 우선순위가 매겨져 있고, 가장 높은 우선순위를 가진 항목이 먼저 처리됩니다.