[BaekJoon/백준] 10845번 C++

 

큐를 직접 구현해보는 문제.

 

링버퍼 기반의 큐로 구현해주었다. 큐는 링버퍼기반으로 구현해주어야 작업의 시간복잡도가 감소한다.

#include <cstdio>
#include <iostream>
#include <cstring>



using namespace std;

typedef struct {
    int *que;
    int front;
    int rear;
    int num;
    int max;
} IntQueue;

int Initialize(IntQueue *q, int s) {

    q->que = (int *)calloc(s, sizeof(int));
    q->front = q->rear = q->num = 0;
    q->max = s;
    return 0;
}

int push(IntQueue *q, int x) {

    if(q->max <= q->num)
        return -1;

    q->num++;
    q->que[q->rear++] = x;

    q->rear = q->rear % q->max;
    return 0;
}

int pop(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;
    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 main() {

    int N;
    char input[6];
    int sub;

    IntQueue q;

    scanf("%d", &N);
    Initialize(&q, N);

    while(N--) {

        scanf("%s", input);

        if(strcmp(input, "push") == 0) {
            scanf("%d", &sub);
            push(&q, sub);
        }
        else if(strcmp(input, "pop") == 0) {
            pop(&q, &sub);
            printf("%d\n", sub);
        }
        else if(strcmp(input, "size") == 0) {
            printf("%d\n", size(&q));
        }
        else if(strcmp(input, "empty") == 0) {
            printf("%d\n", isEmpty(&q));
        }
        else if(strcmp(input, "front") == 0) {
            printf("%d\n", front(&q));
        }
        else if(strcmp(input, "back") == 0) {
            printf("%d\n", back(&q));

        }


    }

}

말만 C++이지 C코드와 똑같이 구현했다.

 

 

C++의 STL 중 <queue> 를 사용하면 queue 자료구조를 사용할 수 있다고 한다.

이를 사용해봤다.

#include <iostream>
#include <cstdio>
#include <queue>
#include <string>

using namespace std;

int main() {
    
    int T, temp;
    string s;
    queue<int> q;
    
    scanf("%d", &T);

    while(T--) {
        cin >> s; //string은 cin만 먹힌다고 한다.
        
        //switch를 사용하려 했으나, C++에서는 switch인자로 정수타입만 허용한다고 한다.
        
        if(s == "push") {
            scanf("%d", &temp);
            q.push(temp);
        } else if(s == "pop") {
            if(!q.empty()) {
                printf("%d\n", q.front());
                q.pop();
            } else
                printf("-1\n");
        } else if(s == "empty") {
            printf("%d\n", q.empty());
        } else if(s == "size") {
            printf("%d\n", q.size());
        } else if(s == "front") {
            if(!q.empty()) {
                printf("%d\n", q.front());
            } else
                printf("-1\n");
        } else if(s == "back") {
            if(!q.empty()) {
                printf("%d\n", q.back());
            } else
                printf("-1\n");
        }
    }
}

코드는 짧아졌는데, 링버퍼 기반의 큐가 아닌건지, 아니면 cin 탓인지 시간이 월등히 차이났다.

위 : STL, 아래 : 직접구현

 

참고 : ldgeao99.tistory.com/254