[자료구조] 큐

큐

큐의 개념

• 한쪽에서는 삽입연산만 발생 가능하고, 다른 한쪽에서는 삭제연산만 발생 가능한 양쪽이 모두 터진 관
• 한쪽에서는 삽입연산: 서비스를 받기 위한 기다림
• 다른 한쪽에서는 삭제연산: 서비스를 받는 중
• 선입 선출(First-In-First_out, FIFO) 또는 선착 순 서브(First-Come-First-Serve, FCFS) 알고리즘과 함께 사용됨

큐의 추상 자료형

• 큐 객체: 0개 이상의 원소를 갖는 유한 순서 리스트
• 연산: queue∈Queue, item∈element, maxQueueSize∈positive integer인 모든 queue, item, maxQueueSize에 대하여 다음과 같은 연산이 정의됩니다.
  (queue는 0개 이상의 원소를 갖는 큐, item은 큐에 삽입되는 원소, maxQueueSize는 큐의 최대 크기를 정의하는 정수)

큐의 삽입(Add_q) 연산

Queue Add_q(queue, item) ::=
    if(IsFull_q(queue))
        then {'queueFull'을 출력한다;}
        else {큐의 rear에서 item을 삽입하고, 큐를 반환한다;}

큐의 삭제(Delete) 연산

Element Delete_q(queue) ::=
    if(IsEmpty_q(queue))
        then {'queueEmpty'를 출력한다;}
        else {큐의 front에 있는 원소를 삭제하고 반환한다;}

빈 큐 검사(IsEmpty_q) 연산

Boolean IsEmpty_q(queue) ::=
    if(rear==front)
        then {'TRUE'값을 반환한다;}
        else {'FALSE'값을 반환한다;}

큐의 만원 검사(IsFull_q) 연산

Boolean IsFull_q(queue, maxQueueSize) ::=
    if(queue의 elements의 개수 == maxQueueSize)
        then {'TRUE'값을 반환한다';}
        else {'FALSE'값을 반환한다;}

Add/Delete 연산의 실행

1. Create_q(4);
2. Add_q(queue, ‘A’);
3. Add_q(queue, ‘B’);
4. Add_q(queue, ‘C’);
5. Delete_q(queue);
6. Delete_q(queue);
7. Delete_q(queue);
8. Add_q(queue, ‘D’);

큐의 응용

CPU의 관리 방법

• FCFS(First-Come First-Served) 스케줄링(FIFO 스케줄링): 작업(프로그램)이 준비 큐에 도착한 순서대로 CPU를 할당받고 작업이 완료될 때까지 CPU를 사용하는 기법

• RR(Round Robin) 스케줄링: 대화형 시스템에 적합하며, 일정 시간(time slice)만 CPU를 사용하는 스케줄링 방식

배열을 이용한 큐의 구현

• 큐의 생성: 변수 rear의 초기값은 큐의 공백 상태를 나타내는 ‘-1’로 시작함

#define QUEUE_SIZE 5
typedef int element;
element queue[QUEUE_SIZE];
	int front = -1;
	int rear = -1;

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

void Add_q(element item) {
	if(rear == QUEUE_SIZE-1) {
		printf("Queue is full!!");
		return;
	}
	queue[++rear] = item;
	return;
}

• 큐의 삭제: 삭제 연산의 수행 결과로 삭제된 원소를 Delete_q 연산자의 호출 프로그램에게 반환해 줌

element Delete_q() {
	if(front == rear) {
		printf("Queue if empty");
		return;
	}
	return(queue[++(front)]);
}

원형 큐

• 배열로 구현한 큐의 문제점을 해결하기 위해 원형 큐가 제안됨
• 원형 큐는 파이크의 입구와 출구 부분을 연결시킨 형태
• 원형 큐의 삽입 연산 결과: 연결된 부분의 데이터 공간을 연속적으로 사용하기 위해 나머지 연산자를 활용함