원형 큐의 추상 자료형

---

원형 큐의 경우 또한 스택과 비슷한 추상 자료형을 갖는다. 기본적으로 큐에 자료를 추가하고 자료를 빼내는 연산이 필요하며, 큐가 가득 찼는지, 아니면 비어 있는지를 확인할 수 있는 연산 또한 필요하다.

이를 바탕으로 원형 큐에 대한 추상 자료형을 정리하면 아래와 같다.

ADT Queue
    자료 : 순서를 가지고 저장되어 있는 n개의 요소
    연산 :
    	Q ∈ Queue; E ∈ Element;
    	- create() ::= 공백 큐를 생성하는 연산
        - isEmpty(Q) ::= 큐가 비어있는지 검사하는 연산
        - isFull(Q) ::= 큐가 가득 찼는지 검사하는 연산
        - enQueue(Q, E) ::= 큐의 맨 위에 요소 E를 삭제하는 연산
        - deQueue(Q) ::= 큐의 제일 아래에 있는 요소 E를 삭제하는 연산
END Queue

이번에도, 원형 큐를 실제로 구현하기 이전에, enQueue(Q, E) 연산과 deQueue(Q) 연산의 알고리즘을 정리해보자.

enQueue 알고리즘

---

삽입 연산인 enQueue의 알고리즘을 정리하면 아래와 같다.

enQueue(Q, E)
    if isFull(Q) then overflow;
    else{
    	rear ← (rear + 1) mod QueueSize;
        Q[rear] ← E
    }
End enQueue()

이는 원형 큐가 가득 찼는지 검사하고 원형 큐가 가득 차지 않았으면 원소를 삽입하고 원형 큐가 가득 찼으면 오버플로우를 반환하는 알고리즘이다.

deQueue 알고리즘

---

삭제 연산인 deQueue의 알고리즘은 아래와 같다.

deQueue(Q)
    if isEmpty(Q) then underflow;
    else {
        front ← (front + 1) mod QueueSize
        return Q[front]
    }
end deQueue()

이는 큐가 비었을 경우 underflow를 반환하고 아닐 경우 가장 아래에 있는 원소를 반환하는 알고리즘이다.

원형 큐의 구현

---

아래는 C언어로 구현한 원형 큐이다.

큐의 크기는 5로 설정하고 A, B, C, D, E, F 문자를 입력 후 출력하는 과정을 수행하도록 지정하였다.

// 원형 큐의 구현

#include <stdio.h>

#define queueSize 5
#define arraySize 6

char queue[arraySize];
int front = 0;
int rear = 0;

int isEmpty() {
    return (front == rear ? 1 : 0);
}

int isFull() {
    return ((rear + 1) % arraySize == front ? 1 : 0);
}

void enQueue(char element) {
    if (isFull() == 1) {
        printf("Overflow!\n");
    }
    else {
        rear = (rear + 1) % arraySize;
        queue[rear] = element;
        printf("rear : %d, front : %d\n", rear, front);
    }
}

char deQueue() {
    if (isEmpty() == 1) {
        printf("Underflow!\n");
    }
    else {
        front = (front + 1) % arraySize;
        printf("rear : %d, front : %d\n", rear, front);
        return queue[front];
    }
}

int main() {
    enQueue('A');
    enQueue('B');
    enQueue('C');
    enQueue('D');
    enQueue('E');
    enQueue('F');
    printf("%c\n", deQueue());
    printf("%c\n", deQueue());
    printf("%c\n", deQueue());
    printf("%c\n", deQueue());
    printf("%c\n", deQueue());
    deQueue();
    return 0;
}

해당 코드는 https://github.com/suitepotato/velog_circular_queue_01/blob/master/circular_queue_01.c 에서도 보실 수 있습니다.

참고

---

정관용, 임종범, 박병기, 복대원. (2013). 고등학교 정보과학 (pp. 201-203). 서울: (주)현대아트컴.