큐 자료구조의 특징은 First In First Out이라는 것이다.
큐를 구현하기 위해 보통 선형 큐를 구현하는데
배열의 메모리 공간에서 front 포인터와 rear포인터를 규칙에 맞게 이동하면서 구현하게 된다.
enqueue : rear + 1 , dequeue : front + 1
과 같이 포인터를 조정해준다.
그렇다면 원형큐는 무엇인가?
선형 큐를 구현하면서 문제는 주기적으로 enqueue 되고 dequeue되면 인덱스를 조정하면서 front가 점차 뒤로 가게되면서 앞쪽 메모리 공간을 효율적으로 사용 할 수 없게 된다. 그래서 메모리 공간을 다 쓰면 다시 앞으로 돌아와서 메모리공간에 enqueue, dequeue할 수 있는 원형 큐가 필요하게 된 것이다.
원형큐는 어떤식으로 구현하나?
우선 10의 크기를 가진 큐를 사용하기 위해서는 11만큼의 배열 사이즈를 할당해야 한다.
큐의 첫 번째 인덱스는 항상 비워두어야 하기 때문이다. 첫 번째 인덱스를 비워놓음으로서 원형 큐가 공백상태인지 포화상태인지 판단 할 수 있게 된다.
공백 상태 : front == rear
포화 상태 : front % M == (rear + 1) % M
| 초기상태 FRONT = 0 REAR = 0 |
| A, B가 차례로 삽입되면서 REAR의 포인터가 하나씩 상승했다. FRONT = 0 REAR = 2 |
| 10개의 메모리 공간이 가득 찼다. 그러므로 큐에 더 이상 값을 삽입할 수 없는 상태다. ISFULL상태 (REAR + 1) % SIZE == FRONT % SIZE 이 만족되므로 더 이상 푸시할 수 없다. |
| DEQUEUE했다. FRONT = (FRONT + 1) % SIZE 를 실행해준다. 이제 가득 차 있는 상태가 아니다. |
| 다시 하나 더 ENQUEUE해준다. 다시 가득 찬 상태가 되었다. |
| 모두 DEQUEUE해주면서 FRONT를 하나씩 증가시켜준다. 다시 제자리로 돌아온다. FRONT == REAR 조건이므로 더 이상 큐를 DEQUEUE할 수 없다. |
코드로 표현하면 다음과 같다.
ISFULL상태와 ISEMPTY상태를 따로 빼지 않았다.
<CIRCULAR QUEUE 소스 코드>
public class CirCularQueue { final int ArraySize = 10; int front = 0, rear = 0; int[] arr = new int[ArraySize]; public void Enqueue(int data){ if((rear + 1) % ArraySize == front % ArraySize){ System.out.println("CircularQueue Full!!"); } else{ rear = (rear + 1) % ArraySize; arr[rear] = data; } } public void Dequeue(){ if(front == rear){ System.out.println("CircularQueue Empty!!"); } else{ front = (front + 1) % ArraySize; System.out.println(arr[front]); } } public void showArray(){ for(int i = 1;i<ArraySize;i++){ System.out.print(arr[i] + " "); } System.out.println(); } public int getFront(){ return arr[front + 1]; } } | cs |