[백준 10845] 큐 (C, C++ Queue)

• 안녕하세요.BlockDMask 입니다.

• 오늘은 영국에 온지 이틀째 되는날입니다.
  제가 원하는 데로 
  저는 영국 런던 리젠트 공원 벤치에 앉아서 문제를 풀어보았습니다.

• 확실히 집중이 안되서; 쉬운 자료구조 문제를 풀어봤습니다.

0. 제목

• 백준 10845 큐

• BOJ 10845 큐

1. 문제설명

큐를 구현하고

각 명령어에 맞게 출력하는 문제입니다.

push X : 정수 X를 큐에 삽입

pop : 큐의 앞에 있는 정수를 없애고, 그 수를 출력합니다. 없는 경우 -1  출력.

size : 큐에 들어있는 원소의 개수 출력.

empty : 큐가 비어있으면 1, 그렇지 않으면 0 을 출력.

front : 큐의 가장 앞에있는 원소 출력, 원소가 없는 경우에는 -1 출력.

back : 큐의 가장 뒤에있는 원소 출력, 원소가 없는 경우에는 -1 출력.

첫째 줄에는 N (1 <= N <= 10000) 이 주어지고

그 수만큼 명령을 받아 들입니다.

출력값은 한줄에 하나씩 출력합니다.

2. 풀이과정

<C 언어를 이용한 큐>

배열 기반의 원형 큐를 구현해서 문제를 풀었습니다.

원형 큐의 특징은

front 와 rear가 있다는 점이고, 

front 와 rear가 배열의 index를 가리키고

같은 index를 가리키는 경우에는 원형 큐가 비어있다고 판단합니다.

rear + 1 이 front 가 가리키는 index 인 경우 원형 큐가 꽉 찼다고 판단합니다.

<C++ 을 이용한 큐>

C++ STL에서 제공하는 queue container 를 이용하여 풀었습니다.

3. 코드

i) C 로 구현

#include<stdio.h>
#include<string.h>
 
#define TRUE 1
#define FALSE 0
 
//배열 기반 원형 큐로 구현하겠습니다.
#define MAX_SIZE 1000
typedef int Data;
 
typedef struct _queue{
    Data arr[MAX_SIZE];
    int front;
    int rear;
    int size;
}Queue;
 
void InitQueue(Queue * pq){
    pq->size =0;
    pq->front = 0;
    pq->rear =0;
}
int getNextIdx(int idx){
    if(idx+1 >= MAX_SIZE) return 0;
    return idx+1;
}
void setNextIdx(int *idx){
    if(*idx +1 >= MAX_SIZE) *idx = 0;
    else (*idx)++;
}
 
int Empty(Queue * pq){
    if(pq->front == pq->rear) return TRUE;
    return FALSE;
}
int Full(Queue *pq){
    if(getNextIdx(pq->rear) == pq->front) return TRUE;
    return FALSE;
}
 
Data Front(Queue *pq){
    if(Empty(pq) == TRUE) return -1;    
    return pq->arr[pq->front];
}
 
Data Back(Queue *pq){
    if(Empty(pq) == TRUE) return -1;
    return pq->arr[pq->rear -1];
}
 
void Push(Queue *pq, Data data){
    if(Full(pq) == TRUE) return;
    pq->arr[pq->rear] = data;
    setNextIdx(&(pq->rear));
    (pq->size)++;
}
 
Data Pop(Queue *pq){
    if(Empty(pq) == TRUE) return -1;
 
    int data = pq->arr[pq->front];
    setNextIdx(&(pq->front));
    (pq->size)--;
    return data;
}
 
 
int main(void){
    int i;
    int N;
    scanf("%d", &N);
    
    char str[6];
 
    Queue q;
    InitQueue(&q);
    Data data;
 
    for(i=0; i<N; i++){
        scanf("%s", str);
        
        if(!strcmp(str, "push")){
            scanf("%d", &data);
            Push(&q, data);
 
        }else if(!strcmp(str, "pop")){
            printf("%d\n", Pop(&q));
 
        }else if(!strcmp(str, "size")){
            printf("%d\n", q.size); 
 
        }else if(!strcmp(str, "empty")){
            printf("%d\n", Empty(&q));
 
        }else if(!strcmp(str, "front")){
            printf("%d\n", Front(&q));
 
        }else if(!strcmp(str, "back")){
            printf("%d\n", Back(&q));
 
        }
 
    }
 
 
 
    return 0;
}
 

ii) C++ 로 구현

#include<iostream>
#include<queue>
#include<string>
 
using namespace std;
 
int main(void){
 
    int N;
    cin >> N;
 
    queue<int> q;
    int num;
 
    for(int i=0; i<N; i++){
        string str;
        cin >> str;
 
        if(str == "push"){
            int data;
            cin >> data;
            q.push(data);
 
        }else if(str == "pop"){
 
            if(q.size() != 0){
                num = q.front();
                q.pop();
            }else{
                num = -1;
            }
            cout << num << endl;
 
        }else if(str == "size"){
            cout << q.size() << endl;
 
        }else if(str == "empty"){
            if(q.size() == 0) num =1;
            else num =0;
            cout << num << endl;
 
        }else if(str == "front"){
            if(q.size() == 0){
                num = -1;
            }else{
                num = q.front();
            }
            cout << num << endl;
 
        }else if(str == "back"){
            if(q.size() == 0){
                num = -1;
            }else{
                num = q.back();
            }
            cout << num << endl;
        }
 
    }
    return 0;
}

4. 인증

i) C 로 구현

ii) C++ 로 구현

메모리와 시간이 차이 남을 볼 수 있습니다.

C++  queue container는 deque container 기반으로 구현되었기 때문에 동적할당을 합니다.

시간이 차이나는이유는 cout과 printf의 차이입니다.

감사합니다.