큐(Queue)
큐(Queue)는 먼저 추가된 데이터가 먼저 출력 처리되는 선입선출(FIFO, First In First Out) 자료 구조로서 입력된 순서대로 처리해야 하는 상황에 이용된다. Queue는 맨 위에(tail)에 데이터를 계속 추가하고, 맨 앞(head)에서만 데이터를 읽는다.
- enQueue(인큐) : Queue의 rear(저장된 원소 중에서 마지막 원소)에서 이루어지는 삽입 연산
- deQueue(디큐) : Queue의 front(저장된 원소 중에서 첫 번째 원소)에서 이루어지는 삭제 연산
원소가 하나도 없는 공백 큐의 경우에는 front와 rear의 위치가 같은 상태가 된다.
cf. 덱(Deque : Double-ended queue)
큐 두 개를 붙여서 만든 자료구조로 큐의 양쪽 끝에서 삽입 연산과 삭제 연산을 수행할 수 있는 확장된 큐로서, 스택의 특성과 큐의 특성을 모두 가지고 있는 자료구조이다. 이중 연결 리스트로 구현이 가능하다.
cf. 큐의 응용
- 프린터 버퍼 큐(Print Buffer Queue) : CPU는 출력으로 내보내는 데이터를 프린터 버퍼 큐에 삽입하고 프린터가 버퍼 큐에 있는 작업을 순서대로 처리하면서 처리가 끝난 작업은 버퍼 큐에서 삭제한다. 이와 같이 처리 속도가 다른 처리기 사이에서 처리 속도를 맞추기 위해 큐를 사용하는데, 이를 버퍼 큐라고 한다.
- 스케줄링 큐(Scheduling Queue) : 컴퓨터 운영체제에서 CPU를 사용할 프로세스들에 대해 CPU 사용 스케줄을 관리하기 위해 사용한다. 준비 큐와 대기 큐로 구성되어 있으며 CPU를 사용할 프로세스들을 준비 큐에 삽입하면 순서대로 준비 큐에서 꺼내서 CPU를 사용하게 한다. CPU를 사용하던 프로세스가 다른 처리를 기다리는 대기 상태가 되면 대기 큐에 삽입하여 대기 상태의 프로세스들을 순서대로 관리한다.
- 큐잉 이론(Queueing Theory) : 서비스를 받기 위해 기다리는 대기 행렬과 대기 시간을 실험하는데 큐가 사용된다. 모든 서비스가 끝나서 대기 행렬 큐가 공백이 될 때까지의 평균 대기 시간을 여러 상황에 대해 시뮬레이션해서 최적의 시스템을 설계한다.
Queue 클래스
.NET에는 큐를 구현한 Queue클래스와 이의 Generic 형태인 Queue<T> 클래스가 있다. 이 Queue클래스는 내부적으로 순환 배열 (Circular Array)로 구현되어 있는데, 배열의 마지막 요소에 다다른 경우 다시 배열 처음 요소로 순환하는 구조(next % arrsize)를 가지고 있다. Queue는 내부적으로 head와 tail 포인터를 가지고 있는데, tail에 데이터를 추가하고(Enqueue) head에서 데이터를 읽고 제거(Dequeue)한다. 만약 데이터 양이 많아 순환 배열이 모두 찰 경우, Queue는 Capacity를 2배로 (디폴트 Growth Factor가 2이다) 증가시키고, 모든 배열 요소를 새 순환 배열에 자동으로 복사하여 큐를 확장한다.
Queue<int> q = new Queue<int>();
q.Enqueue(120);
q.Enqueue(130);
q.Enqueue(150);
int next = q.Dequeue(); // 120
next = q.Dequeue(); // 130