[자료구조] 큐

큐의 개념

큐의 의미

• 추상자료형

→ 택시를 타기 위해 서 있는 행렬

→ 병원 접수대

→ 예금 인출기

→ 작업 큐에 들어간 작업이 가장 처음에 처리되는 작업 스케쥴 (First - In - First - Service)

• 한쪽에서는 삽입연산만 발생 , 다른쪽에서는 삭제 연산만 발생 가능한 구조
• 삽입연산 → 서비스를 받기 위한 기다림
• 삭제연산 → 서비스를 받는 중
• 선입 선출 ( First - In - First - Out, FIFO) 알고리즘이 사용 됨

큐의 정의

삽입 구조

D 입력 시 rear 포인터가 한칸 이동

삭제 구조

front 값 삭제

포인터 활용

• front : 삭제
• rear : 삽입

큐의 추상 자료형

큐의 객체 정의

큐 객체 → 0개 이상의 원소를 갖는 유한 순서 리스트

큐의 삽입(Add_q) 연산

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

큐의 삭제(Delete_q) 연산

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}

큐의 응용

CPU의 관리 방법

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

준비큐 (Ready Queue)

[ a , b , c] → [cpu] → 완료

→ 비효율적이라고 느껴 rr 방식 이 나타남

• RR(Round Robit) 스케줄링 기법은 대화형 시스템에 적합하며, 일정 시간time slice)만 CPU를 사용하는 스케줄링 방식
• 일정 시간이 지나도 안끝날 시 맨 뒤로 이동

준비큐 (Ready Queue) → ex) 10분씩만 사용

[ a , b , c , a ] → [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 if full');
				return;
	}
	queue[++rear] = item;
	return;
}

큐의 삭제 연산

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

element Delete_q() {
	if(front == rear) {
		printf('Queue is empty');
		return;
	}
	return(queuep[++(front)]);
}

원형 큐

원형 큐의 초기 상태

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

원형 큐의 삽입 연산 결과

• 연결된 부분의 데이터 공간을 연속적으로 사용하기 위해 ‘나머지 연산자’ 을 활용함

큐의 개념

큐의 의미

• 추상자료형

→ 택시를 타기 위해 서 있는 행렬

→ 병원 접수대

→ 예금 인출기

→ 작업 큐에 들어간 작업이 가장 처음에 처리되는 작업 스케쥴 (First - In - First - Service)

• 한쪽에서는 삽입연산만 발생 , 다른쪽에서는 삭제 연산만 발생 가능한 구조
• 삽입연산 → 서비스를 받기 위한 기다림
• 삭제연산 → 서비스를 받는 중
• 선입 선출 ( First - In - First - Out, FIFO) 알고리즘이 사용 됨

큐의 정의

삽입 구조

자료구조 강의 내용 속 그림

D 입력 시 rear 포인터가 한칸 이동

삭제 구조

자료구조 강의 내용 속 그림

front 값 삭제

포인터 활용

• front : 삭제
• rear : 삽입

큐의 추상 자료형

큐의 객체 정의

큐 객체 → 0개 이상의 원소를 갖는 유한 순서 리스트

큐의 삽입(Add_q) 연산

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

큐의 삭제(Delete_q) 연산

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}

큐의 응용

CPU의 관리 방법

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

준비큐 (Ready Queue)

[ a , b , c] → [cpu] → 완료

→ 비효율적이라고 느껴 rr 방식 이 나타남

• RR(Round Robit) 스케줄링 기법은 대화형 시스템에 적합하며, 일정 시간time slice)만 CPU를 사용하는 스케줄링 방식
• 일정 시간이 지나도 안끝날 시 맨 뒤로 이동

준비큐 (Ready Queue) → ex) 10분씩만 사용

[ a , b , c , a ] → [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 if full');
				return;
	}
	queue[++rear] = item;
	return;
}

큐의 삭제 연산

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

element Delete_q() {
	if(front == rear) {
		printf('Queue is empty');
		return;
	}
	return(queuep[++(front)]);
}

원형 큐

원형 큐의 초기 상태

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

원형 큐의 삽입 연산 결과

• 연결된 부분의 데이터 공간을 연속적으로 사용하기 위해 ‘나머지 연산자’ 을 활용함