[자료구조] 큐(Queue)

 

 

❓ 큐(Queue) 

 

큐 (Queue)는 FIFO (First In First Out) 구조를 가진 자료구조이다.
First In, 가장 먼저 삽입된 데이터가, First Out, 가장 먼저 삭제된다는 뜻이다.

 

 

 

1부터 5까지 삽입한 queue

enqueue와 dequeue를 진행한 모습

 

 

 

큐는 가장 먼저 삽입된 데이터의 위치를 front, 가장 마지막에 삽입된 데이터의 위치를 rear라고 부른다.

front에서 데이터를 삭제하는 것을 dequeue, rear에서 데이터를 삽입하는 것을 enqueue라고 한다.

 

dequeue를 하게되면 front의 데이터를 삭제하고 위치를 옮긴다.

enqueue를 하게되면 rear가 새로운 데이터를 가리키게 된다.

 

위 그림과 같은 구조의 큐는 선형 큐(Linear Queue)라고도 부른다.

선형 큐는 삭제와 삽입이 반복되면 계속 길어지고 뒤로 밀리는 구조다.

그림에선 편의상 front의 데이터가 삭제될때 정말 없어지는 것처럼 묘사했지만

사실 실제 데이터가 삭제되는게 아닌 더이상 접근할 수 없어지는 것이다.

그래서 과정이 길어질수록 메모리누수가 발생한다.

이런 단점을 보완한 것이 바로 원형 큐(Circur Queue)이다.

 

❓ 원형큐(Circur Queue)

 

원형큐는 선형큐에서 활용하지않았던 공간을 재활용함으로써 메모리성능을 향상시켰다.

 

 

원형큐의 예시

 

그런데 원형큐에도 허점이 있다.

위 예시를 보면 아무것도 들어있지 않을 때는 front와 rare의 값이(위치가) 같다.

그런데 1이 삽입되었을때도 front와 rare가 동일하다.... 

이렇게 원형큐가 비었는지를 확인할 수 없게 되는 문제가 발생한다.

이 문제는 front가 가리키는 공간 하나를 비워두고 사용하면 해결된다.

큐가 비었을때는 rare == front, 가득 찼을때는 rare + 1 == front로 확인이 가능하게 된다.