[C++ - TIL] 원형 큐와 우선순위 큐

📘 TIL – 2025.07.24

✅ 오늘 배운 것: 큐(Circular Queue)와 우선순위 큐(Priority Queue) 구현 및 개념 정리

---

🧩 1. 원형 큐(Circular Queue)

• 정적 배열을 이용한 고정 크기 큐를 구현함.
• FIFO (First In, First Out) 구조.
• 배열 끝까지 데이터가 채워진 뒤, 앞부분에 빈 공간이 있어도 rear가 돌아올 수 있도록 modulo 연산 사용.
• 한 칸을 항상 비워 두는 이유:
  • front == rear일 때 큐가 비어 있는지 가득 찬 것인지 구분 불가.
  • 이를 방지하려고 하나의 공간을 비움.

구현상 주의점

• empty()는 front == rear로 판단.
• peek() 시 큐가 비었을 경우 exit(1)로 종료 처리됨.
• 배열 초기화 시 container[i] = NULL; → 정수형 배열에서는 적절하지 않음. (추후 개선 필요)

---

🏗️ 2. 우선순위 큐(Priority Queue)

• 일반적인 큐와 다르게, 우선순위가 높은 요소가 먼저 나감.
• 내부적으로 힙(Heap) 구조를 사용해 구현.
  • 오늘은 최대 힙(Max Heap) 방식으로 구현.

주요 기능

• push(T data):
  • 데이터 삽입 후, 부모와 비교해 위로 올라가며 정렬 (Heapify-Up)
  • while (child > 0) 루프에서 부모보다 작을 경우 정렬 중단이 필요
    • break문을 안 쓰면 루프가 불필요하게 계속 돌 수 있음 (에러는 아니지만 비효율적)
• resize(int newSize):
  • 동적 배열이 꽉 찼을 때 배열 크기를 늘림 (2배 확장)
  • 메모리 누수를 방지하기 위해 기존 배열 삭제 후 포인터 변경
  • 초기화 시 temporary[i] = NULL; → 템플릿 타입에서는 T() 사용이 안전
• top():
  • 최댓값인 루트 노드를 반환
  • 큐가 비었을 경우 exit(1)로 종료

구현상 실수 및 개선

• child = index - 1이 아닌 child = index를 써야 방금 삽입한 노드 기준으로 정렬됨.
• empty() / size() 함수에서 참조(&)를 반환할 필요 없음, const를 붙이는 게 안전하고 명확.

---

🧠 오늘의 주요 깨달음

개념요약

원형 큐의 한 칸 비움	가득 찼는지 비었는지 구분하기 위해 한 칸 남겨둠
힙 정렬에서 break의 필요성	불필요한 루프 반복을 막고 성능 및 논리 명확성 확보
NULL vs T()	템플릿에서의 안전한 초기화는 T()로 해야 함
동적 배열 크기 조절	resize 시 메모리 관리(할당 + 해제) 중요
참조 반환의 오남용 주의	단순 값 반환은 참조보단 값 복사 + const가 적절