원형 큐(circular queue)와 큐(queue)의 차이점?

1. 큐(queue)

 

선형 자료구조

 

먼저 들어간 데이터가 먼저 나오는 자료구조(First In First Out)

 

큐에 자료를 넣는 것을 enqueue

 

큐에 자료를 빼는 것을 dequeue라고 부른다

 

front, rear 포인터가 무조건 뒤로만 이동하여, 앞부분의 데이터가 삭제되면 다시 삽입할 수 없다는 단점이 있다

 

front 포인터는 삭제할 위치

 

rear 포인터는 삽입할 위치

 

 

 

 

여기서 10을 넣으면

 

 

 

다시 20을 넣으면

 

 

다시 30을 넣으면

 

 

 

 

이제 10을 제거하면

 

 

 

다시 20을 제거하면

 

 

 

 

여기서 40을 넣으면...

 

앞에 들어가는게 아니고 뒤에 들어가는데 이렇게 앞에 공간이 비어있음에도 활용하지 못하는 단점이 있다

 

 

 

 

 

2. 원형 큐(circular queue)

 

큐의 끝과 시작을 연결한 큐

 

rear 포인터가 끝에 도달했으면 다시 처음으로 되돌아옴

 

여전히 먼저 삽입한 데이터가 먼저 나온다는 First In First Out의 구조이지만,

 

선형 큐와는 다르게 rear 포인터가 끝에 도달하면 처음으로 다시 돌아오므로,

 

앞에 빈 공간에도 삽입할 수 있다는 장점이 있다.

 

 

 

 

10, 20, 30을 순서대로 넣으면

 

 

 

 

10,20을 제거하면

 

 

 

 

여기서 40을 넣으면 rear 포인터가 앞으로 되돌아와서 40을 넣는다

 

 

 

 

여기서 dequeue를 하면 어떤 데이터가 빠질까?

 

앞에 있는 40이 빠지나 뒤에 있는 30이 빠지나?

 

어쨌든 원형 큐도 큐이므로 먼저 들어온 30이 빠지게 된다

 

 

 

 

 

특이할 사항으로 여기서 마지막 한칸을 비워뒀는데

 

원형 큐 구현할 때는 한칸을 비워두는게 보통이래

 

front를 첫번째 데이터의 인덱스(삭제할 데이터의 인덱스), rear을 현재 빈 곳라고 한다면,

 

front = rear이면 공백 상태

 

(rear+1) % (큐 사이즈) = front이면 포화 상태로 쉽게 구별할 수 있다네

 

front = rear이면 공백인건 너무 명확하고

 

포화상태이면 다음 그림과 같다

 

 

 

 

(r+1) % q = f이면 삽입이 불가능해서, 삭제만 해야한다.

 

꼭 한칸 안비워도 되는데 비우면 구현이 편해진대