환형 Queue

==========================================================================
이 글은 이론적으로 아는 것을 직접 설명 및 구현을 해 봄으로써 제 자신의
실력을 다지기 위한 글 입니다. 물론 정확한 이론. 용어도 아님을 밝힙니다.
이 글을 직.간접적으로 사용함으로써 발생되는 모든 불이익을 책임지지 않습니다.

문의점, 오류, 잘못된 용어들은 저의 홈페이지 Work 게시판을 이용하여 주시고
이상의 사항에 대하여는 최대한 덧글 ( 코멘트 ) 를 이용해 주십시오.

본 글은 저의 홈페이지인 http://ggaman.com 과
싸이월드의 (JPSC) JAVA program study club 에서 보실수 있습니다.

homepage : http://ggaman.com e-mail n MSN : chan at ggaman.com

20030828 - Chan
==========================================================================

환형큐 란 무엇인가?

이전에 있는 Queue 부분에 보면 난 다음과 같이 생각했었다.
입구와 출구는 고정 되어 있고 자료가 출력이 되고 나면
빈 칸쪽으로 데이터를 한칸씩 당겨 ( 복사하여 ) 큐의 사용 공간을 유지 할려고 했었다.

고정된 크기의 Queue에서 포인터를 이용해 다음에 꺼낼 큐를 가르킨다면
큐의 공간에 할당된 사용 가능한 횟수 이상은 사용할 수 없다.

위의 데이터를 복사하는 방식을 사용한다면 큐의 크기가 크고 이미 큐에 쌓인 자료가 많다면
복사하는데 많은 부하가 걸릴것이다.



여기서 생각을 바꾸면 좀 더 부하를 주지 않고 위와 똑 같은 것을 구현 할 수 있다.

위에서는 입구와 출구를 고정 시켜 놓고 데이터를 옮기는 방식을 사용했지만.
데이터는 그대로 두고 입구와 출구를 옮기는 방식을 택하면 된다.
입구와 출구를 옮기는것은 단지 3-4번의 비교(입력,출력이가능한가?) 와
2번의 복사 ( 입구 및 출구의 조정 ) 만 하면 된다.



큐가 원형으로 서로 붙어 있다고 생각하면 될것이다.
그림으로 본다면 아래와 같다.




입구와 출구가 처음에는 저렇게 붙어 있다.
그리고 하나의 자료를 넣는다면 아래와 같은 그림이 될것이다.


위에서는 자료를 하나 넣고 나면 다음것을 넣기 위해서 입구를 한칸 밀어 줘야 할 것이다.


다시 하나의 자료를 넣어 보자.
그렇다면 아래와 같이 될 것이다.



그렇다면 출구를 통해 하나의 자료를 빼내 보자.
그렇다면 아래와 같이 될것이다.



하나의 자료를 빼 내고 난 다음에는 출구를 하나 당겨 주어야 할것이다.



그렇다면 자료를 가득 채우면 어떻게 될까?
자료를 가득 채운다면 아래와 같은 그림이 될것이다.



하지만 위와 같이 된다면 제일 처음의 그림 ( 환형큐에 하나도 자료가 없을때 그림 ) 과
마찬가지로 입구와 출구가 한곳을 가르키게 된다.
이것을 구분하기 위해서는 어떻게 해야 할까?
간단하다.

큐의 크기에서 한칸을 비워놓고 자료를 채워야 할것이다.
만약 환형 큐가 가득 찼다면 아래의 그림이 될것이다.