[C++] 나만의 Queue만들기 (2) - 원형 큐, 기초

이전 포스팅에서 구현했던 '동적 배열 큐'(선형큐)의 단점을 보완한 '원형 큐'.

원형큐는 선형큐의 단점인 '빈 공간 낭비'를 해결해서, 비교적 효율적으로 빈 공간을 관리한다.

원형큐를 간단하게 설명하면 데이터를 추가할 때 뒷 공간이 꽉차면 다시 비어있는 앞공간을 메꾸는 원리이다.

 

선형큐처럼 front와 rear변수로 데이터의 입출력위치를 관리한다

front: Dequeue()호출 시 꺼낼 데이터의 위치를 가리킴.(큐에 데이터가 없다면 빈 공간을 가리킴.)

rear: Enqueue()호출 시 데이터를 추가할 빈 공간을 가리킴.(큐에 데이터가 꽉차면 빈 공간이 아니라 데이터를 가리킴)

나는 front는 꺼내야할 데이터의 위치를, rear는 데이터가 추가될 빈공간의 위치를 가리키게 했는데,

구현하는 사람에 따라서 다르게 작성할 수도있다. 

 

여기서 데이터를 En,Dequeue하게 되면...

rear는 항상 빈 공간을 가리켜야하고, front는 항상 데이터를 가리켜야한다.

rear가 데이터를, front가 빈공간을 가리키는것은 큐에 데이터가 꽉차있거나 비었다는 뜻이다.

 

여기서 데이터를 3개이상 추가한다고 했을 때, 선형큐같은 경우 큐의 크기가 커져야 한다.

원형큐라면?

숫자 7데이터가 큐의 처음 위치로 오게 되었다.

이 모양을 선형으로 표현하면 아래의 모습으로 나온다

 

여기서 데이터를 하나 더 추가하면?

이런 모습이 되고 front와 rear가 같은곳을 가리키고 있다.

이렇게 front와 rear가 같은곳을 가리킨다면 큐가 비어있거나, 꽉찼다는 의미이다

 

꽉 차게 되면 Enqueue를 할 수 없다.

 

https://github.com/ForestBird1/MyContainer

GitHub - ForestBird1/MyContainer