[Queue] 큐의 구현

 

큐의 구현

queue 도 자료를 저장할 수 있어야 하므로 배열을 이용한다.

queue[6]

1 부터 5 까지 6 개의 공간을 가지는 queue 이다.(0 번째는 사용하지 않는다고 하자)

3 개의 원소가 삽입이 되었고, 하나의 원소가 삭제가 된 아래의 큐 구조를 생각해보자.

(a) 그림과 (b) 그림의 차이점은 삭제가 일어나는 곳을 가르키는 head 와 front 의 위치이다. front 로 이름한 큐는 삭제가 일어나는 바로 전의 위치를 따라가고 , head 는 삭제할 데이터를 가르키게 한다. 두 가지 방식으로 큐를 구현할 수 있는데 하나씩 알아보면

(a) 연결리스트를 이용한 큐의 구현 방식

(a) 방식에서 큐 삭제가 일어나는 경우 head 가 가르키는 위치의 데이터를 삭제후 head 를 1 증가 한다. 그러면 큐 가 빈 경우는 head 가 tail 보다 크지는 경우가 큐가 비었다. 그러면 처음 초기 값의 형태는 어떻게 하나?

그래서 이 방식으로 큐를 구현할 경우 빈 큐가 되었을 때 즉 데이터가 하나 남은 상태(head 와 tail 이 같아지는 경우)에서 삭제가 일어나는 경우는 head 와 tail 을 0 으로 만들어 버린다. head 혹은 tail 이 0 인 경우 (하나가 0 이면 다른 하나는 0 임)를 큐가 비었음을 의미한다. 물론 초기 상태에서의 큐도 빈 큐이므로 head 와 tail 을 0 으로 만들고 시작한다.

일반적인 경우 삽입이 일어나는 경우는 tail 을 1 증가한 후 , 데이터를 삽입한다. 일반적인 삭제가 일어나는 경우는 head 가 가르키는 데이터를 삭제후 , head 를 1 증가한다.

삽입과 삭제시 예외사항

1. 큐에 데이터가 하나 남은 경우 삭제가 일어나는 경우 head 와 tail 을 모두 0 으로 클리어
2. 빈 큐에 삽입이 일어나는 경우 head 를 1 증가(물론 tail 도 증가)

삽입과정----

if (rear == 5) 
{ 
 printf("큐가 꽉참"); 
 exit(1); 
} 
if(head==0) 
 head=1; 

rear=rear+1; 
queue[rear]=data; 

삭제과정----

if( head==0 )
{ 
 printf("큐 빔"); 
 exit(1); 
} 
data=queue[head]; 

if(head==tail) 
{ 
 head=0; 
 tail=0; 
}
else 
 head=head+1; 

간단한 소스

(b) 배열을 이용한 큐의 구현 방식

그림에서 front 의 위치는 삭제할 데이터 밑을 가르키고 있다는 것에 주목하자. 왜 front 가 2 가 아니고 1 일까?

이 질문에 답하기 전에 큐가 꽉찬 경우(삽입 불가) 혹은 비어있는 경우(삭제 불가)를 어떻게 체크할수 있을 까?

그림에서 2 번의 삽입이 이루어지면 더 이상의 삽입이 불가능하다. 즉 rear 가 큐의 제일 꼭대 기를 가르키고 있다면 큐가 꽉 찬 경우이다.(그림에서는 rear 가 5)

그림에서 2 번의 삭제가 일어난다면 더 이상 삭제할 데이터가 없다. 즉 rear 와 front 가 같아지는 경우는 큐가 비어있는 경우이다.

front 가 삭제할 데이터 바로 전 위치를 가르키는 것은 큐가 빈 상태의 체크를 용이하게 하기 위해서 이다.

삽입과 삭제 구현

삽입하는 과정은 rear 를 먼저 증가한후 데이터를 삽입

rear=rear+1; 
queue[rear]=data; 

삭제하는 과정은 front 를 먼저 증가한후 데이터를 빼냄.

front=front+1; 
queue[front]=data; 

큐가 꽉찬 경우는 rear 가 5 인 경우 이고 , 비어 있는 경우는 front 와 rear 가 같은 경우이니

삽입-------

if (rear ==5 ) 
{ 
 printf("꽉찼음"); 
 exit(0); 
} 

rear=rear+1; 
queue[rear]=data; 

삭제---------

if (rear == front ) 
{ 
 printf("비었음슴");
 exit(0); 
}

front=front+1; 
queue[front]=data; 

 

 

 

아래와 같은 구조에서 큐에 데이터를 삽입하는 경우 큐에 데이터를 삽입할 수가 없다. 빈공간이 있음에도 불구하고 큐가 꽉찼다고 데이터를 더 이상 넣을 수 가 없다. 이를 어떻게 해결할 수 있을 까?

 

2 가지 해결 방안

1. 나머지 연산자를 사용하는 경우
2. 나머지 연산자를 사용하지 않는 경우

나머지 연산자를 사용하지 않는 경우

큐를 구현하는 방법 두 가지중 그림 tail 과 head 를 사용한 구조로 환형 큐를 구현하는 방법으로 큐가 꽉찬 경우는 아래 그림과 같은 경우이다.

큐가 꽉찬 경우

위 그림에서 큐에 넣을 수 있는 데이터수가 5 개(즉 큐 사이즈 5)일 때 , 일반화를 시키면 (a) 에서는 tail-head+1 은 큐 사이즈이고 나머지에서는 tail-head+1 은 모두 0 이 된다. 즉 이런 방식으로 환형 큐를 구현할 경우 tail-head+1 은 큐 사이즈이거나 0 이 된다.

큐가 빈 경우

큐가 빈 경우는 일반 큐와 마찬가지로 tail 과 head 가 0 이 된다.

삽입---

if (tail-head+1==n or tail-head+1==0)
{ 
 printf("큐 꽉참"); 
 exit(1); 
} 

if(tail==0) 
 head=1; 

if(tail==n) 
 tail=1; 

tail=tail+1; 
queue[tail]=data; 

삭제---

if(tail==0) 
{ 
 printf("큐 빔"); 
 exit(1); 
} 

data=queue[head]; 

if (head==tail) 
{
 head=0; 
 tail=0; 
}
else if(head===n) 
 head=1; 
else 
 head=head+1; 

간단한 소스

나머지 연산자를 사용하는 경우

기본 개념은 마지막과 처음이 연결되어 있다고 하고 사용하는 것이다.

 

큐가 꽉차는 경우

이렇게 사용할 경우 큐가 꽉찬 경우 , 계속 insert 를 할 경우 rear 가 1 인 경우 , 즉 rear 와 front 가 같아지는 경우 큐가 꽉찬 경우가 된다.

큐가 비는 경우

위 그림에서 계속 삭제를 해 보면 , front 가 3 즉 rear 와 front 가 같아지는 경우가 큐가 빈 상태가 된다.

큐가 꽉찬 경우나 비어있는 경우 둘다가 front 와 rear 가 같아지는 경우가 되기에 어떤 조치를 취해야 한다.

아주 쌈박한 해결책은 아니지만 , 큐 삽입시에 아래 그림과 같은 경우 큐 가 꽉찬 경우로 인식한다.(배열 원소를 하나 버린다)

 

정리하면 , 삽입시에는 rear 를 먼저 증가시킨후 front 와 rear 가 같으면 큐가 꽉찬 경우로 인식하고 , 삭제시에는 먼저 front 와 rear 가 같으면 빈 큐로 인식한다.

삽입(insert)------------

rear=(rear+1)% 6; 

if(rear == front) 
{ 
 printf("큐가 꽉참"); 
 exit(0); 
} 
queue[rear]=data; 

삭제(delete)--------------

if(front == rear)
{ 
 printf("큐가 빔"); 
 exit(0); 
} 
front=(front+1)%6; 
data=queue[front];