카누누카

(C) 자료구조 - 원형 큐의 구현 본문

자료구조

(C) 자료구조 - 원형 큐의 구현

괴물좐 2023. 10. 24. 16:19

3. 원형 큐의 구현

순차 큐의 잘못된 포화 상태 인식 문제를 해결하기 위해 원형 큐를 사용한다.

 

원형 큐는 순차 큐와 같은 1차원 배열을 사용하지만, 논리적으로 배열의 처음과 끝이 연결되어 있는 원형 구조로 가정하고 사용한다.

 

<원형 큐의 논리적 구조>

 

 

 

 

 

 

 

 

 

 

 

 

원형 큐에서는 초기 공백 상태일 때 front와 rear의 값을 0으로 하고, 공백 상태와 포화 상태를 쉽게 구분하기 위해서 자리 하나를 항상 비워 둔다. 원형 큐에서도 공백 상태에는 front와 rear의 위치가 같다.

 

순차 큐와 마찬가지로 rear가 다음으로 이동하면서 원소를 삽입하고, front는 rear가 이동한 방향으로 따라가면서 원소를 삭제한다. 

 

원형 큐에서는 인덱스가 n-1 다음에 다시 0이 되어야하므로 사용할 인덱스를 조정하기 위해 나머지 연산자 mod를 사용한다.

 

<순차 큐와 원형 큐의 비교>

종류 삽입 위치 삭제 위치
순차 큐  rear = rear + 1 front = front + 1
원형 큐 rear = (rear + 1) mod n front = (front + 1) mod n

- 순차 자료구조를 이용한 원형 큐의 알고리즘

- 큐 원소 정의 및 1차원 배열 큐 선언

1
2
3
4
5
6
7
8
#define cQ_SIZE 4
 
typedef char element;                    // 큐 원소(element)의 자료형을 char로 정의
 
typedef struct {
    element queue[cQ_SIZE];            // 1차원 배열 큐 선언
    int front, rear;
} QueueType;
 cs

 

1. 공백 원형 큐 생성

새로 생성한 공백 원형 큐는 front와 rear의 초깃값으로 0을 사용한다.

1
2
3
4
5
6
7
8
// 공백 원형 큐 생성
QueueType* createCQueue(void) {
    QueueType* cQ;
    cQ = (QueueType*)malloc(sizeof(QueueType));
    cQ->front = 0;                        // front 초깃값 설정
    cQ->rear = 0;                        // rear 초깃값 설정
    return cQ;
}
 cs

 

2. 원형 큐의 공백 상태 검사

원형 큐를 생성하여 front와 rear가 0인 경우와 마지막에 삽입한 원소, 즉 rear의 원소를 삭제하여 front와 rear가 같은 위치가 된 경우에 원형 큐의 상태는 공백이 된다. --> front == rear : 원형 큐의 공백 상태 조건

1
2
3
4
5
6
7
8
// 원형 큐가 공백 상태인지 검사하는 연산
int isCQueueEmpty(QueueType* cQ) {
    if (cQ->front == cQ->rear) {
        printf(" Circular Queue is empty! ");
        return 1;
    }
    else return 0;
}
 cs

 

3. 원형 큐의 포화 상태 검사

rear가 원형 큐를 한 바퀴 돌면서 원소를 삽입하여 큐를 모두 채우면 그 다음 rear의 위치, 즉(rear+1) mod n은 현재 front 위치가 되어 더 이상 원소를 삽입할 수 없는 포화 상태가 된다. --> (rear+1) mod n == front : 원형 큐의 포화 상태 조건

1
2
3
4
5
6
7
8
// 원형 큐가 포화 상태인지 검사하는 연산
int isCQueueFull(QueueType * cQ) {
    if (((cQ->rear + 1) % cQ_SIZE) == cQ->front) {
        printf(" Circular Queue is full! ");
        return 1;
    }
    else return 0;
}
 cs

 

4. 원형 큐의 원소 삽입

포화 상태가 아닌 경우에만 삽입 연산을 수행한다.

 

1) 나머지 연산자를 사용하여 rear값을 조정한다.

2) rear에 대한 원형 큐의 원소, 즉 cQ[rear]에 원소 item을 삽입한다.

 

-> 원형 큐에서 삽입할 자리를 정하기 위해서 나머지 연산자를 사용한다.

ex) rear의 위치가 2라면 (2+1) mod 4 = 3이 되어, 다음 삽입 위치는 cQ[3]이 된다.

ex) rear의 위치가 3이라면 (3+1) mod 4 = 0이 되어, 다음 삽입 위치는 cQ[0]이 되어 원형 큐의 동작을 하게 된다.

1
2
3
4
5
6
7
8
// 원형 큐의 rear에 원소를 삽입하는 연산
void enCQueue(QueueType* cQ, element item) {
    if (isCQueueFull(cQ)) return;
    else {
        cQ->rear = (cQ->rear + 1) % cQ_SIZE;
        cQ->queue[cQ->rear] = item;
    }
}
 cs

 

5. 원형 큐의 원소 삭제

공백 상태가 아닐 때만 삭제 연산이 수행한다.

 

1) 나머지 연산자를 사용하여 front값을 조정한다.

2) front 자리에 있는 원형 큐의 원소, 즉 cQ[front]를 삭제하여 반환한다.

1
2
3
4
5
6
7
8
// 원형 큐의 front에서 원소를 삭제하고 반환하는 연산
element deCQueue(QueueType* cQ) {
    if (isCQueueEmpty(cQ)) return;
    else {
        cQ->front = (cQ->front + 1) % cQ_SIZE;
        return cQ->queue[cQ->front];
    }
}
 cs

 

6. 원형 큐의 원소 검색

1
2
3
4
5
// 원형 큐의 가장 앞에 있는 원소를 검색하는 연산
element peekCQ(QueueType* cQ) {
    if (isCQueueEmpty(cQ)) return;
    else return cQ->queue[(cQ->front + 1) % cQ_SIZE];
}
 cs

 

7. 원형 큐의 원소 출력

1
2
3
4
5
6
7
8
9
10
11
12
13
// 원형 큐의 원소를 출력하는 연산
void printCQ(QueueType* cQ) {
    int i, first, last;
    first = (cQ->front + 1) % cQ_SIZE;
    last = (cQ->rear + 1) % cQ_SIZE;
    printf(" Circular Queue : [");
    i = first;
    while (i != last) {
        printf("%3c", cQ->queue[i]);
        i = (i + 1) % cQ_SIZE;
    }
    printf(" ] ");
}
 cs

 

- 예제 : 순차 자료구조를 이용해 원형 큐 구현하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include "cQueueS.h"
 
int main(void) {
    QueueType* cQ = createCQueue();            // 큐 생성
    element data;
    printf("\n ***** 원형 큐 연산 *****\n");
    printf("\n 삽입 A>>"); enCQueue(cQ, 'A'); printCQ(cQ);
    printf("\n 삽입 B>>"); enCQueue(cQ, 'B'); printCQ(cQ);
    printf("\n 삽입 C>>"); enCQueue(cQ, 'C'); printCQ(cQ);
    data = peekCQ(cQ); printf(" peek item : %c \n", data);
    printf("\n 삭제 >>"); data = deCQueue(cQ); printCQ(cQ);
    printf("\t삭제 데이터 : %c", data);
    printf("\n 삭제 >>"); data = deCQueue(cQ); printCQ(cQ);
    printf("\t삭제 데이터 : %c", data);
    printf("\n 삭제 >>"); data = deCQueue(cQ); printCQ(cQ);
    printf("\t삭제 데이터 : %c", data);
    printf("\n 삽입 D>>"); enCQueue(cQ, 'D'); printCQ(cQ);
    printf("\n 삽입 E>>"); enCQueue(cQ, 'E'); printCQ(cQ);
    getchar(); return 0;
}
 cs

 

'자료구조' 카테고리의 다른 글

(C) 자료구조 - 연결 자료구조를 이용한 큐의 구현 (연결 큐)  (3) 2023.10.24
(C) 자료구조 - 큐의 이해 / 순차 큐의 구현  (0) 2023.10.24
(C) 자료구조 - 스택의 응용  (4) 2023.10.23
(C) 자료구조 - 스택의 이해  (6) 2023.10.17
(C) 자료구조 - 연결 리스트의 응용 및 구현  (2) 2023.10.17
'자료구조' Related Articles more