반응형

[ 이 게시물은 개념 설명 게시물이고 소스코드는 다음 게시물에 있습니다. ]


원형 큐(Circular Queue)는 연결 리스트 기반 큐를 동그랗게 만든 것이라 생각하면 된다. 




위의 그림 처럼 처음 이상태로 F,R이 위치해있다.


노드에 값이 들어오기 시작할때는 F는 고정된 채로, R이 움직이게된다.


이때 원형 큐에서는 R이 9 다음 다시 F로오게되는데 이러한 오류 


즉, 어디가 처음인지 구분을 하기위해 F에는 0을 설정한다. (그림에서는 빈공간으로 표현했지만 코드에서는 0을 넣어둔다.)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int NextPosIdx(int pos) // 큐의 다음 위치에 해당하는 인덱스 값 반환
{
    if (pos == QUE_LEN - 1//  만약 현재위치가 큐길이 - 1이라면 // 즉 배열의 마지막 요소의 인덱스 값이라면
        return 0// 0을 반환(큐의 끝에 도달했으므로 회전을 돕는 함수이다)
 
    else
        return pos + 1// 그외에는 다음 큐를 가리키도록
}
 
void Enqueue(Queue *pq, Data data)
{
    if (NextPosIdx(pq->rear) == pq->front// 큐가 꽉 찼다면,
    {
        printf("Queue Memory Eroor!"); // 여기 접근을 할 수 없는 코드인데 접근한다면 에러구문 표시 후 종료
        exit(-1); // 즉, 원형 큐에서는 전체크기 - 1을 기준으로 F,R이 만나지 않게되는 알고리즘인데 F==Q가 될 수 없다.
    }
 
    pq->rear = NextPosIdx(pq->rear); // rear을 한 칸 이동
    pq->queArr[pq->rear] = data; // rear이 가리키는 곳에 데이터 저장
}
 
 
Crocus


이 코드에서 알수 있는 내용은


Enqueue함수 if(NextPosIdx(pq->rear) == pq->front) 의 해석은


만약 위의 그림처럼 F가 현재 0, R이 9를 가리키고 있는 상황일때


NextPosIdx에 QUE_LEN-1이 R위치라면 0을 반환하고


다시 if(NextPosIdx(pq->rear) == pq->front)로 와서


if( 0 == pq->front) 이런 식이 형성된다.


이때, pq->front는 0을 나타내고있으니 if(0 == 0) 즉 참이므로, 이런 상황에 Enqueue함수를 실행하면 오류를 범하게 되는 것이다.

반응형