[BaekJoon/백준] 18258 큐 구현 (링 버퍼 기반)

배열을 이용해서 기본적인 큐를 구현하게 되면 요소 이동을 수행하기 때문에 복잡도가 O(n)이 될 수 있다.

따라서, 처리의 복잡도를 모두 O(1)로 만들어주기 위해 링 버퍼 기반의 큐로 구현해야 좋다.

 

링 버퍼 기반의 큐란, 배열의 처음이 끝과 연결되어있다고 보고 설계하는 자료구조다.

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

// 링 버퍼 구조로 큐를 구현
typedef struct {
    int max; //  큐의 용량
    int num; // 현재 데이터 수. front와 rear의 값이 같은 경우 큐가 비어있는지, 가득찼는지 구별할 수 없는 상황을 피하기 위해 사용.
    int front; // 프런트. 첫 번째 요소의 인덱스를 저장
    int rear; // 리어. 맨 나중에 넣은 요소의 하나 뒤의 인덱스를 저장 (다음 인큐 시에 데이터가 저장될 요소의 인덱스를 미리 준비하는 것)
    int *que; // 큐의 첫 요소에 대한 포인터
} IntQueue;

int Initialize(IntQueue *q, int max) {
    q->num = q->front = q->rear = 0; // 모두 0
    if((q->que = calloc(max, sizeof(int))) == NULL) {
        q->max = 0;
        return -1; // 실패
    }
    
    q->max = max;
    return 0; // 성공
}

int Enque(IntQueue *q, int x) {
    
    if(q->num >= q->max) {
        return -1;
    }
    
    q->num++;
    q->que[q->rear++] = x;
    
    q->rear = q->rear % q->max;
    // 그냥 q->rear == q->max 일 때, q->rear = 0 해줘도 됨.
    
    return 0;
    
}

int Deque(IntQueue *q, int *x) {
    
    if(q->num <= 0) {
        *x = -1;
        return -1;
    }
    
    q->num--;
    *x = q->que[q->front++];
    
    q->front = q->front % q->max;
    // 그냥 q->front == q->max 일 때, q->front = 0 해줘도 됨.

    
    return 0;
    
}

int Size(IntQueue *q) {
    return q->num;
}

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

int Front(IntQueue *q) {
    if(q->num == 0)
        return -1;
    
    return q->que[q->front];
}

int Back(IntQueue *q) {
    if(q->num <= 0)
        return -1;
    
    return q->que[q->rear - 1];
}

int N;
char arr[6];

int main() {
    int input;
    IntQueue que;
    
    scanf("%d", &N);
    Initialize(&que, N);
    
    while(N--) {
        
        scanf("%s", arr);
        
        if(!strcmp(arr, "push")) {
            scanf("%d", &input);
            
            Enque(&que, input);
            
        } else if(!strcmp(arr, "pop")) {
            Deque(&que, &input);
            
            printf("%d\n", input);
                
            
        } else if(!strcmp(arr, "size")) {
            
            printf("%d\n", Size(&que));

            
        } else if(!strcmp(arr, "empty")) {
            
            printf("%d\n", IsEmpty(&que));

            
        } else if(!strcmp(arr, "front")) {
            
            printf("%d\n", Front(&que));

            
        } else if(!strcmp(arr, "back")) {
            
            printf("%d\n", Back(&que));
            
        }
    }

}