스택은 데이타의 출입구가 한 군데인데 반해, 큐는 데이타 입출입이 양뱡향입니다. FIFO(First in First Out)구조를 가졌습니다. 터널을 지나는 자동차를 생각해보면 터널은 큐고 터널의 길이는 큐의 크기가 됩니다. 그리고 자동차는 데이타가 되겠죠.
큐도 스택과 비슷하고 데이타의 입력방향과 출력방향이 다르다는 것만 주의하면 됩니다. 스택에서는 offset(오프셋)을 기억하는 변수를 하나만 두었지만, 큐에서는 입력과 출력의 위치가 다르기 때문에 두개를 두어야합니다.
데이타가 머리부터 차례로 입력된다 생각하고 변수를 정하면, FIFO구조기때문에 출력위치는 머리가 됩니다. 그리고 입력위치는 꼬리가 되겠죠.
출력위치를 가리키는 변수를 head, 입력위치를 가리키는 변수를 tail이라고 하면 구조는 다음과 같습니다.
2014/02/28 - [프로그래밍/C언어] - 동적배열 자료구조의 시작
2014/03/17 - [프로그래밍/C언어] - 동적배열에서 memmove함수 사용하기 연습 C언어
2014/03/20 - [프로그래밍/C언어] - 자료구조 - 연결리스트[linked list] C언어
2014/03/21 - [프로그래밍/C언어] - 자료구조 스택(stack) C언어
위 그림은 데이타를 아무것도 안 넣은 초기화 상태입니다.
이 그림은 데이타를 넣기만 한 상태입니다. 초기화 상태에서 오프셋변수의 위치가 배열의 요소 0을 같이 가리키므로 데이타 입력하려면 tail의 위치를 참조하여 데이타를 입력한 후에 tail의 값을 +1해야합니다. 그래서 tail은 항상 다음에 입력할 위치를 가리킵니다. 그리고 head는 현재 지울 위치를 가리키게됩니다.
데이타를 세개 지워봤습니다. tail은 데이타를 입력한 후 값이 증가되지만 head는 데이타를 지운후 값이 증가됩니다. 그래서 head는 항상 지울 데이타를 가리키게 됩니다. 그런데 문제는 이렇게 증가만 하게되면 앞쪽에 한번 사용했던 요소들은 다시 사용할 수 없다는 것입니다. 오프셋 변수가 가리키는 위치가 배열의 끝에 다다르게 되면 문제가 됩니다. 해결방법으로 배열의 끝과 처음을 연결하면 데이타가 꽉 차기전까지 영구적으로 공간을 사용할 수 있습니다. 이는 %연산으로 해결할 수 있습니다.
위와같이 tail의 위치가 요소의 마지막을 가리키는 경우를 생각해보죠. 데이타를 입력하게되면 tail의 값은 10으로 증가하게 됩니다. 즉 tail+1=10이된다는 말인데 %size 연산을 하게되면 0이 되죠. 그러면 데이타는 큐를 꽉 채운 상태가 되고 tail과 hea는 동일한 장소를 가리키게됩니다.
그런데 원형큐를 사용하면서 이렇게 큐를 완전이 채우게되면 문제가 생기게됩니다. 제일 처음 그림을 다시보면 head==tail인 상태고 비어있는 상태입니다. 하지만 위그림에서 데이타를 꽉 채우게되면 head==tail이면서 데이타가 꽉 채워진 상태가 됩니다. 동일한 head==tail이지만 큐의 상태는 반대가됩니다.
큐에 데이타를 입력시에 먼저 검사해야할 조건이 큐가 꽉 차있는 상태인지를 알아야하는데 그 조건이 큐가 빈상태와 동일한 head==tail이라면 초기화와 동시에 문제가 발생합니다. 그래서 우리는 큐가 꽉 찬 상태를 위 그림과 같은 상태 즉 (tail+1)%size==head인 경우로 합니다.
조건을 검사하는 방법은 입력시에는 큐가 꽉 찼는지 (tail+1)%size == head 인지를 검사하고 출력시(데이타의 삭제)에는 head==tail인지 아닌지를 검사하면 됩니다.
다음은 코드입니다.
나머지 코드는 스택과 비슷합니다. 여기서는 배열을 사용하였지만, 연결리스트를 사용하는 방법도 있습니다. 배열을 사용할 경우에는 정해진 size만큼만 사용할 수 있고, 연결리스트를 사용할 경우에는 무한대로 사용이 가능하다는 점이 장점이 있습니다.