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

저번 시간에는 큐를 배열로 구현하는 방법 중에서 배열을 선형적으로 활용하여 만드는 선형큐에 대해 알아보고

구현해 보는 시간을 가졌었다. 이번에는 선형큐의 단점을 해결한 원형큐를 살펴보도록 하자.

원형큐

원형 큐란 배열을 원형으로 사용해 처음과 끝이 만나도록 큐를 구현하는 것이다.

선형 큐와 마찬가지로 front, rear 이 필요하며 isEmpty, isFull, enqueue, dequeue 연산을 수행하는 함수들이 필요하다.

 

front	큐의 첫 번째 부분 하나 앞의 인덱스를 가리킴
rear	큐의 마지막 부분의 인덱스를 가리킴
isEmpty	큐(Queue)가 비어있는지 검사
isFull	큐가 가득 차있는지 검사
Enqueue(삽입)	큐의 삽입방향(rear방향)으로 데이터를 삽입
Dequeue(삭제)	큐의 삭제방향(front방향)에 있는 데이터 삭제

 

글만으로 이해하기 어렵다면 원형큐의 구조와 연산을 그림으로 나타내면 아래와 같다.

원형큐의 구조와 연산

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

원형큐의 초기상태

front: 큐의 첫 번째 데이터 하나 앞의 인덱스 지칭

rear: 큐의 마지막 데이터의 인덱스를 지칭

 

front와 rear, 그리고 들어갈 배열을 위의 정의와 그림을 참고하여 구현하면 아래와 같다.

 

#include <stdio.h>
#include <stdlib.h>
#define SIZE 10

typedef struct
{
    char data[SIZE];
    int front, rear;
}QueueType;

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

b) isFull, isEmpty

비어 있는 큐와 가득 찬 큐 예시

위의 front, rear의 정의를 토대로 비어 있는 상태와 가득 찬상태를 나타내면 위 그림과 같이 나타낼 수 있다.

 

원형큐가 비어있는 상태는 front와 rear이 같은 경우로 정의가 가능하며

가득 찬 상태는 ((rear+1) % (배열의 크기))와 front가 같은 경우로 정의가 가능하다.

 

 

가득찬 큐의 정의

가득 찬 상태를 왼쪽과 같이 하나를 띄워놓도록 정의하는 이유는 바로 배열 전체를 사용하게 된다면 아래와 같이 원형큐는 front와 rear만으론 공백상태와 가득 찬 상태를 구별 못하게 되기 때문이다.

 

위 내용들을 코드로 정리하면 다음과 같다.

 

int isEmpty(QueueType *Q)
{
    return Q->front == Q->rear;
}

int isFull(QueueType *Q)
{
    return Q->front == (Q->rear + 1) % SIZE;
}

c) enqueue

원형큐의 enqueue 연산은 선형큐와 마찬가지로 큐가 가득 차 있는지 확인 후, 가득 차있지 않다면 rear의 값을 +1 하고 rear부분에 값을 삽입한다.

단, 원형 큐에서는 배열을 순환적으로 사용하므로 rear의 값을 (rear+1)% 배열의 크기 로 해주어야 한다는 차이가 있다.

원형큐의 enqueue() 과정

코드로 정리하면 다음과 같다

 

void enqueue(QueueType *Q, char e)
{
    if(isFull(Q))//큐가 가득 차있는지 확인
        printf("Queue is Full!\n");
    else //가득 차있지 않다면
    {
        Q->rear = (Q->rear + 1) % SIZE; //rear 이동
        Q->data[Q->rear] = e; //데이터 삽입
    }
}

d) dequeue

원형큐의 dequeue 연산 또한 선형큐와 마찬가지로 큐가 비어있는지 확인 후, 가득 차있지 않다면 front의 값을 +1 해주고

front 부분의 값을 삭제한다. 그와 동시에 삭제한 값을 반환한다.

단, 원형 큐에서는 배열을 순환적으로 사용하므로 front의 값을 (front+1)% 배열의 크기 로 해주어야 한다는 차이가 있다.

원형큐의 dequeue() 과정

코드로 나타내면 이렇게 된다

 

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

코드정리

오늘 구현한 원형 큐 코드를 한 번에 정리하면 다음과 같다

 

#include <stdio.h>
#include <stdlib.h>
#define SIZE 10

typedef struct
{
    char data[SIZE];
    int front, rear;
}QueueType;

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

int isEmpty(QueueType *Q)
{
    return Q->front == Q->rear;
}

int isFull(QueueType *Q)
{
    return Q->front == (Q->rear + 1) % SIZE;
}

void enqueue(QueueType *Q, char e)
{
    if(isFull(Q))//큐가 가득 차있는지 확인
        printf("Queue is Full!\n");
    else //가득 차있지 않다면
    {
        Q->rear = (Q->rear + 1) % SIZE; //rear 이동
        Q->data[Q->rear] = e; //데이터 삽입
    }
}

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

 

다음 시간에는 큐를 활용한 예시를 가져와 다뤄보는 시간을 가지도록 하겠습니다
혹시 더 궁금하거나 잘못된 부분이 있다면 언제든 자유롭게 의견 남겨주시면 감사하겠습니다!

참조

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