컴공 일기111

오늘 구현한 것은, 순환 큐라는 자료구조입니다. 스택과는 다르게 양방향이 뚫려있는 구조지요 :) 복잡한 것 같지만, 원리는 간단합니다. 

-CircularQueue.h

#pragma once

#include <stdio.h>

#include <stdlib.h>

typedef struct tagNode

{

    int Data;

}Node;

typedef struct tagCircularQueue

{

    int Capacity;

    int Front;

    int Rear;

    Node* Nodes;

}CircularQueue;

void CQ_CreateQueue( CircularQueue** Queue, int Capacity);

void CQ_DestroyQueue( CircularQueue* Queue);

void CQ_Enqueue( CircularQueue* Queue, int Data);

int  CQ_Dequeue( CircularQueue* Queue);

int  CQ_GetSize( CircularQueue* Queue);

int  CQ_IsEmpty( CircularQueue* Queue);

int  CQ_IsFull(CircularQueue* Queue);

-CircularQueue.c

#include "CircularQueue.h"

void CQ_CreateQueue(CircularQueue** Queue, int Capacity)

{

    (*Queue) = (CircularQueue*)malloc(sizeof(CircularQueue));

    (*Queue)->Nodes = (Node*)malloc(sizeof(Node) * (Capacity+1));

    (*Queue)->Capacity = Capacity;

    (*Queue)->Front = 0;

    (*Queue)->Rear = 0;

}

void CQ_DestroyQueue(CircularQueue* Queue)

{

    free(Queue->Nodes);

    free(Queue);

}

void CQ_Enqueue(CircularQueue* Queue, int Data)

{

    int Position = 0;

    if (Queue->Rear == Queue->Capacity)

    {

        Position = Queue->Rear;

        Queue->Rear = 0;

    }

    else

        Position = Queue->Rear++;

    Queue->Nodes[Position].Data = Data;

}

int CQ_Dequeue(CircularQueue* Queue)

{

    int Position = Queue->Front;

    if (Queue->Front == Queue->Capacity)

    {

        Queue->Front = 0;

    }

    else

        Queue->Front++;

    return Queue->Nodes[Position].Data;

}

int CQ_GetSize(CircularQueue* Queue)

{

    if (Queue->Front <= Queue->Rear)

        return Queue->Rear - Queue->Front;

    else

        return Queue->Rear + (Queue->Capacity - Queue->Front) + 1;

}

int CQ_IsEmpty(CircularQueue* Queue)

{

    return (Queue->Front == Queue->Rear);

}

int CQ_IsFull(CircularQueue* Queue)

{

    if (Queue->Front < Queue->Rear)

        return (Queue->Rear - Queue->Front) == Queue->Capacity;

    else

        return (Queue->Rear + 1) == Queue->Front;

}

-main.c

#include "CircularQueue.h"

int main(void)

{

    int i;

    CircularQueue* Queue;

    CQ_CreateQueue(&Queue, 10);

    CQ_Enqueue(Queue, 1);

    CQ_Enqueue(Queue, 2);

    CQ_Enqueue(Queue, 3);

    CQ_Enqueue(Queue, 4);

    for (i = 0; i < 3; i++)

    {

        printf("Dequeue : %d, ", CQ_Dequeue(Queue));

        printf("Front : %d, Rear : %d\n", Queue->Front, Queue->Rear);

    }

    i = 100;

    while (CQ_IsFull(Queue) == 0)

    {

        CQ_Enqueue(Queue, i++);

    }

    printf("Capacity: %d, Size: %d\n\n", Queue->Capacity, CQ_GetSize(Queue));

    while (CQ_IsEmpty(Queue) == 0)

    {

        printf("Dequeue: %d, ", CQ_Dequeue(Queue));

        printf("Front : %d, Rear : %d\n", Queue->Front, Queue->Rear);

    }

    CQ_DestroyQueue(Queue);

    return 0;

}

[실행결과]

Dequeue : 1, Front : 1, Rear : 4

Dequeue : 2, Front : 2, Rear : 4

Dequeue : 3, Front : 3, Rear : 4

Capacity: 10, Size: 10

Dequeue: 4, Front : 4, Rear : 2

Dequeue: 100, Front : 5, Rear : 2

Dequeue: 101, Front : 6, Rear : 2

Dequeue: 102, Front : 7, Rear : 2

Dequeue: 103, Front : 8, Rear : 2

Dequeue: 104, Front : 9, Rear : 2

Dequeue: 105, Front : 10, Rear : 2

Dequeue: 106, Front : 0, Rear : 2

Dequeue: 107, Front : 1, Rear : 2

Dequeue: 108, Front : 2, Rear : 2