배열로 구현한 큐

선형 큐

큐는 삽입, 삭제에 관련해서 각각 rear, front 두가지 변수를 사용한다.

front 는 큐의 첫 번째 요소 앞을 가리키고 rear 는 큐의 마지막 요소를 가리킨다.

배열로 구현된 선형 큐는 front 와 rear 의 값이 계속 증가만 하기 때문에 언젠가는 끝에 도달하게 되고 배열의 앞이 비어있더라도 사용하지 못하게 된다. 따라서 주기적으로 모든 요소들을 왼쪽으로 이동시켜야 하지만 이는 상당히 오랜 시간이 걸리고 프로그램 코딩 또한 복잡하게 된다.

원형 큐

이러한 선형 큐의 문제점은 큐를 원형으로 생각하면 쉽게 해결된다. 배열의 끝에 도달하면 다음에 증가되는 값을 배열의 처음인 0이 되도록 하는 것이다.

선형 큐에서 front 는 비어있는 경우 인덱스 값이 -1 였지만 원형 큐에서는 0 이다.

원형 큐에서는 포화상태를 구분하기 위해 한 자리를 비워두거나 추가적인 변수 count 를 둔다.

C

소스코드

#include <stdio.h>
#define MAX_QUEUE_SIZE 100

typedef int element;
typedef struct {
    element queue[MAX_QUEUE_SIZE];
    int rear, front;
} QueueType;

void init(QueueType* q) {
    q->rear = 0;
    q->front = 0;
}

int is_empty(QueueType* q) {
    return q->rear == q->front;
}

int is_full(QueueType* q) {
    return (q->rear + 1) % MAX_QUEUE_SIZE == q->front;
}

void enqueue(QueueType* q, element e) {
    if (is_full(q)) {
        printf("큐 포화 에러");
    }
    else {
        q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
        q->queue[q->rear] = e;
    }
}

element dequeue(QueueType* q) {
    if (is_empty(q)) {
        printf("큐 공백 에러");
    }
    else {
        q->front = (q->front + 1) % MAX_QUEUE_SIZE;
        return q->queue[q->front];
    }
}

int main() {
    QueueType q; // create queue
    init(&q);
    printf("rear=%d front=%d\n", q.rear, q.front);
    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);
    printf("dequeue()=%d\n", dequeue(&q));
    printf("dequeue()=%d\n", dequeue(&q));
    printf("rear=%d front=%d\n", q.rear, q.front);

    return 0;
}

출력

rear=0 front=0
dequeue()=1
dequeue()=2
rear=3 front=2