최종 수정 : 24.12.28
큐(Queue)
1. 큐의 정의
큐는 리스트의 한쪽 끝에서 원소를 삽입하고 다른 한쪽 끝에서는 원소의 삭제가 일어나는 구조이다. 이를 선입선출(FIFO : First In First Out)이라고도 한다. 프로세서 스케줄링에서 FCFS(Fist Come Fist Service) 알고리즘과 같이 먼저 작업대기 큐에 들어오면 먼저 서비스를 받는 형식이다.
큐는 near와 front라고 하는 2개의 포인터를 사용한다.
- rear(또는 tail)
☞ rear에서 원소의 삽입 연산이 실행되며, 큐에서 원소를 삽입하기 위해서 rear 포인터를 1 증가시키고 원소를 삽입하게 된다. - front(또는 head)
☞ front에서 원소의 삭제 연산이 일어난다. front 포인터 위치에 있는 원소를 삭제하고 front 포인터를 1 증가한다. - underflow
☞ front 포인터와 rear 포인터가 같아지는 경우, 큐가 비어 있는 상태가 된다. 큐의 초기 상태는 rear = front = -1이고, rear = front가 같아지는 경우는 큐가 공백상태가 되며, 이때 삭제작업을 수행하면 underflow가 된다. - overflow
☞ 큐의 크기가 nn일 때 reat = n-1인 경우는 큐가 가득 찬 상태이므로 더 이상 원소의 삽입이 불가능한 상태가 된다.
front 포인터는 rear 포인터보다 큰 값을 가질 수 없다. 큐에서 원소 삽입은 enQueue라고 하며 rear에서 이루어지고, 원소의 삭제는 deQueue라고 하며 front에서 이루어진다.
2. 선행 큐의 문제 해결방법
선행 큐에서의 삽입과 삭제가 반복되면서 큐의 기억공간은 아직 남아 있지만 조건 감사 알고리즘에 의해 rear = n-1이 되어 큐가 포화상태로 인식되는 경우의 문제가 있다. 이를 해결하기 위한 방법은 선형 큐를 환형 큐, 연결 리스트, 무빙큐로 구현할 수 있다.
1) 무빙큐(Movig Queue)를 이용한 큐 구성
이 문제를 해결하기 위해 원소들을 배열의 앞부분으로 이동시키는 작업을 진행한다. 그러나 이 방법은 많은 작업 과정이 필요하여 효율성이 떨어진다. 선형 큐의 크기가 크면 클수록 이동 횟수는 많아지고, 잦은 삽입과 삭제가 발생할 경우, 큐의 요소를 이동하는 데 소모되는 시간이 많아진다.
2) 연결 리스트로 큐 구성
연결 리스트는 불연속적인 공간에 노드를 생성하여 링크의 조작으로 연결할 수 있으므로 큐의 삽입과 삭제에서 공간의 문제를 해결할 수 있다.
3) 환형 큐 구성
선형 큐를 환형 큐로 변형하여 운용하게 되므로 원소들의 이동이나 링크의 조작 없이 선형 큐의 잘못 인식된 포화상태를 해결할 수 있다.
3. 큐의 적용 분야들
큐의 이용은 버퍼링이나 운영체제에 의한 작업 큐의 생성이다. 운영체제가 작업에 대한 우선순위 기법을 사용하지 않으면 작업들은 시슨템에서 대기하는 순서대로 처리될 것이다. 작업들이 큐에 들어가고 나옴에 따라 큐는 상한값으로 포인터 값이 이동한다. 결국, rear 값이 n-1과 같아져서 큐가 포화상태가 되는 문제가 발생한다. 이러한 문제점을 해결하기 위해서 원형 큐, 다단계 큐, 다단계 피드백 큐를 사용한다.
1) 다단계 큐 스케줄링
커널 내의 준비 큐를 여러 개의 큐로 분리하여 큐 사이에도 우선순위를 부여하는 스케줄링 알고리즘이다. 또 각각의 큐에 대해 다른 스케줄링 알고리즘을 적용하기도 한다.
2) 큐의 적용
- 우선순위가 같은 작업 예약
- 은행이나 콜센터 고객 대기시간(대기표 카운터)
- 프로세스 관리
- 너비 우선 탐색(BFS, Breadth-First Search) 구현
- 캐시(Cache) 구현
- 철해야 할 노드의 리스트를 저장하는 용도로 큐(Queue)를 사용한다.
- 운영체제의 프로세스 스케줄링 처리
참고
독학사 교재
댓글