📖 Queue 2

📌 원형 큐

✅ 선형 큐의 문제점

• 기존 선형 큐의 문제점
  • 앞 메모리 낭비
    -> deQueue때 앞으로 하나씩 땡기면 O(1)에서 O(N)이 되버림

✅ 원형 큐의 구조

• 초기 공백 상태
  • front = rear = 0front = rear = 0
• Index의 순환
  • front와 rear의 위치가 배열의 마지막 인덱스인 n-1을 가리킨 후, 그 다음에는 논리적 순환을 이루어 배열의 처음 인덱스인 0으로 이동해야 함
  • 이를 위해 연산자 mod 사용
• front 변수
  • 공백 상태와 포화 상태 구분을 쉽게 하기 위해 front 자리는 사용하지 않고 항상 빈 자리로 둔다.
• 삽입 위치 및 삭제 위치

구분	삽입 위치	삭제 위치
선형큐	rear=rear+1	front=front+1
원형큐	rear=(rear+1) mod n	front=(front+1) mod n

✅ 원형 큐의 연산 과정

1. createQueue()

2. enQueue(A)

3. enQueue(B)

4. deQueue()

5. enQueue

6. enQueue(D)

📌 우선순위 큐 (Priority Queue)

✅ 우선순위 큐

• 우선순위 큐의 특성
  • 우선순위를 가진 항목들을 저장하는 큐
  • FIFO 순서가 아니라 우선순위가 높은 순서대로 먼저 나가게 됨.
• 우선순위 큐의 적용 분야
  • 시뮬레이션 시스템
  • 네트워크 트래픽 제어
  • 운영체제의 테스크 스케줄링

✅ 우선순위 큐의 구현

• 배열을 이용한 우선순위 큐

• 리스트를 이용한 우선순위 큐

✅ 우선순위 큐의 기본 연산

• 삽입 : enQueue

• 삭제 : deQueue

✅ 배열을 이용한 우선순위 큐 구현

• 배열을 이용하여 자료 저장

• 원소를 삽입하는 과정에서 우선순위를 비교하여 적절한 위치에 삽입하는 구조

• 가장 앞에 최고 우선순위의 원소가 위치하게 됨

• 문제점
  • 배열을 사용하므로, 삽입이나 삭제 연산이 일어날 때 원소의 재배치 발생
  • 이에 소요되는 시간이나 메모리 낭비 큼