[멋쟁이사자처럼 유니티 TIL] 2024_12_06(금) 강의 요약 및 정리

큐 (Queue)

'선입선출' (First In First Out, FIFO) 원칙을 따르는 선형 자료구조.

이는 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조를 의미합니다.

 

큐의 주요 연산

• Enqueue: 큐의 뒤쪽(rear)에 새로운 요소를 추가합니다.
• Dequeue: 큐의 앞쪽(front)에서 요소를 제거하고 반환합니다.
• Peek/Front: 큐의 맨 앞 요소를 조회합니다 (제거하지 않음).
• IsEmpty: 큐가 비어있는지 확인합니다.
• Size: 큐에 있는 요소의 개수를 반환합니다.

 

 

Enqueue 하고 Dequeue 에서 size++, size-- 를 반드시 써야 하는 이유

큐 데이터가 있는지,없는지 확인하려면 큐 size크기로 확인하는데,

큐를 넣고 뺄 때마다 size ++, size --를 따로 써주지 않으면 언젠가 런타임 에러가 발생.

(:: 런타임 에러 : 프로그램이 실행되는 동안 발생하는 에러를 의미.

코드가 컴파일(번역)될 때는 문제가 없었지만, 실제 실행 중에 예기치 못한 상황이 발생해

프로그램이 정상적으로 작동하지 못하는 경우)

 

최소 힙(Min Heap) 구조를 사용하여 구현할 때

where T : IComparable<T>

// 제네릭 제약 조건(generic constraint)으로, T 타입이 반드시

    IComparable<T> 인터페이스를 구현해야 한다는 의미

  T 타입의 객체(정렬, 최대 최소값 찾기, 우선순위 큐 구현)들 간에 크기 비교를 해야 할 때 사용

 

private List<T> heap = new List<T>();

// 리스트를 초기화하고, 빈 리스트를 생성하여 heap 변수에 할당

 

 

public void Enqueue(T item) { heap.Add(item);

// 리스트의 마지막에 item을 추가.

 

int currentIndex = heap.Count - 1;

// 새로 추가된 항목의 인덱스(리스트의 마지막 값)을 구하기 위해 heap.Count -1 을 사용

   그 생성된 값을 currentIndex 에 할당.

 

HeapifyUp(currentIndex);

// currentIndex 위치에 있는 새 항목을 올려서 힙 속성을 만족하도록 함.

   현재, 최소 힙이기 때문에, 부모 노드가 자식 노드보다 작아야 함.

  새로 추가된 항목이 부모보다 우선순위가 높으면,

  교환하는 방식으로 위로 이동시키고, 힙 속성을 유지

 

public T Dequeue() { if (heap.Count == 0) throw new InvalidOperationException("우선순위 큐가 비어있습니다.");

- if (heap.Count == 0)

  // heap.Count 가 0. 즉, heap이 비어 있다면 하기의 코드를 실행.

-  throw new InvalidOperationException

  // " 우선순위 큐가 비어있습니다" 라는 예외을 작업자에게 알림

 

T root = heap[0];

// heap[0]은 우선순위 큐에서 루트 노드 (가장 작은 값)

  최소 힙에서는 루트가 가장 작은 값이므로,

   heap[0]을 root 변수에 저장하여, 반환할 값으로 사용

 

int lastIndex = heap.Count - 1;

// 새로 추가된 항목의 인덱스(리스트의 마지막 값)을 구하기 위해 heap.Count -1 을 사용

   그 생성된 값을 lastIndex  에 할당.

 

heap[0] = heap[lastIndex];

// lastIndex(상기의 코드에서 마지막 인덱스의 값) 힙을, heap[0] (가장 값이 작은 노드) 에 할당.

 

heap.RemoveAt(lastIndex);

// heap 리스트에서 마지막 항목을 제거

   마지막 항목이 루트 자리에 배치되었기 때문에,

   리스트의 크기가 1 줄어들며 마지막 항목이 리스트에서 제거

 

if (heap.Count > 0) 

// 만약 큐에 항목이 하나 이상 남아 있다면, 힙 속성을 유지해야 함

  남아있다면 하기의 코드를 실행

 

HeapifyDown(0);

//  현재, 최소 힙이기 때문에, 부모 노드가 자식 노드보다 작아야 함.

     부모 노드가 자식 노드보다 크다면, 서로의 위치를 교환하는

     방식으로, 부모 자식의 자리를 바꿈.

 

return root;

root에 저장된 루트 노드(가장 작은 값)를 반환

 

Heapify up

 

HeapifyDown