[자료구조][C언어]큐(Queue)란?(2)_큐의 구현(선형큐)

저번 시간에는 큐의 개념과 구조에 대해 간단히 살펴보았었다. 이번시간에는 큐를 구현해 보도록 하자.

 

큐는 배열을 사용하면 쉽게 구현이 가능하다.

큐를 배열로 구현하는 방법에는 크게 두 가지 방법이 있다. 이는 바로 선형큐와 원형큐이다.

 

먼저, 큐의 구조와 필요한 함수 등을 정의하고 선형큐와 원형큐를 차례대로 구현해 보자.

큐의 구현

큐를 구현하기 위해서 데이터를 담을 배열, 큐의 시작과 끝의 위치를 나타내는 front와 rear이 필요하며,

아래의 연산들을 수행하는 함수가 필요하다.

 

isEmpty: 큐(Queue)가 비어있는지 검사

isFull: 큐가 가득 차있는지 검사

Enqueue(삽입): 큐의 삽입방향으로 데이터를 삽입

Dequeue(삭제): 큐의 삭제방향에 있는 데이터 삭제

선형큐의 구조 및 연산

선형큐란 배열을 선형적으로 사용하여 큐를 구현하는 것이다.

큐의 앞과 끝을 나타내기 위해서 front와 rear을 사용한다.

데이터의 삽입은 rear쪽에서, 데이터의 제거는 front쪽에서 일어난다.

선형큐의 구조 및 연산

a) 선형큐 구조체 정의 및 초기화

위 그림과 정의를 바탕으로 선형큐 구조체를 구현하면 다음과 같다.

#include <stdio.h>
#include <stdlib.h>

//큐의 최대 크기
#define SIZE 100

//선형큐 구조체
typedef struct 
{	
    //데이터를 담을 배열
    int data[SIZE]; 
    //큐의 시작과 끝을 가리킬 변수
    int front, rear;
}QueueType;

void init(QueueType *Q)
{   //큐의 front와 rear를 -1로 초기화
    Q->front = Q->rear = -1; 
}

b) isFull, isEmpty

선형큐의 isFull과 isEmpty 연산을 구현하고자 한다.

큐가 비어 있는 경우, 큐가 가득찬 경우 예시

위 그림과 같이 큐가 가득 찬 경우는 rear이 배열의 끝을 가리키게 되며

큐가 비어있는 경우는 front와 rear이 같은 곳을 가리키게 되므로

이를 이용해 아래와 같이 구현가능하다.

int isEmpty(QueueType *Q) 
{
    return Q->front == Q->rear;
    /*
    큐가 비어있는 경우는 
    front와 rear이 같은 곳을 가리킨다.
    */
}

int isFull(QueueType *Q) 
{
    return Q->rear == SIZE-1;
    /*
    큐가 가득 찬 경우는 rear이 
    배열의 끝을 가리킨다.
    */
}

c) enqueue

enqueue연산을 구현하고자 한다.

isFull 연산을 통해 큐가 가득 차있는지 확인 후, 큐가 가득 차있지 않다면 데이터를 삽입한다.(rear 방향으로)

enqueue(3) 동작 방식

enqueue의 동작방식을 그림으로 나타내면 위와 같으며 코드로 다음과 같이 구현된다.

//enqueue는 삽입할 큐와 데이터를 인수로 받는다.
void enqueue(QueueType *Q, char e)
{
    //가득 차있는지 확인
    if(isFull(Q))
        printf("Queue is Full!\n");
    //가득 차있지 않다면
    else
    {
        //큐의 끝부분을 이동
        Q->rear++;
        //데이터 삽입
        Q->data[Q->rear] = e;
        
    }
}

d) dequeue

isEmpty연산을 통해 큐가 비어있지 않다면 데이터를 제거한다.(front 방향의 데이터를 제거)

그리고 제거한 값을 반환한다.

dequeue()동작 방식

char dequeue(QueueType *Q)
{   //큐가 비어 있는지 확인
    if(isEmpty(Q))
    {
        printf("Queue is Empty.\n");
        return 0;
    }
    
    //front 이동
    Q->front++;
    //제거한 값 반환
    return Q->data[Q->front];
}

e) 선형큐의 단점

선형큐는 큰 단점이 몇 가지 있다.

반복적으로 삽입과 삭제를 하다 보면 이런 식으로 배열의 공간이 남아있지만

더 이상 데이터를 삽입을 할 수가 없는 문제가 생긴다.

이를 해결하기 위해서는 배열의 데이터들을 옮겨주거나 원형큐를 사용해야 한다는 단점이 있다.

선형큐의 단점

코드정리

오늘 구현한 선형큐 코드를 정리하자면 아래와 같다. 

#include <stdio.h>
#include <stdlib.h>

//큐의 최대 크기
#define SIZE 100

//선형큐 구조체
typedef struct 
{	
    //데이터를 담을 배열
    int data[SIZE]; 
    //큐의 시작과 끝을 가리킬 변수
    int front, rear;
}QueueType;

void init(QueueType *Q)
{   //큐의 front와 rear를 -1로 초기화
    Q->front = Q->rear = -1; 
}
int isEmpty(QueueType *Q) 
{
    return Q->front == Q->rear;
    /*
    큐가 비어있는 경우는 
    front와 rear이 같은 곳을 가리킨다.
    */
}

int isFull(QueueType *Q) 
{
    return Q->rear == SIZE-1;
    /*
    큐가 가득찬 경우는 rear이 
    배열의 끝을 가리킨다.
    */
}

//enqueue는 삽입할 큐와 데이터를 인수로 받는다.
void enqueue(QueueType *Q, char e)
{
    //가득차있는지 확인
    if(isFull(Q))
        printf("Queue is Full!\n");
    //가득차있지 않다면
    else
    {
        //큐의 끝부분을 이동
        Q->rear++;
        //데이터 삽입
        Q->data[Q->rear] = e;
        
    }
}

char dequeue(QueueType *Q)
{   //큐가 비어있는지 확인
    if(isEmpty(Q))
    {
        printf("Queue is Empty.\n");
        return 0;
    }
    
    //front 이동
    Q->front++;
    //제거한 값 반환
    return Q->data[Q->front];
}

 

다음 시간에는 선형큐의 단점을 해결한 원형큐에 대해 알아보고 구현해 보는 시간을 가지도록 하겠습니다

혹시 더 궁금하거나 잘못된 부분이 있다면 언제든 자유롭게 의견 남겨주시면 감사하겠습니다!

참조

천인국 외 2인 , C언어로 쉽게 풀어쓴 자료구조, 생능출판, 2019