자료구조 CircularQueue

/*
중위 표기법 후위 표기법
1+3 1 3 +
23/7+12 23 7 / 12 +
(117.32+83)*49 117.32 83 + 49 *
1-3*2 1 3 2 * -
*/

//Enqueue - 삽입
//Dequeue

//CircularQueue.h 헤더파일 작성하기

#ifndef CIRCULAR_QUEUE_H

#define CIRCULAR_QUEUE_H

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

typedef int ElementType;

typedef struct tagNode {
        int data;
}Node;

typedef struct tagCircularQueue {
        int Capacity; //용량
        int Front; //전단의 인덱스
        int Rear; // 후단의 인덱스
        Node* Nodes; // 노드 배열
}CircularQueue;

void CreateQueue(CircularQueue** Queue, int Capacity);
void DestroyQueue(CircularQueue* Queue);
void Enqueue(CircularQueue* Queue, ElementType data);
ElementType Dequeue(CircularQueue* Queue);
int GetSize(CircularQueue* Queue);
int IsEmpty(CircularQueue* Queue);
int IsFull(CircularQueue* Queue);

#endif

=================================================

#include "Circular_Queue.h"

void CreateQueue(CircularQueue** Queue, int Capacity) {
        //큐를 자유저장소에 생성
        (*Queue) = (CircularQueue*)malloc(sizeof(CircularQueue));

        //입력된 Capacity+1만큼의 노드를 자유저장소에 생성
        (*Queue)->Nodes = (Node*)malloc(sizeof(Node)*(Capacity+1));

        //초기화
        (*Queue)->Capacity = Capacity;
        (*Queue)->Front = 0;
        (*Queue)->Rear = 0;
}

void DestroyQueue(CircularQueue* Queue) {
        //노드를 자유 저장소에서 해제
        free(Queue->Nodes);
        //큐를 자유 저장소에서 해제
        free(Queue);
}

void 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 Dequeue(CircularQueue* Queue){
        int Position = Queue->Front;
        if (Queue->Front == Queue->Capacity) {
                Queue->Front = 0;
        }else
                Queue->Front++;
        return Queue->Nodes[Position].data;
}

int GetSize(CircularQueue* Queue) {
        if (Queue->Front <= Queue->Rear)
                return Queue->Rear - Queue->Front;
        else return Queue->Rear + (Queue->Capacity - Queue->Front) + 1;
}

int IsEmpty(CircularQueue* Queue){
        return Queue->Front == Queue->Rear);
}

int IsFull(CircularQueue* Queue){
        if (Queue->Front < Queue->Rear) {
                return (Queue->Rear - Queue->Front ) == Queue->capacity;
        } else {
                return (Queue->Rear + 1) == Queue-> Front;
}

void main() {
        CircularQueue* Queue;

        int i;
        CreateQueue(&Queue, 10);

        Enqueue(Queue, 1);
        Enqueue(Queue, 2);
        Enqueue(Queue, 3);
        Enqueue(Queue, 4);

        for (i = 0; i < 3; i++) {
                printf("Dequeue : %d, ", Dequeue(Queue));
                printf("Front : %d, Rear : %d\n", Queue->Front, Queue->Rear);
        }

        i = 100;
        while (IsFull(Queue) == 0) {
                Enqueue(Queue, i++);
        }

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

        while (IsEmpty(Queue) == 0)
        {
                printf("Dequeue : %d, ", Dequeue(Queue));
                printf("Front : %d, Rear : %d\n", Queue->Front, Queue->Rear);
        }
        DestroyQueue(Queue);
}


=======================================================================

//출력값