C언어로 복습하는 자료구조 (5) 큐

큐

FIFO(First In First Out) 형태의 자료구조

먼저 들어온 것이 먼저 나간다

스택은 삽입과 삭제가 모두 스택 top에서만 이루어지지만 큐는 삽입은 후단(rear), 삭제는 전단(front)에서 일어난다

연산에는 스택과 유사하게 초기화(init), is_empty, is_full이 있고, 요소를 삽입하는 enqueue, 삭제하는 dequeue, 삭제하지 않고 읽기만 하는 peek가 있다.

운영체제에서 cpu를 어느 프로세스가 갖고있냐... 그런거 공부할때 자주 나오는 자료구조였다 cpu를 받기 위해 waiting queue에서 기다리고 cpu를 받으면 running 상태가 되고 입출력을 기다릴 때는 큐에서 block 상태로 기다리고 뭐시기 뭐 그런거

 

큐는 크게 선형큐와 원형큐로 나누어진다.

 

1) 선형큐

큐를 1차원 배열로 구현하는 것을 가정하자

초기 상태에는 rear(삽입 관련 변수), front(삭제 관련 변수)가 모두 배열의 -1번째 인덱스를 가리키고 있다. front는 큐의 첫 번째 요소, rear은 큐의 마지막 요소를 가리킨다.

요소를 하나 삽입하면 rear의 인덱스가 1 증가하고, 증가한 rear의 인덱스 자리에 해당 요소가 삽입된다.

요소를 하나 삭제하면 front의 인덱스가 1 증가하고, 증가한 front의 인덱스 자리에 있던 요소가 삭제된다.

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

 

초기화는 rear과 front를 모두 -1로

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

 

is_full은 큐가 가득 찼는지 확인하는 함수

큐가 가득 찼다는 건 더는 삽입할 자리가 없다는 뜻이니까 rear == MAX QUEUE SIZE -1 일 때를 의미한다

is_empty는 큐가 비었는지 확인하는 함수

큐에서는 삽입할때 rear이 1 증가하고 삭제할때 front가 1 증가하므로, 요소가 없을 경우에는 rear과 front 값이 같아야 한다

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

 

큐에 요소를 삽입하는 enqueue

rear을 1 증가시키고 그 자리에 데이터를 넣는다

void enqueue(QueueType* q, int item) {
	if (is_full(q)) {
		error("큐가 포화상태");
		return;
	}
	q->data[++(q->rear)] = item;
}

 

요소를 삭제하는 dequeue

front를 1 증가시키고 그 자리에 있던 데이터를 삭제한다

int dequeue(QueueType* q) {
	if (is_empty(q)) {
		error("큐가 공백상태");
		return;
	}
	int item = q->data[++(q->front)];
	return item;
}

인큐와 디큐 모두 인덱스를 증가시킨 이후에 아이템을 삽입/삭제한다는 점이 포인트

 

추가로 큐를 프린트하는 함수까지

void print_queue(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");
}

 

선형큐는 구현이 쉽다

그치만 front와 rear값이 계속 증가만 하기 때문에 언젠가는 끝에 도달하게 된다. 또한 계속 삽입삭제를 반복하면 배열 앞부분이 비게 될 수 있어 낭비가 발생한다. 이런 문제를 해결하려면 요소들을 주기적으로 앞으로 땡겨줘야 하는데, 귀찮고복잡하고오래걸린다

 

2) 원형큐

배열을 일렬이 아닌 원형으로 생각해보자

front와 rear이 MAXQUEUESIZE에 도달하기 전까지는 계속 증가한다.

그러다가 배열 끝에 도달하면 다음 증가 값을 0으로 만들어 다시 카운트를 시작한다고 생각하면 된다

배열의 처음(0)과 끝(MAXSIZE - 1)이 연결되어 있는 원 형태라고 보면 된다

 

원형큐는 선형큐와 다르게 front와 rear의 초기값을 0으로 한다.

front는 큐의 첫 번째 요소의 하나 앞, rear은 큐의 마지막 요소를 가리킨다.

인덱스를 먼저 증가시키고 그 자리에 데이터를 넣거나 지운다는 것은 선형큐와 동일하다.

 

초기상태는 front와 rear이 모두 0

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

 

원형큐에서는 공백상태와 포화상태를 구별하기 위해 항상 한 자리를 비워둔다.

우선 선형큐와 마찬가지로 공백 상태에서는 front == rear이다.

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

 

포화상태에서는 한 자리를 제외하고는 큐가 꽉 차 있을 것이므로, rear에 1 더한 값이 MAX_QUEUE_SIZE의 배수가 되고, front는 rear보다 한 칸 앞에 있을 것이다.

예를 들어 8칸짜리 원형큐가 있다면 포화상태일 때는 rear이 7, front가 0에 있을 것이다

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

 

인큐디큐 똑같은데 끝까지 가면 0으로 돌아와야 하니까 맥스사이즈로 나눈 나머지값을 사용한다

증가시키고 -> 삽입삭제 순서

void enqueue(QueueType* q, int item) {
	if (is_full(q)) {
		error("큐가 포화상태");
		return;
	}
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->data[q->rear] = item;
}

int dequeue(QueueType* q) {
	if (is_empty(q)) {
		error("큐가 공백상태");
		return;
	}
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->data[q->front];
}

 

 

큐의 응용

1) 버퍼

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

데이터를 생산하는 생산자 프로세스, 소비하는 소비자 프로세스 사이에 큐로 구성되는 버퍼가 존재한다고 한다. 걍 cpu 스케줄링에 쓰인다는 말인듯

 

예제

큐에 난수를 입력하는 생산자 프로세스는 20% 비율로, 큐에서 수를 꺼내는 소비자 프로세스는 10% 비율로 스케줄링하는 버퍼

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

대충그러함

 

2) 덱(deque)

덱은 큐의 응용 자료구조인데 double-ended queue의 줄임말이다. 즉 큐의 rear과 front에서 모두 삽입과 삭제가 가능한 큐를 의미한다.

그러니 front에서 삽입하는 함수, rear에서 삭제하는 함수를 추가로 만들어주면 될것

다른건 다 똑같으니 저 두개만 만들자

저 두개는 기존 동작과 반대로 이루어져야 하니까 반대방향 회전을 해줘야한다. 감소를 시켜줘야하는데 음수가 되면 안 되니까 그럴 경우에는 MAXSIZE를 더해준다.

 

void add_front(QueueType*q, element item) {
	if (is_full(q)) error("큐가 포화상태");
	q->data[q->front] = item;
	q->front = (q->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}

주의해야 할 점은 front에 값을 추가할 때는 아이템을 먼저 넣고 front값을 감소시켜줘야 한다는 것이다

현재 front가 가리키고 있는 곳은 빈칸일 테니까 거기 아이템을 넣고 그다음에 front를 감소시킨다.

 

element delete_rear(QueueType* q) {
	int prev = q->rear;
	if (is_empty(q)) error("큐가 공백상태");
	q->rear = (q->rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
	return q->data[prev];
}

현재 rear이 가리키고 있는 곳에 삭제하고 싶은 아이템이 들어있을 것이므로, 현재 rear 위치의 데이터를 리턴한다.

그리고 rear은 1 줄어야 하니까 감소시켜준다.

기본 큐의 동작과 순서가 다름에 유의