18258: 큐 2

18258번: 큐 2(BOJ C/C++)

사용 언어: C

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

 

풀이

이 문제를 처음풀때 보자마자... 음 연결리스트로 풀면 시간 초과 문제가 안 뜨지 않을까? 해서 그렇게 풀었는데 예상치 못한 부분에서 문제가 터졌었다.

int pop(Queue *queue)
{
    int re = -1;
    if (empty(queue))
        return re;
	
    Node *now = queue->front;
    re = now->data;
    queue->front = now->next;
    free(now);
    return re;
}

위 pop()함수 안의 코드로 정의를 하고 백준에 답을 냈더니 Double Free 에러가 떴다. 이 에러는 딱 봐도 free(now)에서 일어나는 것 같은데 이유를 잘 모르겠어서.. 풀이에서 free(now) 자체를 없애버렸는데 코드가 돌아갔다. 어느 부분에서 Free가 중복되는 건지 잘 모르겠어서 넘어갔지만 궁금하다.. 

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

typedef struct Node
{
    int data;
    struct Node *next;
}Node;
 
typedef struct Queue
{
    Node *front;
    Node *rear;
    int queuesize;
}Queue;

int size(Queue *queue)
{
    return queue->queuesize;
}

int empty(Queue *queue)
{ 
    return queue->front==NULL;
}

int front(Queue *queue)
{
    if(empty(queue)==1)
        return -1;
    else
        return queue->front->data;
}

int back(Queue *queue)
{
    if(empty(queue)==1)
        return -1;
    else
        return queue->rear->data;
}

void InitQueue(Queue *queue)
{
    queue->front = NULL;
    queue->rear = NULL;
    queue->queuesize = 0;
}

void push(Queue *queue, int data)
{
    Node *now = (Node *)malloc(sizeof(Node));
    now->data = data;
 
    if (empty(queue))
        queue->front = now;     
    else
        queue->rear->next = now;
	
    queue->rear = now;
    queue->queuesize++;
}

int pop(Queue *queue)
{
    if (empty(queue))
        return -1;
	
    int re = queue->front->data;
    queue->front = queue->front->next;
    queue->queuesize--;
    return re;
}

int main(void)
{
    Queue *queue = (Queue*)malloc(sizeof(Queue));
	InitQueue(queue);
	char Get_Com[10];
	int N,pushnum;
	scanf("%d",&N);
	for(int i=0;i<N;i++)
	{
		scanf("%s",Get_Com);
		if(strcmp(Get_Com,"push")==0)
		{
			scanf("%d",&pushnum);
			push(queue,pushnum);
		}
		else if(strcmp(Get_Com,"pop")==0)
			printf("%d\n",pop(queue));
		else if(strcmp(Get_Com,"size")==0)
			printf("%d\n",size(queue));
		else if(strcmp(Get_Com,"empty")==0)
			printf("%d\n",empty(queue));
		else if(strcmp(Get_Com,"front")==0)
			printf("%d\n",front(queue));
		else if(strcmp(Get_Com,"back")==0)
			printf("%d\n",back(queue));
	}
    return 0;
}