[자료구조] 원형큐에 대한 이해와 보강

[원형큐 구현에 대한 이해]

 

원형규는 어디든지 시작점이 가능하다는게 제일 큰 장점임.

 

따라서 enqueue를 하든 dequeue를 하든 front와 rear의 위치를 

초기화하거나 재배치할 필요가, 아니 애초에 걱정 자체를 할 필요가 없다

 

---

[원형큐 보강]

 

원형큐를 일반적으로 구현하면
빈상태와 꽉찬상태의 구분이 안간다

 

한번 생각해보면

빈상태가 front==rear인 상태일 것이다.
왜? 아무것도 없으니까

그럼 한 턴의 enqueue는 현 rear자리에 data를 집어넣고

rear++ 하는 방식으로 코드가 짜일 것이다.

그럼 이렇게 enqueue로 쭉쭉쭉 가다가 원형배열이 꽉 찼다.

그럼 rear는 어디에 있을까??
바로 front 랑 같은 위치를 가리키고 있을 거다.

이때의 enqueue 방식은 입력 후 rear 증가 이므로
마지막꺼 입력하고 rear++되어 가장 첫번째인 front와 동일한 위치를 가리키게 된다!

그럼 지금까지 설명한걸 정리해보면

빈상태일때도 front==rear이고 

꽉찬상태도 front==rear이다!

따라서, 빈상태와 꽉찬상태가 구별이 안간다는 것이다

 

사실 별로 중요한 문제는 아니다.

꼭 해결해야되는 문제도 아니고 

해결안해도 잘만 돌아가는 원형큐일 것이다!

 

하지만, 해당 원형큐를 보강하여 저 문제점을 없앨 수 있다

 

바로 시작점을 "emtpy 칸" 으로 만드는 것이다

 

자 시작점을 empty 칸으로 지정한다는 것은 뭔 의미인가 보니... 

 

 

이렇게 front 부터 data를 저장하는게 아니라 항상 front 다음부터 data를 저장해나간다는 소리임

(배열길이가 n이면 저장가능 data는 n-1개로 된다! 한 개는 empty 칸이므로)

 

이 방식대로 구현하면 빈상태와 꽉찬상태가 구분됨 ㅇㅇ

 

빈상태일때는 front==rear이고 꽉찬상태일때는 rear+1==front 이다

 

이렇게 보강했을시에 enqueue 코드 순서는

바로 rear++ 후 data 입력이다. 

시작할때 empty가 있기 때문

 

따라서 이때의 rear은 다음 data가 저장될 자리가 아닌

마지막 데이터가 저장된 자리를 가리킨다 ㅇㅇ

 

그럼 dequeue 시에는??

 

front++ 하고 출력이다.

이것도 위와 동일한 이유.

시작할때 empty 존재 ㅇㅇ