[자료구조]개선된 원형 큐의 구현

배열기반의 큐는 대부분 원형 큐를 의미한다고 봐도 무리가 아니다.
코드는 그저 F와 R이 배열의 끝에 도달했을 떄 앞으로 이동 시키는 것이 전부이다.

CircularQueue.h

//
//  CircularQueue.h
//  Queue
//
//  Created by 서희찬 on 2021/04/04.
//

#ifndef CircularQueue_h
#define CircularQueue_h

#define TRUE 1
#define FALSE 0

#define QUE_LEN 100
typedef int Data;

typedef struct _cQueue
{
    int fornt; // f
    int rear; // r
    Data queArr[QUE_LEN];
}CQueue;

typedef CQueue Queue;

void QueueInit(Queue*pq); //초기화
int QIsEmpty(Queue*pq); //비었는지 체크
 
void EnQueue(Queue*pq,Data data); // 삽입
Data deQueue(Queue * pq); //삭제
Data QPeek(Queue * pq); // 확인
 
#endif /* CircularQueue_h */

헤더 파일을 통해서 함수들을 정의해주었다.

CircularQueue.c

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

void QueueInit(Queue * pq) // 텅 빈 경우 front와 rear은 동일 위치 가리킴
{
    pq->fornt = 0;
    pq->rear = 0;
}

int QIsEmpty(Queue * pq)
{
    if(pq->fornt == pq->rear) //큐가 텅 비었을 때
        return TRUE;
    else
        return FALSE;
}

int NextPosIdx(int pos) // 핵심 함수 ! 회전을 돕는 함수이다.
{
    if(pos==QUE_LEN-1) //배열의 마지막 요소의 인덱스 값이라면
        return 0; // 0을 반환한다
    else
        return pos+1; //아니면 그냥 다음 인덱스 값을 전달해준다
}

void Enqueue(Queue * pq, Data data)
{
    if(NextPosIdx(pq->rear) == pq->fornt) //큐가 꽉 찼다면
    {
        printf("Queue Memory Error!");
        exit(-1);
    }
    pq->rear = NextPosIdx(pq->rear); // rear 한 칸 이동
    pq->queArr[pq->rear] = data; // rear 이 가리키는 곳에 데이터 저장
}

Data Dequeue(Queue * pq)
{
    if(QIsEmpty(pq))
    {
        printf("Queue Memory Error!");
        exit(-1);
    }
    pq->fornt = NextPosIdx(pq->fornt); //fornt 1칸 이동
    return pq->queArr[pq->fornt]; //front가 가리키는 데이터 반환
}

Data Qpeek(Queue * pq)
{
    if(QIsEmpty(pq))
    {
        printf("Queue Memory Error!");
        exit(-1);
    }
    return pq->queArr[NextPosIdx(pq->fornt)]; //맨 앞 데이터 알려주기 front = 비었으니 인덱스 알려준다 
}

이 중 nextPosIdx 함수가 이 원형 큐의 핵심이 되는 함수라고 볼 수 있다.
그 이유는 큐의 다음 위치에 해당하는 배열의 인덱스 값을 반환하는데, 큐의 길이보다 하나 작은 값이 인자로 전달되면 0을 반호나하고 이는 배열이 끝에 도달했으므로, 앞으로 이동해야함을 의미 하기 때문이다.
즉, F와 R의 회전을 돕는 함수이다.

Main.c

int main(void){
    
    // Queue의 생성 및 초기화 //
    Queue q;
    QueueInit(&q);
    
    // 데이터 넣기 //
    Enqueue(&q, 1); Enqueue(&q, 2);
    Enqueue(&q, 3); Enqueue(&q, 4);
    Enqueue(&q, 5);
    
    // 데이터 빼기 //
    while(!QIsEmpty(&q)) // True 일떄 == 안비어져 있을때까지 와일문 실행
        printf("%d ", Dequeue(&q));
    
    return 0;
}```

이를 통해서 연산의 결과를 눈으로 볼 수 있다. 

이로써 원형 큐에 대한 설명은 끝 !!

흐.. 힘들다 하지만, 이는 배열기반으로 설명한 것...

이제 연결 리스트 기반구현으로 슝,,,,,