[자료구조] 원형 큐(Circular Queue) 개념

원형 큐 개념

👍🏻 원형 큐는 선형 큐와 마찬가지로 선입선출 형태의 데이터 구조이다. 선형 큐의 한계점을 해결하기 위해 구조화한 것으로, 배열의 마지막 인덱스에서 다음 인덱스로 넘어갈 때, (rear+1) % 배열 사이즈 공식으로 OutOfBoundException 이 일어나지 않고 인덱스 0으로 순환하는 구조를 가진다.

 

선형 큐의 문제점

선형 큐는 데이터 삽입/삭제 시 메모리 낭비가 발생한다. 선형 큐의 인덱스는 항상 배열의 마지막 인덱스를 가리키고 있기 때문에, 앞쪽에서 dequeue 로 빈 공간이 발생하고 이를 활용할 수가 없다. 그렇다고 매번 빈 공간이 없도록 데이터를 앞당길 수도 없고...

 

원형 큐의 등장

선형 큐는 데이터를 가리키는 인덱스가 하나였지만, 원형 큐는 front, rear 로 두 개의 인덱스 변수가 존재한다. 

✨ 원형 큐는 포인터 증가 방식이 (rear+1)%array size 형식으로 변환하기 때문에 배열의 첫번째 인덱스부터 다시 삽입하여 재활용이 가능해진다. 

 

원형 큐 - 삽입 

rear 포인터를 +1 증가 시키고 그 위치에 데이터를 삽입한다.

만약 rear+1 이 배열의 끝이고 포화상태가 아니라면 첫번째 인덱스에 데이터를 넣는다.
* 배열의 포화상태 여부를 판단하기 위해 배열의 1칸은 비워둔다. 

✔ (rear+1)%array size == front 값과 동일하다면 배열이 포화상태인 것으로, 데이터를 삽입하지 않는다. 

 

원형 큐 - 제거

front +1 증가시키고 그 위치의 데이터를 배열에서 가지고 온다. 

✔ rear==front 조건이라면 배열이 공백인 것으로 판단해 제거하지 않고 넘어간다. 

 

💬 쉽게 정리하기

데이터를 추가하면 rear 값은 증가하고, 
데이터를 제거하면 front 가 가리키던 곳의 데이터를 제거하고 front 값이 증가한다. 

 

예제

ex ) 사이즈 4 짜리 원형 큐 
1. rear = 0 / front = 0
-> dequeue 불가. (rear == front)

2. enqueue 
(rear+1)%arrsize = 1%4==1 (!=front)
rear = 1 / front = 0  증가. 

3. enqueue
(rear+1)%arrsize = 2%4==2 (!=front) enqueue 가능.
rear = 2 / front = 0 증가.

4. enqueue
(rear+1)%arrsize = 3%4==3 (!=front) enqueue 가능.
rear = 3 / front = 0 증가.

5. dequeue 
front != rear 즉, 
(front+1)%4 한 인덱스에 있는 배열 가져오기. ==1 
rear = 3 / front = 1

6. dequeue
front != rear 즉
(front+1)%arrsize ==2 에 있는거 빼기 
rear = 3/ front = 2

7. enqueue 
(rear+1)%arrsize = 4%4==0(!=front) enqueue 가능.
rear = 0 (0위치에 데이터 넣기.) / front = 0

 

✔ 필요한 class 함수

• isEmpty() : 원형 큐가 비어있는지 체크 
• isFull() : 원형 큐가 가득 찼는지 체크 
• enqueue() : 원형 큐에 데이터 삽입
• dequeue() : 원형 큐에 데이터 삭제 
• peek() : 원형 큐에서 front+1 위치에 있는 데이터 반환
• clear() : 원형 큐를 초기화