큐(Queue)

큐는 FIFO (First In First Out) 자료구조이다.

 

이해가 쉽게 안된다면 버스 줄을 생각하면 쉽다.

 

첫번째로 줄에 들어온 사람이 첫번째로 줄에서 나간다.

 

큐의 성질

• 원소의 추가: O(1)
• 원소의 제거: O(1)
• 제일 앞/뒤의 원소 확인 O(1)
• 제일 앞/뒤가 아닌 원소 확인 원칙적으로 불가능

 

큐는 데이터를 rear(뒤쪽)에 추가하고 front(앞쪽)에서 제거한다.

 

 

큐를 배열로 구현하면 rear은 데이터가 추가될 때마다 1 증가하고, front 또한 데이터가 제거될 때마다 1씩 증가한다.

rear와 front가 뒤쪽으로 계속 밀리면서 큐 앞쪽에 쓸모없이 차지되는 공간이 생기게 된다.

 

이를 해결하는 방법은 간단한데, 원형 큐를 쓰는 것이다.

큐의 원소가 들어갈 배열을 원형으로 만드는 것을 원형 큐라고 한다.

관념적으로는 원형이지만, 실제 구현할 때는 그냥 지정된 큐 크기를 넘어설 때 0번지로 다시 오도록 하면 된다.