4. 큐

주요용어

1. 큐 : 한쪽에서는 삽입이 발생하고 다른 한쪽에서는 삭제가 발생하도록 정의되었으며, 먼저 삽입된 원소가 먼저 삭제되므로 선입 선출(First-In-First-Out: FIFO) 또는 선착순 서브(First-Come-First-Serve: FCFS) 알고리즘을 갖는 순서 리스트
2. 큐의 앞(front) : 원소의 삭제연산이 이루어지는 곳
3. 큐의 뒤(rear) : 원소의 삽입연산이 이루어지는 곳
4. FCFS(First-Come First-Served) 스케줄링(또는 FIFO 스케줄링) : 작업(프로그램)이 준비 큐에 도착한 순서대로 CPU를 할당받도록 해 주는 기법
5. RR(Round Robin) 스케줄링 기법 : 작업이 도착한 순서대로 CPU가 할당되지만, CPU의 시간 할당량 또는 시간 간격에 의해 제한을 받으며, 일정한 크기의 시간 할당량을 모든 작업에게 주고 그 시간동안 작업이 완료되지 못하면 준비 큐의 맨 뒤에 다시 배치되는 기법
6. 원형 큐 : 파이프의 입구와 출구 부분을 연결시킨 형태이며, 큐의 양 끝을 연결시켜서 원으로 만든 형태의 큐

---

큐의 의미

• 한쪽에서는 삽입연산만 발생 가능하고, 다른 한쪽에서는 삭제연산만 발생 가능한 양쪽이 모두 터진 관
• 한쪽에서는 삽입연산: 서비스를 받기 위한 기다림
• 다른 한쪽에서는 삭제연산: 서비스를 받는 중

큐의 삽입연산

• 삽입 연산이 발생하면 rear 변수만 오른쪽으로 이동하고, 삭제 연산이 발생하면 front 변수만 오른쪽으로 이동함

원형큐의 초기 상태

• 배열의 메모리가 낭비되는 문제점을 해결하기 위해 원형큐가 제안됨
• 원형 큐는 파이프의 입구와 출구 부분을 연결시킨 형태

---

정리하기

1. 큐는 한쪽에서는 삽입이 발생하고 다른 한쪽에서는 삭제가 발생하도록 정의되었으며, 먼저 삽입된 원소가 먼저 삭제되므로 선입 선출(First-In-First-Out : FIFO) 또는 선착순 서브(First-Come-First-Serve : FCFS) 알고리즘을 갖는 순서 리스트라고 합니다.
2. 큐에서는 원소의 삭제연산이 이루어지는 곳을 앞(front)이라 하고 삽입연산이 이루어지는 곳을 뒤(rear)라고 합니다.
3. 큐 생성 함수(Create_q(maxQueueSize))를 호출하기만 하면 프로그래머가 지정한 크기의 새로운 큐를 생성할 수 있습니다. Create_q(maxQueueSize) 함수의 매개변수인 maxQueueSize는 큐가 저장할 수 있는 최대 개수의 원소(element)를 의미합니다.
4. Boolean IsFull_q(queue, maxQueueSize) 연산은 큐가 가득 찼는지를 확인합니다. 즉, 큐에 저장된 원소(element)의 개수가 maxQueueSize와 같다면, 그 큐는 가득 찼으며 큐에 자료(원소)를 더 이상 저장시킬 수 없다는 것을 의미합니다.
5. Queue Add_q(queue, item) 연산은 큐에 새로운 원소를 삽입합니다. 만일 큐가 가득 찼다(Full)면 더 이상의 원소를 큐에 삽입할 수 없으며, ‘queueFull‘ 메시지를 출력합니다.
6. Boolean IsEmpty(queue) 연산은 큐 상태가 빈 상태인지를 확인합니다. 만일 큐가 빈 상태이면 ‘TRUE’ 값을 반환하고, 큐에 하나이상의 원소라도 있다면 ‘FALSE’ 값을 반환합니다.
7. Element Delete_q(queue) 연산자는 큐가 빈 상태라면 삭제할 원소가 없으므로 ‘queueEmpty‘를 출력합니다. 하지만, 빈 상태가 아니라면 삭제할 원소가 있으므로, 큐의 front가 가리키는 원소를 삭제하고 그 원소를 반환합니다.
8. 큐의 추상자료형에서 정의된 연산은 시스템 개발자에 따라 다르게 정의되고 구현될 수도 있고, 컴파일러 설계자에 따라 프로그래밍 언어에서 다르게 제공될 수도 있습니다.
9. 원형큐는 파이프의 입구와 출구 부분을 연결시킨 형태입니다. 연결된 부분의 데이터 공간을 연속적으로 사용하기 위해 ‘나머지 연산자‘를 사용합니다.