[Data Structure] 큐 (Queue)

✔ 큐

큐(Queue)란?

• 배열에서 발전된 형태의 선형 자료구조
• 삽입과 삭제 연산이 선입선출로 이루어지는 자료구조

큐의 특징

1. 먼저 들어간 원소(First In First Out, FIFO)가 먼저 나옴
   또는 나중에 들어간 원소(Last In Last Out, LILO)가 나중에 나옴
   • 새 값 추가는 큐의 rear에서 이루어지고, 삭제는 큐의 front에서 이루어짐
   • O(N)의 시간 복잡도와 공간 복잡도를 가짐
2. 삽입과 삭제가 양방향에서 이루어짐
3. 큐는 빈 메모리가 남아 있어도, rear가 끝에 도달할 경우 꽉 차있는 것으로 판단할 수 있으므로
   이를 개선하기 위해 처음과 끝이 연결되어 있도록 간주하는 원형 큐, 연결리스트 큐가 존재

큐 용어

• rear : 큐의 가장 끝 데이터를 가리키는 영역
• front : 큐에서 가장 앞의 데이터를 가리키는 영역
• add : rear 부분에 새로운 데이터를 삽입하는 연산
• poll :  front 부분에 있는 데이터를 삭제하고 확인하는 연산
• peek : 큐의 맨 앞인 front에 있는 데이터를 확인하는 연산
• isEmpty : 큐가 비어있는지 확인하는 연산

큐는 언제 사용할까?

• 너비 우선 탐색에서 자주 사용
• 버퍼, 마구 입력된 것을 처리하지 못하는 상황, 캐시 등에서도 사용

우선순위 큐(Priority Queue)란?

• 값이 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조
• 큐 설정에 따라 front에는 항상 최댓값 또는 최솟값이 위치함
• 하지만 front 외에는 정렬이 되어 있지 않으므로 주의