자료구조 기본: 큐(Queue) 완벽 가이드

큐(Queue)란?

• 큐는 선입선출(First In, First Out; FIFO) 방식으로 작동하는 선형 자료구조입니다.
• 큐에서 데이터는 한쪽 끝에서 추가되고, 반대쪽 끝에서 제거됩니다.

큐의 주요 특징

• 선입선출 구조: 가장 먼저 들어온 요소가 가장 먼저 나갑니다.
• 두 개의 주요 연산:
  • Enqueue: 큐의 뒤쪽에 요소를 추가합니다.
  • Dequeue: 큐의 앞쪽에서 요소를 제거하고 반환합니다.
• 추가 연산:
  • Peek/Front: 큐의 맨 앞에 있는 요소를 반환하지만 제거하지는 않습니다.
  • IsEmpty: 큐가 비어 있는지 확인합니다.

큐의 사용 사례

• 대기열 관리: 은행, 티켓 창구, 프린터 작업 등 순차적 처리가 필요한 곳에서 사용됩니다.
• 데이터 버퍼링: 네트워크 트래픽 관리, 메시지 큐 시스템 등 데이터의 임시 저장 및 순차적 처리에 적합합니다.
• 너비 우선 탐색(BFS): 트리나 그래프의 너비 우선 탐색 알고리즘에 사용됩니다.

큐의 구현

• 큐는 배열이나 연결 리스트를 사용하여 구현할 수 있습니다.
• 배열 기반 큐: 고정된 크기를 가지며, 요소가 추가될 때 배열의 끝으로 이동합니다.
• 연결 리스트 기반 큐: 동적으로 크기가 조정되며, 새로운 요소를 추가하거나 제거하기 쉽습니다.

큐의 장단점

• 장점
  • 데이터를 순차적으로 처리하기 쉽습니다.
  • 구현이 간단하고 직관적입니다.
• 단점
  • 배열 기반의 큐는 크기가 고정되어 있어 확장성에 제한이 있습니다.
  • 연결 리스트 기반의 큐는 추가적인 메모리(포인터)가 필요합니다.

결론

• 큐는 데이터를 순차적으로 처리하는 다양한 시나리오에서 매우 유용한 자료구조입니다.
• 적절한 큐의 선택과 구현은 프로그램의 성능과 효율성에 큰 영향을 미칩니다.