queue 란

영화관에서 줄을 서는 경우를 생각해 보자.

줄을 설때는 뒤에서 서고 , 입장은 앞에서 부터 해 나간다. 이런 구조를 queue 라 한다. queue 의 영어단어뜻도 줄을 서다라는 의미이다.

queue 구조에서는 두 개의 변수가 필요하다. 줄을 설때 즉 삽입시에 뒤에서 서야 하므로 뒤를 가르키는 rear 혹은 tail 이란 변수가 필요하고 , 입장 즉 삭제시에는 앞에서 부터 삭제되므로 앞을 의미하는 front 혹은 head 라는 변수가 필요한다.

queue 구조는 한 쪽끝에서(rear) 에서 삽입이 일어나고 , 한쪽 끝에서(front) 삭제가 일어나는 구조이다.

[애플릿 보기]

queue 구현

[애플릿 보기]

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

queue[6]

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

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

(a) 방식

그래서 이 방식으로 큐를 구현할 경우 빈 큐가 되었을 때 즉 데이터가 하나 남은 상태(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) 방식

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

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

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

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

삽입과 삭제 구현

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

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

삽입-------

if (rear ==5 ) {
   printf("꽉찼슴");
   exit(0);
}
rear=rear+1;
queue[rear]=data;

if (rear == front  ) {
   printf("비었슴");
   exit(0);
}
front=front+1;
queue[front]=data;

간단한 소스

환형 큐(circular queue)

[애플릿 보기]

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

2 가지 해결 방안

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

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

큐가 꽉찬 경우

위 그림에서 큐에 넣을 수 있는 데이터수가 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;

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