[C언어] 백준 10854 큐

문제

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

명령은 총 여섯 가지이다.

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

입력

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

출력

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

예제 입력 1 

15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front

예제 출력 1 

1
2
2
0
1
2
-1
0
1
-1
0
3

https://www.acmicpc.net/problem/10845

10845번: 큐

전형적인 큐 자료구조 문제입니다.

문제에서 요구하는 큐 명령은 총 6가지로

push : 새로운 정수를 큐의 최상단에 삽입

pop : 큐의 최상단 요소의 정수값 반환 하면서 최상단 요소 제거, 큐가 비어있으면 -1 반환

empty : 큐가 비어있으면 1반환, 큐가 비어있지 않다면 0반환

front : 큐의 최상단 요소의 정수값 반환, 큐가 비어있으면 -1 반환

back : 큐의 최하단 요소의 정수값 반환, 큐가 비어있으면 -1 반환

size : 큐의 요소의 개수 반환

 

이렇게 6가지 명령을 만드는것을 요구하는 문제입니다.

큐를 얼마나 잘 알고 있느냐 보다는 구현능력을 테스트 하는 문제 같습니다.

 

이 문제를 풀 때는 직접 큐를 만들어도 되고 배열로 구현해서 풀어도 상관은 없습니다.

하지만 배열로 문제를 푸는것은 별로 추천하지 않습니다.

배열로 풀면 실제 큐를 구현해서 bfs알고리즘을 사용하기 매우 어렵습니다.

그렇기에 직접 큐를 만들어서 푸시는것을 추천드립니다.

 

 

typedef struct t
{
    int content;
    struct t *next;
    struct t *prev;
} node;

typedef struct q
{
    int size;
    node *head;
    node *tail;
} queue;

먼저 큐를 만들기 위한 구조체를 선언합니다.

queue *create_queue(void)
{
    queue *temp;

    temp = (queue *)malloc(sizeof(queue));
    temp->head = (node *)malloc(sizeof(node));
    temp->tail = (node *)malloc(sizeof(node));
    temp->head->content = -1;
    temp->head->next = temp->tail;
    temp->head->prev = NULL;
    temp->tail->next = NULL;
    temp->tail->prev = temp->head;
    temp->size = 0;
    return (temp);
}

node    *create_node(int content)
{
    node *temp;

    temp = (node *)malloc(sizeof(node));
    temp->content = content;
    temp->next = NULL;
    temp->prev = NULL;
    return (temp);
}

그리고 큐를 만드는 create_queue 함수와

안에 요소들을 만들어 줄 create_node 함수를 만들어 줍니다.

 

void q_push(queue *q, int content)
{
    node *temp;
    node *last;

    temp = create_node(content);
    last = q->tail->prev;
    if (q->head->next == q->tail)
    {
        q->head->next = temp;
        temp->prev = q->head;
    }
    else
    {
        last->next = temp;
        temp->prev = last;
    }
    temp->next = q->tail;
    q->tail->prev = temp;
    q->size++;
}

push 명령문이 들어왔을 때 사용할 q_push 함수를 만들어 줍니다.

맨 처음에 큐는 비어있을 것이기 때문에 비어있을 때 따로 조건을 걸지 않으면

segment fault 오류가 나기 쉬워서 따로 조건을 걸어주고 push 할 때마다 큐의 size를 1씩 올려줍니다.

 

void    del_node(queue *q)
{
    node *del;
    node *second;

    if (q->size == 0)
        return;
    del = q->head->next;
    second = del->next;
    q->head->next = second;
    second->prev = q->head;
    q->size--;
    free(del);
}

pop 명령을 도와줄 del_node함수입니다.

큐의 맨 앞의 노드를 제거해 주는 함수입니다.

int q_pop(queue *q)
{
	int	n;

    if (q->size == 0)
        return (-1);
    n = q->head->next->content;
    del_node(q);
    return (n);
}

pop 명령이 들어왔을 때 사용할 q_pop함수입니다.

큐가 비어있을 때 -1을 반환해주고 그 외에는

큐의 최상단 요소의 값을 미리 받고 del_node 함수를 사용한뒤

최상단 요소의 값을 반환해 줍니다.

 

int q_front(queue *q)
{
    if (q->size == 0)
        return (-1);
    return (q->head->next->content);
}

front 명령이 들어왔을 때 사용할 q_front함수입니다.

큐가 비어있다면 -1 반환해주고 그 외에는

최상단 요소의 값을 반환해 줍니다.

int q_size(queue *q)
{
    return (q->size);
}

size 명령이 들어왔을 때 사용할 q_size함수입니다.

단순히 큐의 size만 반환시켜줍니다.

 

int q_empty(queue *q)
{
    if (q->size == 0)
        return (1);
    return (0);
}

empty 명령이 들어왔을 때 사용할 q_empty함수입니다.

큐가 비어있다면 1을 반환 그 외에는

0을 반환해 줍니다.

 

int q_back(queue *q)
{
    if (q->size == 0)
        return (-1);
    return (q->tail->prev->content);
}

back 명령이 들어왔을 때 사용할 q_back함수입니다.

큐가 비어있다면 -1을 반환 그 외에는

큐의 최하단 요소의 값을 반환해 줍니다.

void    q_free(node *temp)
{
    if (temp->next != NULL)
        q_free(temp->next);
    free(temp);
}

큐를 다 사용하고 큐의 노드들을 동적 할당 했으니 해제해줄

q_free 함수입니다.

 

int main(void)
{
    queue *q;
    scanf("%d", &t);
    q = create_queue();
    char cmd1[6];
    char cmd2[12];
    for(int i = 0; i < t; i++)
    {
        scanf("%s", cmd1);
        if (!strcmp(cmd1, "push"))
        {
            scanf("%s", cmd2);
            q_push(q, atoi(cmd2));
        }
        else if (!strcmp(cmd1, "front"))
            printf("%d\n", q_front(q));
        else if (!strcmp(cmd1, "back"))
            printf("%d\n", q_back(q));
        else if (!strcmp(cmd1, "size"))
            printf("%d\n", q_size(q));
        else if (!strcmp(cmd1, "empty"))
            printf("%d\n", q_empty(q));
        else if (!strcmp(cmd1, "pop"))
            printf("%d\n", q_pop(q));
    }
    q_free(q->head);
    free(q);
    return (0);
}

main함수입니다.

맨 처음 create_queue 함수를 호출해 큐를 만들어 주고 반복적으로 명령을 받고 실행 해줍니다.

먼저 cmd1을 받아 첫 번째 명령을 받습니다.

각각 명령을 찾기 위해 strcmp함수를 사용해줍니다.

cmd1이 push인 경우 추가적으로 cmd2로 두 번째 인수를 받기 위한 cmd2를 입력받고

받은 인자를 atoi를 사용해 정수로 변환한 뒤 push해줍니다.

cmd1이 다른 명령문이라면 상황에 맞게끔 함수를 호출해주면서 반복문을 끝내준 뒤

q_free 함수를 사용해 큐의 모든 노드들을 해제해 주고 마지막으로 큐도 해제해준뒤 main 함수가 종료되면서 끝납니다.

 

 

반응형

 

저는 C언어를 사용할 때 링크드 리스트를 자주 애용하는데요.

링크드 리스트 중에서 특히 양방향을 굉장히 좋아합니다.

단방향과 양방향 서로의 장단점이 있지만 마지막 노드를 연산 1로

찾을 수 있다는 매력이 너무 좋아서 양방향을 주로 사용합니다.

그래서 이번 문제도 양방향 링크드 리스트를 사용해서 풀어 보았습니다.