[자료구조] 배열 기반 큐(Queue) 구현 - C

큐(Queue) 

• 선입선출(FIFO, First in Finst out)의 구조이다.
• 일상생활에서 많이 사용되는 자료구조이다.
• 대기번호처럼 순서대로 출력과 입력이 이루어진다.

변수로는 front, rear를 사용한다.

두 변수의 초기값은 -1이며, Enqueue(삽입)은 rear에서, Dequeue(삭제)는 front에서 이루어진다.

 

 

배열을 사용한 큐

배열을 사용하면 공간의 크기가 정적이다.

이러한 점을 보완하기 위해 원형 배열을 사용한다.

 

 

 

 

 

isEmpty()

• front와 rear가 같은 값이라면 그 큐는 비어있는 상태이다.

int isEmptyQ()
{
    if (front == rear)
        return 1;
    else
        return 0;
}

 

 

isFull()

• front가 rear의 바로 다음 칸에 존재한다면 이 큐는 가득 찬 상태이다.

int isFullQ()
{
    if (front == (rear + 1) % SIZE)
        return 1;
    else
        return 0;
}

 

 

 

Enqueue(int val)

• isFull()을 확인하여 가득 찬 경우에는 종료한다.
• 가득 차있지 않은 경우에는 rear의 위치를 한칸 옮기고, 해당 위치에 값을 넣는다.

void Enqueue(int val)
{
    if (isFullQ())
    {
        printf("큐가 가득 차있습니다. \n");
        return;
    }
    else
    {
        rear = (rear + 1) % SIZE;
        queue[rear] = val;
    }
}

 

 

 

Dequeue()

• isEmpty()를 사용하여 빈 경우에는 종료한다.
• 비어있지 않은 경우에는 queue[front] 에 해당하는 값을 반환한다.

int Dequeue()
{
    if (isEmptyQ())
    {
        printf("큐가 비어있습니다.\n");
        return -1;
    }
    else
    {
        int temp = 0;
        front = (front + 1) % SIZE;
        temp = queue[front];
        queue[front] = 0;
        return temp;
    }
}

 

 

전체 코드와 함께 실행 결과를 첨부한다.

 

참고로 큐 배열은 전역 변수로 선언하였다.

 

전체 코드

#include <stdio.h>
#define SIZE 10
int queue[SIZE];
int front = -1;
int rear = -1;

int isEmptyQ()
{
    if (front == rear)
        return 1;
    else
        return 0;
}

int isFullQ()
{
    if (front == (rear + 1) % SIZE)
        return 1;
    else
        return 0;
}

void Enqueue(int val)
{
    if (isFullQ())
    {
        printf("큐가 가득 차있습니다. \n");
        return;
    }
    else
    {
        rear = (rear + 1) % SIZE;
        queue[rear] = val;
    }
}

int Dequeue()
{
    if (isEmptyQ())
    {
        printf("큐가 비어있습니다.\n");
        return -1;
    }
    else
    {
        int temp = 0;
        front = (front + 1) % SIZE;
        temp = queue[front];
        queue[front] = 0;
        return temp;
    }
}

void printQueue()
{
    for (int i = 0; i < SIZE; i++)
    {
        printf("%d ", queue[i]);
    }
    printf("\n");
}

int main(void)
{
    Enqueue(1);
    Enqueue(2);
    Enqueue(3);
    Enqueue(4);
    Enqueue(5);
    printQueue();
    printf("Dequeue : %d\n", Dequeue());
    printf("Dequeue : %d\n", Dequeue());
    printf("Dequeue : %d\n", Dequeue());
    printQueue();

    return 0;
}

 

 

실행 결과