[소프트웨어공학] 원형 큐

원형 큐 (circular queue)

1) 특징

- 초기 자료가 없을 때, front = rear = 0 또는 -1;

- 입력 : rear 증가 자료 입력

- 출력 : front 증가 자료 출력

- mod 연산을 통해 front와 rear 값 계산

2) 공백상태 포화상태 구별

i) flag 변수 사용

flag = 0 //빈상태
flag = 1 //포화상태

 

ii) 기억장소 하나 포기

  포화상태라도 front =/= rear임!

 공백상태 : front = rear
 포화상태 : front == rear+1

 

 

3) 알고리즘

//2019 국가 7급 자료구조론

#define MAX_QUEUE_SIZE 10 //크기가 10인 큐
int queue[MAX_QUEUE_SIZE];
int front = rear = -1; //초기상태
void addq(int front, int *rear, int item) {
	*rear = (*rear+1) % MAX_QUEUE_SIZE; //새 값이 들어갈 자리주소
    if(front == *rear){  //꽉 차있을 때,
    	printf("Queue if full!!\n");
        return -1;
    }
    queue[*rear] = item;
}

 

4) 문제 포인트

공백상태에서만 front와 rear이 값이 서로 같다 

 = 기억장소를 하나 포기한 원형 큐

 = 포화상태 : front = rear +1

 

왼쪽이  공백큐 오른쪽이 꽉 찬 큐