원형 큐(Circular queue)

일반 큐의 문제점

일반적인 큐는 배열로 일직선으로 구현되어짐. 그리고 선입 선출이라 맨앞에 데이터가 빠져나가면 한칸씩 앞으로 당겨야되기때문에 성능적으로 좋지 않음

 

원형 큐

말그대로 큐를 선형이 아닌 원형으로 생각하여 구현 하는 것이다.

• enqueue() : 원소 뒤에서 삽입
• dequeue() : 원소 앞에서 삭제
• isEmpty() : 공간 확인
• getSize() : 사이즈 반환

lastOp 변수를 사용하여 큐의 공간 전부를 사용할 수 있게 한다. (즉 원형 큐 문제점 해결방안)

쉽게 이야기하면 마지막 연산을 기록해두는 변수이다.

삽입이 마지막이면 push, 삭제가 마지막이면 pop로 설정하여 front == rear 일때 lastOp가 push이면 포화, lastOp가 pop이면 공백

하지만 큐의 삽입 삭제 연산이 느려짐...