[자료구조] 큐(Queue)

큐(Queue)

큐는 스택과 같은 자료구조 중 하나로 먼저 들어간 데이터가 먼저 나오는 구조입니다.
데이터가 순서대로 처리되어야 하는 상황에서 매우 유용합니다.

주요 연산

연산	설명	자바 메서드
Enqueue	큐의 끝에 데이터를 추가합니다.	add(E e), offer(E e)
Dequeue	큐의 앞에서 데이터를 제거하고 반환합니다.	remove(), poll()
Peek/Front	큐의 앞에 있는 데이터를 제거하지 않고 반환합니다.	element(), peek()
IsEmpty	큐가 비어 있는지 확인합니다.	isEmpty()
Size	큐에 있는 데이터의 수를 반환합니다.	size()

특성

• FIFO(First In, First Out): 먼저 들어간 데이터가 먼저 나오는 구조입니다. 예를 들어, 줄을 서서 기다리는 사람들을 생각해보면, 먼저 줄을 선 사람이 먼저 줄을 나가는 것과 같습니다.

큐 사용 사례

• 프린터 작업 관리: 여러 사용자가 프린터에 인쇄 작업을 보낼 때, 작업은 큐에 저장됩니다. 큐는 각 작업이 도착한 순서대로 처리되도록 보장합니다.
• 프로세스 스케줄링: 운영 체제는 여러 프로세스의 실행 순서를 관리하기 위해 큐를 사용합니다. 프로세스는 준비 큐에 들어가고, 스케줄러는 큐에서 프로세스를 꺼내서 CPU에 할당합니다.
• 탐색 알고리즘: 너비 우선 탐색(BFS) 알고리즘은 큐를 사용하여 그래프나 트리의 노드를 레벨 순서대로 탐색합니다.

큐의 종류

1. 일반 큐 (Simple Queue): 기본적인 FIFO 구조를 따릅니다.
2. 원형 큐 (Circular Queue): 일반 큐에서 마지막 위치가 처음 위치와 연결된 형태로, 배열의 처음과 끝을 연결하여 원형으로 만든 구조입니다.
3. 우선순위 큐 (Priority Queue): 데이터가 들어온 순서가 아닌 우선순위에 따라 처리되는 큐입니다.
4. 이중 큐 (Deque, Double-Ended Queue): 앞과 뒤 양쪽에서 데이터를 삽입하고 제거할 수 있는 큐입니다.