C언어로 큐(Queue) 구현하기

큐(Queue)

스택은 나중에 들어온 데이터가 먼저 나가는 후입선출(last in, first out)구조였다.

큐는 먼저들어온 데이터가 먼저 나가는 선입선출(first in, first out)구조다.

뒤(rear)에서 데이터가 들어오고, 앞(front)에서 데이터가 하나씩 삭제된다.

Queue의 구조

---

큐를 구현해보자

일단 큐를 구현하기전에 필요한 것을 나열해보면,

 

1. 큐 구조체 정의, 생성

2. full인지 empty인지 확인하는 함수

3. 데이터를 삽입하는 함수

4. 데이터를 삭제하면서 반환하는 함수

5. 큐를 출력하는 함수

---

1. 큐 구조체 정의 생성

#include <stdio.h>
#define MAX_QUEUE 5

typedef int element;
typedef struct {
    int front;
    int rear;
    element data[MAX_QUEUE];
} QueueType;

 

void init_queue(QueueType *q)
{
    q->front = -1;
    q->rear = -1;
}

여기서 중요한 점은, front와 rear가 -1부터 시작한다는 것이다.

데이터를 삽입할 때, rear를 한칸이동 후 데이터 삽입,

데이터를 삭제할 때, front를 한칸이동 후 데이터 삭제

 

 

---

2. full 인지 empty인지 확인하는 함수

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

만약 front와 rear의 위치가 같다면, 그 큐는 비어있는 큐다.

rear에 데이터를 일정 데이터를 삽입 후, front에서 데이터를 빼낸다고 했을 때,

계속 front에서 데이터를 빼내면 rear와 같아질 것임

 

int is_full(QueueType *q)
{
    if(q->rear == MAX_QUEUE - 1)
        return 1;
    else
        return 0;
}

만약 큐의 rear가 큐의 끝에 다다르면, 그 큐는 포화된 큐다.

 

 

---

3. 데이터를 삽입하는 함수

void enqueue(QueueType *q, element item)
{
    if(is_full(q) == 1){
        printf("full\n");
        return;
    }
    else
        q->data[++(q->rear)] = item;
}

큐가 포화상태인지 검사 후, 포화상태가 아니라면

rear를 증가시키고 그 rear위치에 데이터를 삽입한다.

---

4. 데이터를 반환하고 삭제하는 함수

int dequeue(QueueType *q)
{
    if(is_empty(q) == 1){
        printf("empty");
        exit(1);
    }
    else
        return q->data[++(q->front)];
}

큐가 공백상태인지 검사 후, 공백상태가 아니라면

front를 증가시키고 그 값을 가져온다.

 

주의! )

++, --가 뒤에 붙는지 앞에 붙는지 그 이유를 정확히 알아야한다.

---

5. 큐를 출력하는 함수

void print_queue(QueueType *q)
{
    for(int i = 0; i < MAX_QUEUE; i++){
        if(i <= q->front || i > q->rear){
            printf(" | ");
        }
        else
            printf("%d|", q->data[i]);
    }
    printf("\n");
}

 

---

전체 코드)

#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE 5

typedef int element;
typedef struct {
    int front;
    int rear;
    element data[MAX_QUEUE];
} QueueType;

void init_queue(QueueType *q)
{
    q->front = -1;
    q->rear = -1;
}

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

int is_full(QueueType *q)
{
    if(q->rear == MAX_QUEUE - 1)
        return 1;
    else
        return 0;
}

void enqueue(QueueType *q, element item)
{
    if(is_full(q) == 1){
        printf("full\n");
        return;
    }
    else
        q->data[++(q->rear)] = item;
}

int dequeue(QueueType *q)
{
    if(is_empty(q) == 1){
        printf("empty");
        exit(1);
    }
    else
        return q->data[++(q->front)];
}

void print_queue(QueueType *q)
{
    for(int i = 0; i < MAX_QUEUE; i++){
        if(i <= q->front || i > q->rear){
            printf(" | ");
        }
        else
            printf("%d|", q->data[i]);
    }
    printf("\n");
}

int main(void)
{
    int i = 0;
    QueueType q;
    init_queue(&q);

    enqueue(&q, 1);
    print_queue(&q);
    enqueue(&q, 2);
    print_queue(&q);
    enqueue(&q, 3);
    print_queue(&q);

    i = dequeue(&q);
    print_queue(&q);
    i = dequeue(&q);
    print_queue(&q);
    i = dequeue(&q);
    print_queue(&q);

    return 0;
}

---

과정을 살펴보자

int main(void)
{
    int i = 0;
    QueueType q;
    init_queue(&q);

    enqueue(&q, 1);
    print_queue(&q);
    enqueue(&q, 2);
    print_queue(&q);
    enqueue(&q, 3);
    print_queue(&q);

    i = dequeue(&q);
    print_queue(&q);
    i = dequeue(&q);
    print_queue(&q);
    i = dequeue(&q);
    print_queue(&q);

    return 0;
}

이부분이 큐에 데이터를 넣고 빼는 부분이다.

 

초기 상태

 

 

enqueue(&q, 1)

 

 

enqueue(&q, 2)

 

 

enqueue(&q, 3)

 

 

dequeue(&q)

 

 

dequeue(&q)

 

 

dequeue(&q)

 

결과

데이터를 다 빼내면 front와 rear의 위치가 결국 같아진다.

공백상태가 된다.