[자료구조] 원형Queue란? C언어로 구현

▶Queue란?

---

Queue는 앞뒤가 뚫려있는 쇠파이프를 떠올리면 이해하기 쉽다.

 

 

우리는 쇠파이프의 뒤로 차곡차곡 데이터를 넣을것이다.

그 후 데이터를 꺼내고싶으면 그 데이터를 앞에서 꺼낼 것이다.

즉, 먼저 들어가 데이터가 가장 먼저 나오게 된다.

이것을 First In First Out(FIFO) 데이터 구조라고 부른다.

 

원형큐는 이 파이프를 동그랗게 만든것이다.

 

동그랗게 만들면 메모리를 아낄 수 있다는 장점이 있다.

 

 

 

 

 

 

▶큐의 ADT

---

https://suzzeong.tistory.com/106

• 데이터를 집어넣을 수 있는 선형(linear) 자료형
• FIFO(First In First Out) - 먼저 집어넣은 데이터가 먼저 나옴
• 데이터를 집어 넣는 enqueue, 데이터를 추출하는 dequeue 등의 작업을 할 수 있음큐는 순서대로 처리해야 하는 작업을 임시로 저장해두는 버퍼(buffer)로 많이 사용됨

 

큐의 시간 복잡도

삽입/삭제 : O(1)

검색 : O(N)

 

구현 할 함수

isFull : 큐가 꽉 찼는지 확인

isEmpty : 큐가 비었는지 확인

enQueue : 큐의 맨위에 데이터 추가

deQueue : 큐의 맨 앞 데이터 삭제 후 삭제한 데이터 반환

initQueue : 큐 초기화

printQueue : 큐 출력

 

 

 

 

▶원형큐 C언어 구현

---

#include <stdio.h>
#define Queue_SIZE 5

typedef struct {
	int items[Queue_SIZE];
	int front, rear;
}CircularQueue;

int isFull(CircularQueue* q) {
	if(q->rear+1 % Queue_SIZE == q->front) {
		return 1;
	}
	else {
		return 0;
	}
}

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

void enQueue(CircularQueue* q, int data) {
	if(isFull(q) == 1) {
		printf("Queue is Full\n");
	}
	else {
		q->rear = (q->rear + 1) % Queue_SIZE;
		q->items[q->rear] = data;
	}
}

int deQueue(CircularQueue* q) {
	if(isEmpty(q) == 1) {
		printf("Queue is Empty");
		return -1;
	}
	else {
		q->front = (q->front + 1) % Queue_SIZE;
		return q->items[q->front];
	}
	
}

void initQueue(CircularQueue* q) {
	q->front = 0;
	q->rear = 0;
	
}

void printQueue(CircularQueue* q) {
	printf("Queue : ");
	if (isEmpty(q)==1) {
		printf("The queue is empty\n");
		return;
	}
	
	int i = q->front;
	while(i != q->rear) {
		i = (i+1) % Queue_SIZE;
		printf("%d ",q->items[i]);
	}
	printf("\n");
}

int main() {
	
	CircularQueue q;
	initQueue(&q);
	
	enQueue(&q, 1);
	enQueue(&q, 2);
	enQueue(&q, 3);
	printf("Dequeue: %d\n", deQueue(&q));
	printf("Dequeue: %d\n", deQueue(&q));
	
	printQueue(&q);
	
	enQueue(&q, 4);
	enQueue(&q, 5);
	
	while(isEmpty(&q)==0) {
		printf("Dequeue: %d\n", deQueue(&q));
	}
	
	printQueue(&q);
	
	return 0;
}

위에서 부터 차근차근 살펴보자

 

#include <stdio.h>
#define Queue_SIZE 5

typedef struct {
	int items[Queue_SIZE];
	int front, rear;
}CircularQueue;

원형큐의 구조체를 typedef 해준다.

원형큐 안에는 선형배열이 존재하고,  큐의 앞과 뒤를 표시해주는 front, rear가 존재한다.

 

 

int isFull(CircularQueue* q) {
	if(q->rear+1 % Queue_SIZE == q->front) {
		return 1;
	}
	else {
		return 0;
	}
}

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

isFull과 isEmpty 함수는 큐가 꽉찼는지, 비었는지 확인해주는 함수이다.

isFull함수를 보면 % 모듈러 연산이 있는데 이걸 설명하자면

이렇게 크기가 6인 원형큐가 있다고 해보자.

지금 원형큐를 보면 꽉 차있다. front = 0이고 rear = 5이다.

위에 if(q->rear + 1 % Queue_SIZE == q->front)를 위 숫자를 대입해보면

(5+1)%6 == 0이면 포화상태인 것이다.

위 큐는 포화상태이므로 참이다!! 이해가 될런지... 

 

그리고 아래 isEmpty함수는 front와 rear의 위치가 같으면 비어있는 함수이기 때문에 저렇게 구현했다.

 

 

void enQueue(CircularQueue* q, int data) {
	if(isFull(q) == 1) {
		printf("Queue is Full\n");
	}
	else {
		q->rear = (q->rear + 1) % Queue_SIZE;
		q->items[q->rear] = data;
	}
}

enQueue 함수는 큐의 끝에 data를 삽입하는 함수이다.

우선 큐가 꽉 차있으면 데이터를 못삽입하기 때문에 확인을 해주고 

꽉 차있지 않다면 rear의 위치를 하나 늘려주기 위해서 (q->rear + 1) % Queue_SIZE를 rear의 위치로 바꿔준다.

위 식은 무조건 원형큐에 rear의 위치에서 다음 인덱스로 가게 해주는 식이다.

 

다시 돌아와서 rear의 위치를 다음 인덱스로 바꾼 다음에 rear의 위치에 data를 삽인하는 함수이다.

 

 

int deQueue(CircularQueue* q) {
	if(isEmpty(q) == 1) {
		printf("Queue is Empty");
		return -1;
	}
	else {
		q->front = (q->front + 1) % Queue_SIZE;
		return q->items[q->front];
	}
	
}

deQueue 함수는 front의 위치를 다음 인덱스로 바꿔서 data를 삭제해주고 삭제 된 데이터를 반환하는 함수이다.

우선 큐가 비어있으면 삭제할 수 없기때문에 isEmpty함수로 비어있는지 확인을해주고

비어있지 않다면 front의 위치를 그 다음 위치로 바꾼다음 return해준다.

 

여기서 q->front+1을 해줬는데 그대로 반환해주나요?? 라고 할 수있다.

근데 원형큐에서는 공백상태와 포화상태 구분을 쉽게 하기 위해서 front가 있는 자리는 사용하지 않고 항상 빈자리로 두기 때문에 front+1을 해주면 그 자리에 있는 데이터가 삭제된 것이고 그 삭제된 데이터를 반환하게 된다.

즉 삭제되었지만 데이터는 남아있는 것이다.  

 

 

void initQueue(CircularQueue* q) {
	q->front = 0;
	q->rear = 0;
	
}

void printQueue(CircularQueue* q) {
	printf("Queue : ");
	if (isEmpty(q)==1) {
		printf("The queue is empty\n");
		return;
	}
	
	int i = q->front;
	while(i != q->rear) {
		i = (i+1) % Queue_SIZE;
		printf("%d ",q->items[i]);
	}
	printf("\n");
}

initQueue는 큐를 초기화 해주는 함수이고, printQueue함수는 큐를 출력해주는 함수이다.

 

initQueue는 front와 rear를 0으로 초기화해주면 되고

printQueue는 우선 함수가 비어있는지 확인해서 비어있다면 메세지를 보내고 

비어있지 않다면 현재 front의 위치를 i로 받아주고

그 i가 rear의 위치가 아니면 계속 반복해준다.

즉 front가 rear의 위치에 올때까지 반복해준다.

i는 계속 다음 인덱스로 가고 그러면 순서대로 모든 큐의 원소들을 출력해줄 수 있다.

 

int main() {
	
	CircularQueue q;
	initQueue(&q);
	
	enQueue(&q, 1);
	enQueue(&q, 2);
	enQueue(&q, 3);
	printf("Dequeue: %d\n", deQueue(&q));
	printf("Dequeue: %d\n", deQueue(&q));
	
	printQueue(&q);
	
	enQueue(&q, 4);
	enQueue(&q, 5);
	
	while(isEmpty(&q)==0) {
		printf("Dequeue: %d\n", deQueue(&q));
	}
	
	printQueue(&q);
	
	return 0;
}

메인함수까지 적어서 실행해보면

 

이런 결과가 나오게된다!