#. 큐(Queue)
##1. 큐(Queue)란?
큐는 FIFO(First In First Out) 원칙을 따르는 자료구조이다.
즉, 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조를 가진다. 일상생활에서 줄을 서는 것을 생각하면 이해하기 쉽다.
##2. 큐(Queue)의 특징
-
데이터의 삽입과 삭제가 각각 다른 방향에서 이루어진다.
데이터는 뒤쪽(rear)에서 삽입되고, 앞쪽(front)에서 삭제된다. -
데이터의 입력 순서를 유지한다.
들어온 순서대로 데이터가 저장되며, 먼저 들어온 데이터부터 차례대로 나갑니다. -
종류로는 선형과 원형이 있다.
##3. 큐(Queue)의 장점과 단점
##3.1 장점
데이터의 삽입과 삭제가 각각 다른 방향에서 이루어지므로 구현이 간단하고, 데이터를 관리하기 쉽다.
##3.2 단점
선형 큐는 데이터를 Dequeue하면서 생기는 빈 공간을 재활용하지 못하는 단점이 있다.
이로 인해 메모리 사용이 비효율적이며, 큐가 가득 찼다는 오류 메시지를 받을 수 있음에도 불구하고 실제로는 사용되지 않는 메모리 공간이 있을 수 있다. 이러한 단점을 해결하기 위해 원형 큐(Circular Queue)가 도입되었다.
##4. 큐(Queue)의 추상자료형
##4.1 Enqueue
큐의 뒤쪽(rear)에 데이터를 추가하는 연산이다.
##4.2 Dequeue
큐의 앞쪽(front)에서 데이터를 제거하고, 그 데이터를 반환하는 연산이다.
##4.3 Front/Peek
큐의 앞쪽(front)의 데이터를 조회하는 연산이다.
##4.4 isEmpty
큐가 비어있는지 확인하는 연산이다.
##4.5 isFull
큐가 가득 차 있는지 확인하는 연산이다.
##5. 큐(Queue)의 시간복잡도
큐의 주요 연산인 Enqueue(삽입)과 Dequeue(삭제) 모두 O(1)의 시간복잡도를 가진다.
##6. 큐(Queue)의 종류
###6.1 선형 큐 (Linear Queue)
###6.2 원형 큐 (Circular Queue)
##7. 큐(Queue)의 사용
###7.1 버퍼
데이터가 임시로 저장되는 중간 메모리 영역인 버퍼 구현에 큐가 사용된다.
###7.2 너비 우선 탐색(BFS)
그래프 탐색 알고리즘인 너비 우선 탐색에서 큐가 사용된다
###7.3 캐시 구현
최근에 참조된 항목을 저장하는 캐시에서 큐가 사용된다.
###7.4 프린터의 인쇄 작업 관리 등
여러 작업을 순차적으로 실행해야 할 때 큐가 사용된다.
