[C언어] C언어로 원형큐 구현하기

 

큐는 선입선출의 자료구조형으로 가장 먼저 들어온 값이 가장 먼저 나갑니다.

 

선입선출은 표를 구매하는 것을 예시로 들 수 있습니다.

 

 

출처 : 조선일보

 

표를 구매할때는 가장 먼저 줄을 선 사람이 가장 먼저 표를 사서 나가는 구조입니다. 따라서 표 구매 또한 

선입선출의 구조를 하고 있다고 할 수 있습니다.

 

출처 : https://songeunjung92.tistory.com/23

위 사진처럼 큐는 양쪽의 두 끝 부분을 front와 rear로 지정해

front는 삭제를 rear는 삽입을 담당하고 있습니다.

 

큐에는 선형큐, 원형큐 등이 있습니다.

 

선형큐는 위 그림과 같은 모습을 하고 있습니다.

 

선형큐에는 큰 단점이 있는데, 선형큐에서 삽입 삭제를 반복하다보면 rear가 

마지막 위치를 가르킬때 앞이 비어있어도 값을 입력할 수 없는 문제가 발생합니다.

 

때문에 선형큐의 문제점을 보완한 원형큐가 생깁니다.

 

출처 : https://hokeydokey.tistory.com/37

 

원형큐는 front와 rear가 같은 위치에서 시작하며 rear가 마지막 위치에 있더라도 다음 값이 다시 

처음 위치로 돌아와 값을 저장할 수 있는 형태입니다.

 

즉, 처음과 끝이 원형으로 연결되어있는 구조 입니다.

 

이를 C언어로 구현해보겠습니다.

 

1. 입출력 구현하기

 

#include <stdio.h>
#define queue_size 4
char queue[queue_size];
int front = 0,rear=0;

int enqueue(char item){
	if(front == (rear+1)%queue_size)
	{
		printf("Queue Overflow!\n");
		return 0;
	}
	rear = ++rear%queue_size;
	queue[rear] = item;
	printf("queue : %c\n",queue[rear]);
	return 0;
}

 

먼저 큐의 사이즈를 지정합니다.

 

그리고 front와 rear변수를 선언합니다.

 

다음 입력함수인 enqueue함수를 작성합니다.

 

만약 값이 들어왔을때

front와 rear의 다음 위치가 일치할 시 오버플로우이므로 

오류 메시지를 출력합니다.

 

만약 문제가 없다면 rear의 위치를 이동시키고

그 위치에 입력한 값을 저장합니다.

 

int dequeue(){
	int data=0;
	if(front==rear)
	{
		printf("Queue Underflow!\n");
		return 0;
	}
	front=++front%queue_size;
	data = queue[front];
	printf("delete value : %c\n",data);
	return 0;
}

 

출력 함수입니다.

 

만약 front와 rear의 위치가 일치한다면

언더플로우이므로 오류 메시지를 출력합니다.

 

아무 문제가 없다면 front의 위치를 이동시킵니다.

 

2. 출력결과 확인

 

int main()
{
	enqueue('A');
	enqueue('B');
	enqueue('C');
	enqueue('D');
	dequeue();
	dequeue();
	enqueue('E');
	enqueue('F');
	enqueue('G');
	
	return 0;
}

 

ABCD를 입력하고 두번 삭제 후 다시 EFG를 입력받겠습니다.

 

 

위 사진과 같은 출력결과를 확인할 수 있습니다.

 

먼저 A, B, C는 문제 없이 입력됩니다. 

 

D에서 오버플로우가 난 이유는

rear의 위치가 다시 처음으로 돌아왔는데

front와 동일한 위치를 가지게 되기 때문입니다.

 

rear의 현 위치 ( front의 현 위치 0 )

0 -> 1(A) -> 2(B) -> 3(C) -> 0(D) = overflow

 

두번의 삭제 과정을 거치고 

 

E, F, G를 입력했을때  

G에서 오버플로우가 났습니다.

 

front의 현 위치

0 -> 1(A)  -> 2(B)

 

rear의 현 위치

3(C) -> 0(E) -> 1(F) -> 2(G) = overflow

 

이처럼 원형큐는 빠르고 지속적으로 값을 저장할 수 있다는 장점을 가지고 있습니다.

 

circular_queue.cpp

0.00MB