[BaekJoon/백준] 2164번 큐 활용

문제에서 '나 큐야' 라고 알려준다!

 

일반 선형배열 큐보다 성능이 좋은

링 버퍼 기반의 큐를 통해 문제를 풀었다.

 

문제에서 주어진대로 Enque와 Deque 작업을 해주면 된다!

#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);
    
    for(int i = 1; i <= N; i++) {
        
        Enque(&que, i);
        
    }
    
    input = Front(&que);
    while(que.num != 1) {
        Deque(&que, &input);
        Deque(&que, &input);
        Enque(&que, input);
    }
    
    printf("%d", input);
}