Queue

이번엔 Queue를 정리해보자.

Queue는 위 아래 모두 구멍이 있는 박스라고 생각을 하면 된다.

그림을 보면 데이터는 위에서만 넣을 수 있고 빠지는 건 아래에서부터 빠진다.

이런 구조라면 먼저 들어간 데이터가 먼저 나오는 구조가 된다.

Queue는 FIFO(First In First Out) 구조이다.

 

코드적으로 생각해보기

Queue가 가지고 있는 보통의 대표적인 메서드는 다음과 같은 것들이 있다.

• enqueue(item): 데이터 추가하기
• dequeue(): 가장 오래된 데이터 빼기
• peek(): 가장 오래된 데이터 보기
• isEmpty(): Queue가 비었는지 확인하기

 

비어있는 사이즈가 7인 큐가 있다.

 

1. 이 상태에서 데이터 1을 넣으면 다음 모양이 된다.

 

2. 그리고 데이터 2를 또 추가적으로 넣는다면 이런 모양이 된다.

 

이 상태에서 peek() 메서드를 호출하면 결과는 1이다.

가장 먼저 넣은 데이터가 가장 오래된 데이터.

이 상태에서 isEmpty() 메서드를 호출하면  결과는 false다.

 

3. 데이터를 빼보자. 가장 먼저 들어간 1이 나온다.

4. 또 빼보자. 그 다음으로 들어간 2가 나온다.

 

 

이런 구조가 큐이고 가장 먼저 들어간 녀석을 빼는 작업과, 비었는지 안 비었는지를 확인할 수 있으려면 큐 구조는 시작과 끝을 알고 있어야 한다.

 

struct Queue

#define MAX_SIZE = 100

struct queue {
	int data[100];
    int front, rear;
}

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

void enqueue(struct queue *q, int value) {
	if (q->rear == 100) {
    	printf("Queue is full.\n");
        return;
    }
    q->data[q->rear++] = value;
}

int dequeue(struct queue *q) {
	if (q->front == q->rear) {
    	print("Queue is empty\n");
        return -1;
    }
    return q->data[q->front++];
}

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

int peek(struct queue *q) {
	if (q->front == q->rear) {
    	printf("Queue is empty\n");
        return -1;
    }
    return q->data[q->front];
}

 

 

Queue test

int main() {
    struct queue q;
    init_queue(&q);
	...
}

이 코드를 수행하면 다음과 같은 그림이 된다.

int main() {
    struct queue q;
    init_queue(&q);
    enqueue(&q, 1);
    ...
}

이 코드를 수행하면 큐에 1을 넣는다. 그러면 가장 오래된 데이터를 가르키는 위치와 다음에 넣을 수 있는 위치에 대한 정보가 변한다.

다음 그림처럼.

int main() {
    struct queue q;
    init_queue(&q);
    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);
    ...
}

이렇게까지 코드가 수행되면 다음 그림이 된다.

int main() {
    struct queue q;
    init_queue(&q);
    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);
    int value = dequeue(&q);
    ...
}

이제 dequeue() 메서드를 호출한다. 가장 오래된 데이터(1)가 나오게 된다. 그리고 가장 오래된 데이터를 큐에서 뺐으니 가장 오래된 데이터를 가르키는 포인터는 변경된다.

만약 이 상태에서 peek() 메서드를 호출하면 나오는 값은 2가 된다. 현재 front가 가르키는 값이 2니까.

만약 이 상태에서 is_empty() 메서드를 호출하면 결과는 false다.

 

이런것을 큐라고 한다.

 

 

큐에서 발생할 수 있는 문제점

다음 그림을 보자.

이렇게 사이즈가 7인 큐에 값을 계속 넣었고 마지막 자리까지 넣었다. 그럼 꽉 찬 상태라 더 넣을 수 없다. 

이 모양일 때 dequeue()를 2번 수행했다고 해보자.

이런 그림이 될 것이다. 그럼 큐는 이제 꽉 차지 않았다. 이때 큐에 넣을 수 있을까? rear가 마지막 자리라 넣을 수가 없다. 

이런 문제를 어떻게 해결할까? Circular Queue.

 

Circular Queue는 이 문제를 어떻게 해결할까? rear 포인터가 밖으로 벗어나면 맨 앞으로 다시 가져오는 방법이다.

 

이런 그림이 될 수 있도록.

그렇게 또 다시 채울 수 있게 되고 두번을 더 채우다 보면 다음 그림이 된다.

이렇게 다시 front, rear 포인터가 같은 자리를 가르키면 꽉 찼다는 걸 알 수 있게 된다.

rear, front를 다시 회전시키는 방법은 간단하다.

rear = (rear + 1) % queue_size
front = (front + 1) % queue_size

rear 포인터가 6이 되어서 더 채울 수 없는 공간까지 오면 rear + 1은 7이 된다.

그걸 큐의 사이즈(7)로 나눈 나머지는 0이니까 다시 0을 가리키게 된다.

front 포인터도 같은 방식.

 

Queue 활용

그래서 큐는 대표적으로 Graph / Tree에서 BFS할 때 사용한다.