Page 145 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)
P. 145
링 버퍼로 큐 만들기
이번에는 배열 요소를 앞쪽으로 옮기지 않는 큐를 구현해 보겠습니다. 이를 위해 사용하는 자
료구조가 링 버퍼(ring buffer)입니다. 링 버퍼는 그림 4-9처럼 배열의 처음이 끝과 연결되었
다고 보는 자료구조입니다. 여기서 논리적으로 어떤 요소가 첫 번째 요소이고 어떤 요소가 마
지막 요소인지 식별하기 위한 변수가 프런트(front)와 리어(rear)입니다.
여기서 프런트(front)와 리어(rear)는 논리적인 데이터의 순서를 말합니다(배열의 물리적 요소의 순서는 아닙니다).
프런트(front) : 맨 처음 요소의 인덱스
리어(rear) : 맨 끝 요소의 하나 뒤의 인덱스(다음 요소를 인큐할 위치를 미리 지정)
11 ０ ０ 73
맨 끝 １ 19
10 １ 맨 끝
95 73 ❷
68 19 ３
９ ❷ rear ４
24
５
６
56
８ ３ ❼ 35 맨 처음
35 ８ 56
９ 24
맨 처음 ❼ ４ １０ 68
front ６ ５ １１ 95
[그림 4-9] 링 버퍼를 사용하는 큐의 구현
인큐와 디큐를 수행하면 프런트와 리어 값이 아래와 같은 과정을 거치게 됩니다(그림 4-10).
1. 7개의 데이터(35, 56, 24, 68, 95, 73, 19)가 차례대로 que[7] que[8], …, que[11], que[0],
que[1]에 저장됩니다. 프런트 값은 7이고 리어 값은 2입니다(그림 a ).
2. 그림 a 에 82를 인큐한 다음의 상태입니다. que[2](리어가 가리키고 있는 위치)에 82를 저장
한 다음 리어 값을 1만큼 증가합니다(그림 b ).
3. 그림 b 에 35를 디큐한 다음의 상태입니다. 프런트 요소(que[front], que[7])의 값 35를
빼고 프런트 값을 1만큼 증가합니다(그림 c ).
이렇게 큐를 구현하면 프런트와 리어 값을 업데이트하며 인큐와 디큐를 수행하기 때문에 앞
에서 발생한 요소 이동 문제를 해결할 수 있습니다. 물론 처리의 복잡도는 O(1)입니다.
앞에서 구현한 큐는 요소 이동을 수행하기 때문에 복잡도가 O(n)이었습니다.
04•스택과 큐 145
