1. 큐의 개념 및 추상 자료형
1.1. 큐의 의미
•
정의
◦
작업 큐에 들어간 작업이 가장 처음에 처리되는 작업 스케쥴 (FIFO: First In First Out)
•
현실의 예시
◦
택시를 타기 위해 서 있는 행렬
◦
병원의 접수대
◦
은행의 예금 인출기
•
기술적 정의
◦
한쪽에서는 삽입 연산만 발생가능하고, 다른 한쪽에서는 삭제 연산만 발생 가능한 양쪽이 모두 터진 관
▪
데이터에 접근하는 변수를 각각 달리씀 (For 삽입 연산, 삭제 연산)
◦
한쪽에서는 삽입 연산: 서비스를 받기 위해 기다림
◦
다른한쪽에서는 삭제 연산: 서비스를 받는 중
1.2. 추상 자료형
•
정의
◦
자료구조 큐에서는 Front / Rear 를 통해서만 접근 가능
◦
다른 방법으로 접근은 불가하게끔 정의된 추상자료형임
•
큐의 삽입(Add_q) 연산
Queue_Add_q(queue, item)::=
if(IsFull_q(queue))
then {'queueFull'을 출력한다;}
else {큐의 rear에서 item을 삽입하고 큐를 반환한다;}
C
복사
•
큐의 삭제(Delete_q) 연산
Element Delete_q(queue)::=
if(IsEmpty_q(queue))
then {'queueEmpty'을 출력한다;}
else {큐의 front에서 원소를 반환한다;}
C
복사
•
빈큐 검사(IsEmpty_q) 연산
Boolean IsEmpty_q(queue)::=
if(rear == front)
then {'TRUE'값을 출력한다;}
else {'FALSE'값을 반환한다;}
C
복사
•
큐의 만원 검사(IsFull_q) 연산
Boolean IsFull_q(queue, maxQueueSize)::=
if((queue의 elements의 개수) == maxQueueSize)
then {'TRUE'값을 출력한다;}
else {'FALSE'값을 반환한다;}
C
복사
•
Add/Delete 연산의 실행
◦
5번에 사실 A가 존재 & 6번에 사실 A,B 존재
◦
그러나 접근불가능하며, front / rear로만 접근가능하게 한 추상자료형
2. 큐의 응용
2.1. CPU의 관리 방법
•
FCFS(First-Come First Served)
◦
스케쥴링(또는 FIFO 스케쥴링) 기법은 작업(프로그램)이 준비 큐에 도착한 순서대로 CPU를 할당받도록 해주는 기법
•
RR(Round Robin)
◦
대화형 시스템에 사용되는 스케쥴링 방식
▪
CPU 사용시간 제한
▪
큐의 작업 시간이 CPU 사용시간 제한을 초과하면 큐 뒤로 다시감
3. 배열을 이용한 큐의 구현
3.1. 큐의 생성
•
변수 rear의 초기값은 큐의 공백 상태를 나타내는 -1 로 시작함
#define QUEUE_SIZE 5
typedef int element;
element queue(QUEUE_SIZE];
int front = -1;
int rear = -1;
C
복사
3.2. 큐의 삽입 연산
•
삽입 연산이 발생하면 rear 변수만 오른쪽으로 이동
void Add_q(int *rear, element item) {
if(*rear == QUEUE_SIZE-1) {
printf("queue size is full");
return;
}
queue(++(*rear)] = item; //rear값에 +을하고 item을 넣음
return;
};
C
복사
3.3. 큐의 삭제 연산
•
삭제 연산이 발생하면 front 변수만 오른쪽으로 이동함
•
삭제 연산의 수행 결과로 삭제된 원소를 Delete_q 연산자의 호출 프로그램에게 반환해 줌
element Delete_q(int *front, int rear){
if(*front == rear){
printf("queue size is empty");
return;
}
// front 값을 증가시키고 값을 반환함
return (queue[++(*front)]);
}
C
복사
4. 원형 큐
•
정의
◦
파이프의 입구와 출구 부분을 연결시킨 형태이며, 큐의 양 끝을 연결시켜서 원으로 만든 형태의 큐
◦
메모리를 더 효율적으로 사용하고자 원형 큐 사용
•
원형 큐의 초기 상태
◦
큐의 만원상태를 해결하기 위해 원형 큐를 사용
•
원형 큐의 만원 검사
◦
배열 큐에서는 rear == queue 인경우 큐가 비어있다고 판단할 수 있었음
◦
그러나, 원형큐에서는 rear == queue 일 경우 큐가 비었을 수도 있고 가득 찰 수 도 있음. 따라서 확인할 추가 방법이 필요함