[스택과 큐] #4. 큐 함수

큐 구조체: IntQueue

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

typedef struct{
    int max; //큐의 용량
    int num; //현재 데이터 개수

    int front; //프런트
    int rear; //리어
    int *que; // 배열 포인터 == 큐의 맨 앞 요소에 대한 포인터
} IntQueue;

max	큐의 최대 용량 저장 멤버. 배열 que에 저장할 수 있는 최대 요소의 개수와 같다.
num	현재 큐에 쌓아놓은 데이터 개수.
front	인큐하는 데이터 가운데 첫 번째 요소의 인덱스.
rear	인큐한 데이터 가운데 맨 나중에 넣은 요소의 하나 뒤 인덱스.
que	인큐하는 데이터를 저장하기 위한 큐

front와 rear의 구별

프런트와 리어

front와 rear의 상태가 비어 있는지, 가득 차 있는지 구분할 수 없는 경우에는 front와 rear의 값이 같은데, 이처럼 두 값이 같다면 두 상태를 구분할 수 없다. 따라서 현재 큐에 쌓아놓은 데이터 개수를 구분하기 위해 추가적인 num이라는 멤버가 존재해야한다.

front	다음 디큐 시 삭제되는 인덱스
rear	가장 최근에 인큐하 인덱스

큐 초기화: Initialisze

Initialisze 함수는 큐의 메모리 공간을 확보하는 등의 작업을 수행한다.

• 큐를 처음 만들때 큐는 비어있으므로 num,front,rear의 값을 모두 0으로 만든다.
• 매개변수 max로 받은 큐의 최대 용량 만큼  배열 que을 동적할당한다.

int Initialize(IntQueue *Que,int max){
    Que->num = Que->front = Que->rear = 0;
    //큐의 변수 초기화
    /**
    현재 데이터 개수, 프런트, 리어를 모두 0으로 저장
    대입은 <- 순으로 0 저장됨.
     */
    Que->que = (int*) malloc(sizeof(int)*max);
    //큐에 사용할 배열을 동적할당: 인자로 받은 큐의 용량만큼 동적할당
    if(Que->que == NULL){
        //동적할당 실패 시 용량 0 초기화 및 종료
        Que->max = 0;
        return - 1;
    }
    //동적할당 성공 시
    Que-> max = max;
    //큐의 '공식' 용량을 업데이트
    return 0;
}

인큐 함수 Enque

Enque 함수는 큐에 데이터를 인큐하는 함수이다.

인큐 성공	현재 데이터 개수를 증가.  입력받은 데이터를 배열 추가 후 rear(후미 인덱스)을 증가시킴. 0 반환
인큐 실패	-1 반환

 

이때 주의할 점은, 인큐 과정에서 rear값과 max값이 같아지는 경우이다.

rear값과 max값이 같아지면 실제 배열에 없는 공간을 가리키기 때문에 오류가 발생하게된다.

 

이러한 오류를 방지하기 위하여 다음과 같은 조건문을 이용하여 rear값과 max값이 같아지는 경우를 방지한다.

if(Que->rear == Que ->max) Que->rear = 0;

rear값을 1만큼 증가할때 큐의 최대 용량의 값인 max와 같아질 경우 rear의 값을 배열의 처음인 0으로 변경한다.

int EnQue(IntQueue *Que,int data){
    if(Que->num >= Que->max) return -1;
    else{
        /**
        큐의 현재 데이터 개수가 큐의 최대 용량보다 큰 경우 -1 반환 후 종료
        >> 현재 데이터 개수가 최대 용량보다 크거나 작으면 더 이상 데이터 추가할 수 없음.
        */
        Que ->num ++;
        //큐의 현재 데이터 개수 증가
        Que->que[Que->rear ++] = data;
        if(Que->rear == Que ->max) Que->rear = 0;
        /**
        큐가 가리키는 현재 인덱스에 데이터를 추가하고 
        rear(후미 인덱스) 값을 증가한다.
        */
    }
    return 0;
}

디큐 함수 Deque

Deque 함수는 큐에서 데이터를 디큐하는 함수이다.

디큐 성공	0 반환
디큐 실패	-1 반환

디큐도 인큐와 마찬가지로 인덱스 초과 문제가 발생한다.

디큐하기전의 front값이 배열의 끝이라면 front의 값은 max가 되어 배열 마지막 요소의 인덱스를 초과하게된다.

 

이러한 오류를 방지하기 위해 다음 조건문을 이용하여 front와 max의 값이 같아지는 경우를 방지한다.

if(Que->front == Que->max) Que->front = 0;

int DeQue(IntQueue *Que,int *data){
    if(Que->num <=0) return -1;
    /**
    큐의 현재 데이터 개수가 0과 같거나 작으면 -1 반환 후 종료
    >> 현재 데이터 개수가 없으면 데이터를 디큐 할 수 없음
     */
    Que->num --;
    //현재 데이터 개수를 1 감소
    *data = Que->que[Que->front++];
    //인자로 받은 data에 현재 인덱스의 값을 저장하고 front를 증가 == 현재 인덱스 데이터를 빼냈기 때문
    
    if(Que->front == Que->max) Que->front = 0;
    /**
    만약 큐의 front가 큐의 최대 용량보다 같은 경우
    >>예를 들어 최대 용량이 10(0~9)인 큐에서 디큐를 9인덱스에서 하게되면 인덱스가 10으로 초과한다.
      따라서 front값을 맞춰주기 위해 이 조건문을 사용한다.
     */
    return 0;
}

피크 함수 Peek

Peek 함수는 큐의 꼭대기의 데이터를 확인하는 함수로, que[front]의 값을 출력한다.

피크 성공	0 반환
피크 실패	-1 반환

int Peek(IntQueue *Que,int *data){
    if(Que->num <= 0 ) return -1;
    /**
    큐의 현재 데이터 개수가 0과 같거나 작으면 -1 반환 후 종료
    >> 현재 데이터 개수가 없으면 데이터를 피크 할 수 없음
     */
    *data = Que->que[Que->front];
    //맨 앞의 데이터 == 디큐에서 꺼낼 데이터를 저장
    return 0;
}

초기화 함수 Clear

clear 함수는 인자로 받은 큐에 쌓여 있는 모든 데이터를 삭제한다.

void Clear(IntQueue *Que){Que->num = Que->front = Que->rear = 0;}
//모든 큐의 인덱스를 초기화하여 접근을 제거

최대 용량 확인 함수 Capacity

Capacity 함수는 큐의 용량(max)을 확인하고 max의 값을 반환한다.

int Capacity(IntQueue *Que){return Que->max;}
//큐의 최대 용량 반환

데이터의 개수 확인 함수 Size

Size 함수는 현재 큐에 저장된 데이터의 개수(num)를 반환한다.

int Size(IntQueue *Que){return Que->num;}
//큐의 현재 데이터 개수 반환

저장 상태 확인 함수 IsEmpty

IsEmpty 함수는 큐가 비어있는지 검사하는 함수이다. 

큐가 비어있는 경우	1 반환
큐가 차 있는 경우	0 반환

int IsEmpty(IntQueue *Que){return Que->num <=0;}

큐의 과저장 유무 확인 함수 IsFull 

IsFull 함수는 큐가 가득 찼는지 검사하는 함수이다.

큐가 가득 차 있는 경우	1 반환
큐가 가득 차 있지 않은 경우	0 반환

int IsFull(IntQueue *Que){return Que->num >= Que->max;}

데이터를 검색하는 함수 Search

search 함수는 큐의 배열에서 data와 같은 데이터가 저장되있는 인덱스를 반환하는 함수이다.

검색 성공	요소의 인덱스 반환
검색 실패	0 반환

큐는 링버퍼를 사용하므로 현재 검색하는 위치의 인덱스를 구하는 방식은 (i+Que->front)%Que->max)를 사용한다.

int Search(IntQueue *Que,int data){
    int idx;
    for(int i=0;i<Que->num;i++){//현재 데이터 개수 만큼 반복
        if(Que->que[idx = (i + Que->front)%Que->max] == data) return idx;
        /**
        큐가 가리키는 배열의 인덱스를 증가하면 인자로 받은 값과 확인.
        (i + Que->front)%Que와 같이 나머지 연산을 사용하는 이유는 front가 0~9일 수 있지만
        3~9~2일 수 도 있기 때문!

        이때 값을 찾은 인덱스를 반환
         */
    }
    return - 1;
}

데이터 출력 함수 Print

void Print(IntQueue *Que){
    for(int i=0;i<Que->num;i++) printf("%d ",Que->que[(i + Que->front)%Que->max]);
    // Search와 같은 로직으로 모든 데이터 출력
}

큐 종료 함수 Terminate

Terminate 함수는 큐를 해제하고 스택의 용량과 데이터 개수를 0으로 초기화한다.

void Terminate(IntQueue *Que){
    if(Que->que != NULL) free(Que->que);//큐의 배열이 할당되있으면(메모리 공간이 차있으면) 메모리 공간 해제
    Que->max = Que->num = Que->front = Que->rear = 0;
    //큐의 매개변수를 초기화
}