[C언어로 쉽게 풀어쓴 자료구조] Chapter5. 큐 (1)

5.1 큐 추상 데이터 타입

● 큐: 뒤(rear)에서 새로운 데이터가 추가되고 앞(front)에서 데이터가 하나씩 삭제되는 구조로

먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO: First-In First-Out) 방식을 따른다.

- 스택은 삽입과 삭제가 같은 쪽에서 일어나지만 큐에서는 삽입과 삭제가 다른 쪽에서 일어난다.

- 따라서 스택에선 top이라는 변수 하나만 사용됐지만 큐에서는 front와 rear 두 변수가 사용된다.

- enque는 rear쪽에 삽입 연산을, deque는 front쪽에 삭제 연산을 수행한다.

 

- 은행에서 대기하는 사람들의 대기열, 공항에서 이륙하는 비행기들 등 많은 분야에서 큐를 사용한다.

- 컴퓨터와 주변기기 사이에서 속도 차이를 해결하여 CPU를 효율적으로 사용하기 위해 큐가 사용된다.

- 먼저 입력된 프로그램부터 큐에 쌓이며 순차적으로 실행된 후 실행이 완료되면 큐에서 삭제된다.

 

♠ 149p Quiz

01 선입선출

02 가장 먼저 들어온 'a'가 삭제된다.

 

5.2 선형큐

1차원 배열을 만들어서 큐를 정의한다.

- front는 큐의 첫 번째 요소를 가르키고 rear는 큐의 마지막 요소를 가리킨다.

- front는 첫 번째 요소가 위치한 바로 앞 인덱스를 가리키는 반면 rear는 마지막 요소가 위치한 인덱스를 가리킨다.

- front와 rear의 초기값은 -1이고 삽입과 삭제 연산이 이루어질 때마다 각각 rear와 front를 하나 증가시킨다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 5

typedef int element;
typedef struct{
	element data[MAX_QUEUE_SIZE];
	int front;
	int rear;
}QueueType;

void error(char *message){
	fprintf(stderr,"%s\n",message);
	exit(1);
}

void init_queue(QueueType *q){
	q->front=-1;
	q->rear=-1;
}

int is_empty(QueueType *q){
	if(q->front == q->rear) return 1;
	else return 0;
}

int is_full(QueueType *q){
	if(q->rear == MAX_QUEUE_SIZE-1) return 1;
	else return 0;
}

void enqueue(QueueType *q,element item){
	if(is_full(q)){
		error("큐가 가득 참");
		exit(1);
	}
	q->data[++(q->rear)] = item;
}

element dequeue(QueueType *q){
	if(is_empty(q)){
		error("큐가 빔");
		return -1;
	}
	element item = q->data[++(q->front)];
	return item;
}

void queue_print(QueueType *q){
	for(int i=0;i<MAX_QUEUE_SIZE;i++){
		if(i<=q->front || i>q->rear){
			printf("   | ");
		}
		else{
			printf("%d | ",q->data[i]);
		}
	}
	printf("\n");
}


int main(){
	QueueType q;
	init_queue(&q);
	
	enqueue(&q, 10);
	queue_print(&q);
	enqueue(&q, 20);
	queue_print(&q);
	enqueue(&q, 30);
	queue_print(&q);
	
	int item =0;
	item = dequeue(&q);
	queue_print(&q);
	item = dequeue(&q);
	queue_print(&q);
	item = dequeue(&q);
	queue_print(&q);
	
	return 0;
}

♠ 153p Quiz

01 front와 rear값이 계속 증가만 하기 때문에 언젠가는 배열의 끝에 도달하게 되고, 배열의 앞부분이 비어있더라도

사용하지 못한다. 오른쪽에 추가적인 삽입을 위한 공간을 만들기 위해선 모든 요소들을 왼쪽으로 이동시켜야하는데

많은 시간이 소요되고 프로그램이 복잡해진다.

 

 

5.3 원형큐

앞선 퀴즈에서 다룬 바와 같이 선형큐는 한계가 명확한데, 이를 보완하기 위해 선형 대신 원형을 생각할 수 있다.

실제로 배열이 원형으로 변화하는 것이 아닌, 배열의 처음과 끝이 연결되어 있다고 생각하는 것이다.

front와 rear의 값이 배열의 끝인 (MAX_QUEUE_SIZE -1)에 도달하면 다음에 증가하는 값은 0이 되도록한다.

 

- front는 첫 번째 요소가 위치한 바로 앞 인덱스를 가리키는 반면 rear는 마지막 요소가 위치한 인덱스를 가리킨다.

- 원형큐에서 front와 rear의 초기값은 -1이 아닌 0이고 삽입과 삭제 연산이 이루어질 때마다

  각각 rear와 front를 하나 증가시킨다.

- front와 rear의 값이 같으면 원형 큐는 공백 상태이다.

- 원형큐에서 하나의 자리는 항상 비워두는데, 이 한 자리빼고 나머지 인덱스에 값이 다 들어있으면 포화상태이다.

- 요소들의 개수를 저장하고 있는 추가적인 변수 count를 사용한다면 한자리를 비워두지 않아도 된다.

  *5강 연습문제에서 get_count를 구현하는 문제를 통해 다룬다. 

 

● 원형큐의 삽입, 삭제 알고리즘

front <- (front+1) % MAX_QUEUE_SIZE;
rear <- (rear+1) % MAX_QUEUE_SIZE;

위와 같이 front와 rear가 배열의 끝에 도달하면 그 다음부턴 나머지 연산자를 사용하여 0으로 돌아간다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 5

typedef int element;
typedef struct{
	element data[MAX_QUEUE_SIZE];
	int front;
	int rear;
}QueueType;

void error(char *message){
	fprintf(stderr,"%s\n",message);
	exit(1);
}

int is_empty(QueueType *q){
	if(q->front == q->rear) return 1;
	else return 0;
}


void init_queue(QueueType *q){
	q->front = q->rear = 0;
}


int is_full(QueueType *q){
	if((q->rear +1)%MAX_QUEUE_SIZE == q->front) return 1;
	else return 0;
}

void enqueue(QueueType *q,element item){
	if(is_full(q)){
		error("큐가 가득 참");
		exit(1);
	}
	q->rear = (q->rear +1) % MAX_QUEUE_SIZE;
	q->data[q->rear] = item;
}

element dequeue(QueueType *q){
	if(is_empty(q)){
		error("큐가 빔");
		return -1;
	}
	q->front = (q->front +1) % MAX_QUEUE_SIZE;
	element item = q->data[(q->front)];	
	return item;
}

void queue_print(QueueType *q){
	printf("QUEUE(front=%d rear=%d) = ", q->front,q->rear);
	if(!is_empty(q)){
		int i= q->front;
		do{
			i=(i+1)%MAX_QUEUE_SIZE;
			printf("%d | ",q->data[i]);
			if(i==q->rear) break;
		}while(i != q->front);
	}
	printf("\n");
}


int main(){
	QueueType q;
	init_queue(&q);
	element a;
	printf("---데이터 추가 단계---\n");
	while(!is_full(&q)){
		printf("정수를 입력하시오: ");
		scanf("%d",&a);
		enqueue(&q,a);
		queue_print(&q);
	}
	printf("큐가 포화상태입니다.\n");
	
	printf("\n");
	
	printf("---데이터 삭제 단계---\n");
	while(!is_empty(&q)){
		a = dequeue(&q);
		printf("꺼내진 정수: %d \n",a);
		queue_print(&q);
	}
	printf("큐는 공백상태입니다.\n");
	return 0;
}

♠ 160p Quiz

01 front는 첫 번째 요소의 바로 앞을, rear는 마지막 요소를 가르킨다.

02 front는 1 rear는 4

 

 

5.4 큐의 응용: 버퍼

큐는 서로 다른 속도로 실행되는 두 프로세스 간의 상호작용을 조화시키는 버퍼 역할을 담당한다.

-생산자-소비자 프로세스 : 큐를 버퍼로 사용한다.

-교통 관리 시스템: 컴퓨터로 제어되는 신호등에서는 신호등을 순차적으로 제어하는데 원형큐를 사용한다.

-CPU 스케쥴링: 운영체제는 실행 가능한 프로세스를 저장하거나 대기하는 프로세서를 저장하기 위해 큐를 사용한다.

 

큐를 버퍼처럼 사용하는 예시로, 큐에 20% 비율로 난수를 생성하여(5로 나누어 떨어지는 지) 큐에 입력하고,

10% 비율(10으로 나누어 떨어지는지)로 큐에서 dequeue를 실행하는 프로그램을 작성해보았다.

//위는 원형큐 예제와 동일

int main(){
	QueueType q;
	init_queue(&q);
	element a;
	srand(time(NULL));
	
	for(int i=0;i<100;i++){
		if(rand()%5 ==0){
			enqueue(&q,rand()%100);
		}
		queue_print(&q);
		if(rand()%10 ==0){
			int data = dequeue(&q);
		}
		queue_print(&q);
	}
	return 0;
}