데이터의 삽입과 삭제가 서로 다은 위치에서 일어나는 자료구조이다.
선입선출(먼저 입력된 것이 먼저 출력)의 특성을 가지고 있음
FIFO (First-In-First-Out)
front와 rear의 두 개의 위치를 지정한다.
단순 배열 큐는 구현은 쉽지만 문제점이 있다.
데이터 삭제로 인한 빈 공간이 발생한다.
빈 공간을 채워 주기 위해 전체 데이터를 앞으로 이동시켜 줘야함.
이 문제를 해결하기 위해 원형큐를 사용함.
배열 전체를 사용하는 것이 아니라 한칸은 빈 상태로 만들어줘야 가득찼을 때와 빈 공간을 구별 할 수 있다.
원형 큐의 동작 방법은 배열 큐와 동일하다. 삽입할 때는 rear를 한 칸 앞으로 가서 값을 저장하고 삭제는 front를 한 칸 앞으로 가서 값을 삭제하면 되는 방식이다. 차이점은 한 칸 앞으로 갈 때 ((front+1) % 배열크기)로 가는 것이다. 즉 배열 끝에서 한 칸 앞으로 가면 다시 제일 앞으로 오는 것이다.
원형큐가 비었을 때 : rear와 front의 위치가 같을 때
원형큐가 가득 찼을 때 : rear + 1이 front 일 때이다.