[CS][Data Structure] 큐 (Queue)

Queue란?

Queue는 FIFO(First In First Out) 원칙을 따르는 데이터 저장 방식의 자료구조입니다.

데이터가 한쪽 끝에서 삽입되고 반대쪽 끝에서 삭제 및 검색이 됩니다. 이 때 삽입되는 곳을 'rear' 또는 'enqueue' 라고 하며 삭제 및 검색되는 곳을 'front' 또는 'dequeue'라고 합니다.

Queue의 기본 연산

1. add(n) : 큐의 rear에 데이터를 추가합니다.

2. poll() : 큐의 front의 데이터를 제거하고 반환합니다. 큐가 비어 있으면 null을 반환합니다.

3. remove() : poll()과 동일하지만 큐가 비어있으면 NoSuchElement 에러를 반환합니다.

4. peek() : 큐의 front의 데이터를 반환합니다.

5. isEmpty() : 큐가 비어있는지 확인합니다.

Queue의 장점

1. FIFO 원칙으로 인해 순서가 중요한 상황에서 활용하기 좋습니다.

2. 대기열, 버퍼 같은 실제 문제를 해결하는데 적용하기 쉽습니다.

3. 배열이나 연결 리스트로 구현하기에 적합합니다.

4. 데이터를 삽입하거나 삭제할 때 한쪽에서만 일어나기 때문에 O(1)의 시간복잡도를 가집니다.

5. peek()같은 데이터 조회 또한 한쪽에서만 처리되기 때문에 O(1)의 시간 복잡도를 가지지만 전체 탐색 시에는 각 원소를 한 번씩 처리해야 하기 때문에 O(n)의 시간복잡도를 가집니다.

Queue의 단점

1. 큐에서 임의의 위치에 있는 항목에 접근하기 어렵습니다.

2. 배열 기반의 구현에서 크기가 고정되어 있어 확장이 어렵습니다.

Queue의 종류

선형 큐

일반적인 큐로, 데이터가 선형적으로 저장됩니다. 배열이나 연결리스트로 구현이 가능합니다.

원형 큐

선형 큐의 한 정류로, rear와 front가 순환적으로 움직이게 됩니다.

우선순위 큐

각 데이터의 우선순위가 정해져 있고, 우선순위에 따라 삭제 및 검색이 이루어지는 큐입니다. Heap과 같은 자료구조로 구현될 수 있습니다.

덱

양쪽 끝에서 데이터의 삽입과 삭제가 가능한 큐로, 스택과 큐의 기능을 모두 가지고 있습니다.

Queue 활용

1. 버퍼링 : 네트워크 통신이나 파일 입출력에서 데이터 전송이 일시적으로 지연될 때 유지하기 위해 사용합니다.

2. 스케쥴링 : 운영체제에서 여러 프로세스나 쓰레드를 순서대로 처리할 때 사용됩니다.

3. 대기열 관리 : 프린터 대기열과 같은 선입선출 순서를 유지해야 하는 데이터 구조에서 활용됩니다.