3.6 큐
큐(queue)는 선입 선출(FIFO, First-In-First-Out) 형태의 자료 구조로, 먼저 추가한 원소가 먼저 제거됩니다.
▲ 그림 3-4 큐
큐는 다음과 같이 다양한 용도로 사용합니다.
1. 공유 자원 접근(예: 프린터)
2. 멀티 프로그래밍
3. 메시지 큐
4. 그래프와 트리의 너비 우선 탐색(BFS, Breadth First Search)
큐의 API는 다음과 같습니다.
• Add(k) 큐의 맨 뒤쪽에 새 원소 k를 추가합니다.
• Remove() 큐의 맨 앞에 있는 원소의 값을 반환하고 이 원소를 삭제합니다.
• Front() 큐의 맨 앞에 있는 원소의 값을 반환합니다.
• Size() 큐의 원소 개수를 반환합니다.
• IsEmpty() 큐가 비었으면 1을 반환하고 그렇지 않다면 0을 반환합니다.
큐의 모든 연산은 시간 복잡도가 O(1)입니다.