[자료구조] Queue 개념

큐(Queue)란?

• 들어온 순서대로 출력되는 First In First Out으로 FIFO(피포) 구조라고 하며 선입선출 형태의 선형 자료 구조
• 입력과 출력이 동일한 스택과 달리 데이터가 입력되는 입구와 데이터가 출력되는 출구 총 2개의 입출구를 가짐

---

큐의 특징

• 선입 선출의 자료 구조
• 기본 연산
  • enqueue : 큐의 끝에 요소 추가
  • dequeue : 큐의 맨 앞의 요소를 제거하고 반환
  • peek : 큐의 맨 앞 요소를 확인하되 제거는 하지 않음
• 큐의 front와 rear
  • front : 큐의 가장 앞에 있는 데이터 위치
  • rear : 큐의 가장 마지막 위치

---

큐 사용 시 주의 사항

• 오버플로우(Overflow) : 고정된 크기의 큐를 사용할 경우 큐가 가득 찬 상태에 데이터 추가 시 발생
• 언더플로우(Underflow) : 비어 있는 큐에서 요소를 꺼내려 할 경우 데이터 출력 시 발생
• 메모리 누수 : 큐에서 요소를 제거하지 않고 계속 추가할 경우 메모리 누수가 발생할 수 있음
• 동기화 문제
  • 멀티스레드 환경에서 동기화가 필요할 수  있음
  • Java에서는 ConcurrentLinkedQueue 등 스레드에 안전한 큐 구현체 사용을 권장

---

큐(Queue)의 종류

선형 큐(Linear Queue)

• 가장 기본적인 큐의 형태
• 선형 큐는 배열, 연결 리스트로 표현 가능
• 큐에서 deQueue() 함수를 사용할 경우 맨 앞에 있는 값(front)이 반환되며 제거 되는데, 이 때 front += 1이 되어 한칸씩 밀려나게 되어 큐의 가용범위가 줄어들고, 큐의 재사용 또한 불가능하게 된다는 문제점 존재
  • 이 방식을 해결하기 위해 deQqueue를 하였을 때 front 값은 고정 시키고 뒤에 있는 데이터들의 index를 한 칸씩 당기는 방법밖에 없음
• 이를 보완하기 위해 원형 큐가 등장

원형 큐(Circle Queue)

• 기존의 큐는 직선 형태로 구현되었지만, 원형 큐는 이름 그대로 원형으로 연결된 구조를 가짐
• 원형 큐는 1차원 배열 형태로 큐를 원형으로 구성하여 배열의 처음과 끝을 연결
• 삽입/삭제 연산에서 변경되는 front와 rear 값이 가리키는 위치가 마지막 index에서 다시 처음 index로 돌아오게 되는 경우를 위해 나머지 연산자((front + 1) % maxSize)를 사용

우선 순위 큐(Priority Queue)

• 우선 순위 큐는 일반적인 큐의 구조(FIFO)와 다르게 들어간 순서와 관계없이 우선 순위가 높은 데이터가 먼저 나오는 자료구조를 의미
• 우선 순위 큐는 일반적으로 힙(Heap)을 이용하여 구현

---

큐의 활용 예시

• 작업 대기열이나 요청 처리 시스템(프린트 출력 대기, 은행/병원 대기표)
• BFS(너비 우선 탐색) 알고리즘에서 사용
• 멀티스레드 환경에서의 작업 스케줄링