Queue

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

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

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

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

20030827 - Chan
==========================================================================

Queue ( 이하 큐 ) 는 자료구조의 일종이다.
그림으로 그린다면 아래와 같은 구조를 가지고 있다.



한쪽 방향으로 들어가서 다른 한쪽 방향으로 나오는 모양이다.
즉 빨대나 대롱 모양과 같은 것이다.
( FIFO : First In First Out  라고 한다. )


먼저 1 이라는 데이터가 들어 가고 2 , 3 이 각각 들어가고,
데이터를 하나씩 꺼낸다면 제일 처음 들어간 1 일 제일 처음 나오는 것이다.


사용되는 곳에는 주로 운영체제에서 사용된다.
사용자의 이벤트가 순서대로 이루어져야 하기 때문에
그 순서대로 큐에 들어 가고. 큐에서 이벤트를 순서대로 꺼내 운영체제가 실행 시키는 것이다.

예를 든다면
마우스를 움직이고 난 뒤에 클릭을 하는 것은.
움직이는 것이 먼저 큐에 들어가고 그후 클릭하는것이 큐에 들어가는 것이다.
( 물론 워낙 빨라서 움직이는 것이 다 처리 되어 버렸을 것이다. )
( 위의 예는 부정확한 예임을 알린다. )




현재 내 생각으로는 구현상에 문제점이 있다.

큐의 크기가 정해져 있다면..
만약 큐에 3개의 데이터가 들어 갔다가, 거기서 하나의 데이터를 꺼냈다면.
현재는 2,3번에만 데이터가 들어 있을 것이다.
여기서 두가지 선택을 할 수 있다.

첫번째.
2,3 번째 있는 데이터를 각각 1, 2 번째로 옮긴다.
그런후에 다시 데이터를 꺼낼때 1번에 있는 것을 꺼낸다.

이것의 문제는 만약 큐에 데이터가 많이 쌓여 있다면,
그 만큼 복사하는데 부하가 걸릴것이다.
하지만 데이터를 꺼낼때는 항상 1번에 있는 자료를 꺼낼 수 있다.


두번째.
처음에 1번의 자료를 꺼냈으므로
어디의 자료를 꺼내야 할 지 알려주는 포인터를 지정하여
그 포인터를 2번째 칸을 가르키도록 한다.

이것의 문제점은 이미 고정 되어 있는 큐의 크기를 넘어 버리면
더이상 큐에 데이터를 채우지 못하는 문제가 있다.
하지만, 첫번째의 예처럼 자료를 복사하는데 부하는 없을 것이다.




링크드 리스트를 이용한다면 큐의 크기를 정하지 않고 사용할 수 있다.
단 링크드 리스트는 구조체를 이용하고 사용에 난해한 점 ( 크기가 정해져 있는것보다 ) 이 있다.

구현은 다음과 같다.
큐에서 하나의 자료를 넣는다면 한개의 자료는 구조체로 이루어 질것이고
그 구조체는 데이터와 다음에 올 구조체를 가르킬 포인터를 만든다.


제일 처음 5라는 자료를 넣고 꺼낼 포인터(*point)에 5가 들어 있는 구조체를 가르킨다.
그리고 다시 7 , 8 , 10 을 각각 넣는다.
물론 각 데이터를 넣을 때에는 이미 앞에 있는 구조체를 가리킬 수 있게 해 놓는다.
그림으로 본다면 이상의 과정이 아래와 같은 것이다.



이제 자료를 꺼내보자. 우선 *point 가 가르키고 있는 자료를 꺼낼것이다.
그렇다면 물론 5라는 데이터를 꺼낼수 있을 것이다.
그런뒤에 5가 들어 있는 구조체가 다음에 있는 데이터( 7 )를 가르키는 포인터를
임시 기억 공간에 저장 시켜 놓는다.
이제 5라는 기억공간은 사용했으므로 없애 주어야 하기 때문에 메모리를 풀어주고
임시 기억 공간에 저장시켜 놓았던 7 이 들어 있는 구조체 주소를 *point 에 넣어 준다.

그러므로 *point 가장 앞에 있는 자료 7 을 가지게 될것이다.
( 이미 5는 꺼내 버렸음. )



책이나 다른 예제에서 보면 이렇게 리스트를 이용해서 구현을 해 놓았다.
( 물론 아래에 있는 Stack의 예제 역시 리스트를 이용해서 구현해 놓았다. )