Special Effects FX 스스로를 감동시켜야 최선을 다 한 것이다.

F(Front), R(Rear)

F는 큐의 머리를, R은 큐의 꼬리를 가리키는 일종의 변수를 의미.

R이 배열의 끝에 도달하면, 다시 맨 앞으로 이동시켜서 R이 회전하게 만든다. 물론 R을 뒤쫗아 가는 F도 배열의 끝에 도달하면 회전해야 한다. 그리고 이러한 방식으로 동작하는 배열 기반의 큐를 가리켜 '원형 큐(Circular Queue)' 라 한다. 

논리적으로 배열이 원형의 형태를 갖춘다고 해서 붙여진 이름이다.

원형 큐의 문제점

원형 큐는 F와 R의 위치만 가지고는 꽉 찬 경우와 텅 빈 경우를 구분할 수가 없다.

원형 큐의 문제해결

배열을 꽉 채우지 않는다. 꽉 차면 구분이 안되니 꽉 채우지 않는다.

즉, 배열의 길이가 N이라면 데이터가 N-1개 채워졌을 때, 이를 꽉 찬 것으로 간주한다.

이렇게 하면 저장 공간 하나를 낭비하지만 이로 인해서 문제 하나가 해결이 되는 셈이니 잃는 것보다 얻는 것이 더 많다.

실제 큐의 구현을 위해서 인지하고 있어야 하는 2가지

1. enqueue 연산 시, R이 가리키는 위치를 한 칸 이동시킨 다음에, R이 가리키는 위치에 데이터를 저장한다.

2. dequeue 연산 시, F가 가리키는 위치를 한 칸 이동시킨 다음에, F가 가리키는 위치에 저장된 데이터를 반환 및 소멸한다.

이 중에서 특히 dequeue 연산 시에도 F가 가리키는 위치를 우선 한 칸 이동한다는 사실을 잊어선 안된다.

이로써 구현할 큐의 특성 두 가지를 다음과 같이 추가로 정리할 수 있다.

# 원형 큐가 텅 빈 상태        -        F와 R이 동일한 위치를 가리킨다.

# 원형 큐가 꽉 찬 상태        -        R이 가리키는 위치의 앞을 F가 가리킨다.

Header File

Source File

Main File