[백준 10845/C언어] 큐 풀이

백준 10845번 문제를 풀어보았습니다.

백준 10845번: https://www.acmicpc.net/problem/10845

10845번: 큐

 

 

문제 내용은 다음과 같습니다.

 

 

 

큐(Queue)는 대표적인 자료구조 중 하나입니다. 보통 스택(Stack)과 함께 이야기되는데, 큐는 FIFO(Frist In First Out, 선입선출)이고 스택은 LIFO(Last In First Out, 후입선출)를 구현한 대표적인 자료구조에 해당합니다.

 C언어에서 큐를 구현할 때는 보통 배열 하나를 선언한 후에 head와 tail 변수로 queue 배열의 구간을 표시해 두어 사용합니다. C언어 배열들은 삽입이나 삭제가 자유롭지 않기 때문입니다. 큐에서는 선입선출이므로 배열의 첫 요소가 삭제되고 새로운 요소는 맨 뒤에 삽입이 되는데, 맨 앞 요소가 삭제되면 보통 그 뒤 요소들을 하나씩 당겨와야 하기 때문에 이런 비효율을 방지하기 위해 그러한 방법을 사용합니다. 

 

자세한 구현 방법을 아래에서 보겠습니다. 우선 큐 자체를 구현하기 위해서는 배열 하나와 head 그리고 tail을 담은 구조체를 만들었습니다. head 변수에서 구간이 시작되고, tail 변수에서 구간이 종료됩니다. 

typedef struct QUEUE {
    int ary[10000];
    int head;
    int tail;
} Queue;

 

 

다음은 queue의 기능들입니다. 문제에서 push, pop, size, empty, front, back의 다섯 가지 기능을 구현할 것을 요구하고 있습니다.

우선 push와 pop, 즉 삽입과 삭제를 하는 기능부터 보겠습니다. push를 할 때는 맨 뒤에 붙여넣어야 하므로, tail 위치에 입력받은 n을 넣어주고 tail을 하나 증가시켜 줍니다.

 pop을 할 때는 이어서 나올 isEmpty() 함수를 통해 큐가 비어있는지 확인하고, 비어있다면 -1을 아니라면 head 위치에 있는 요소를 리턴해주면서 head를 하나 증가시켜줍니다. head를 증가시켜 준다는 것은 구간을 바꿔 기존 head 위치에 있던 요소를 삭제하는 것을 의미합니다.

 그리고 삽입과 삭제를 하는 함수에서만 queue를 포인터로 받습니다. 여기서만 queue 내의 변화가 발생하기 때문입니다. 

void push(int n, Queue *queue) {
    queue->ary[(queue->tail)++] = n; 
}

int pop(Queue *queue) {
    if (isEmpty(*queue)) return -1;
    else return queue->ary[(queue->head)++];
}

 

 다음은 크기 관련 정보를 가져오는 함수입니다. size는 tail과 head의 차로 큐에 몇 개의 원소가 있는지를 리턴합니다. 만약 둘의 차가 음수라면 0을 리턴합니다.

 isEmpty()는 head가 tail보다 크거나 같다면, 큐가 비어있다는 의미이므로 1을 리턴하고, 아니라면 0을 리턴합니다. 

int size(Queue queue) {
    int size = queue.tail - queue.head;
    if (size <= 0) return 0;
    else return size;
}

int isEmpty(Queue queue) {
    if (queue.head >= queue.tail) return 1;
    else return 0;
}

 

다음은 특정 위치의 요소를 가져오는 함수입니다. getFront는 가장 첫 요소, 즉 head 위치에 있는 요소를 가져옵니다. 큐가 비어있다면 -1을, 아니면 head 인덱스에 있는 요소를 리턴합니다.

 getBack은 가장 마지막 요소, 즉 tail 위치에 있는 요소를 가져옵니다. 하지만 tail을 바로 인덱스로 쓰게 되면 빈 요소가 출력됩니다. 왜냐하면 앞서 삽입을 할 때, 삽입 후 바로 tail을 증가시켜줬기 때문입니다. 간단히 예를 들면, head와 tail은 (0, 0)으로 출발하게 되는데, 하나가 추가되면 index 0에 값이 추가되고 tail은 1이 됩니다. 이때 tail에는 아무런 값이 저장되어 있지 않습니다. 따라서 마지막 요소는 엄밀히 말하면 tail-1 인덱스에 존재하는 것입니다. 그래서 구현 시에는 큐가 비어있다면 -1을 아니면 tail-1 인덱스에 있는 요소를 리턴하게 됩니다. 

int getFront(Queue queue) {
    if (isEmpty(queue)) return -1;
    else return (queue.ary[queue.head]);
}

int getBack(Queue queue) {
    if (isEmpty(queue)) return -1;
    else return (queue.ary[queue.tail - 1]);
}

 

 

 마지막으로 main 함수입니다. 메인 함수에서는 앞서 작성한 함수를 활용하여 문제에서 요구한 대로 값을 입력받고 출력하게 됩니다. 우선 명령의 수인 N을 입력받고, Queue를 생성하여, head와 tail의 초기값을 0으로 설정해 줍니다. 

 명령문을 받을 command 문자열과 push 명령일 때에 삽입할 n을 변수로 선언해주고, N번의 명령을 실행할 for문으로 진입합니다. 먼저 command 문자열을 읽어주고, command 문자열의 첫 글자에 따라 실행문을 정하는 switch case문을 실행하게 됩니다. 문제에 제시된 명령들 중 첫 글자가 같은 명령은 push와 pop밖에 없으므로, default에서 두 번째 글자로 다시 나눠주고, 나머지는 첫 글자로 나눠주면 됩니다. 

 첫글자가 's'인 경우 size 명령이므로 size 함수의 리턴값을 출력해 줍니다. 'e'인 경우 empty 명령이므로 isEmpty 함수의 리턴값을 출력해 줍니다. 'f'인 경우 front 명령이므로 getFront 함수의 리턴값을, 'b'인 경우 back 명령이므로 getBack 함수의 리턴값을 출력해 줍니다. default에서는 첫 글자가 p인 경우를 처리합니다. 두 번째 글자가 'u'인 경우는 push 명령이므로, 큐에 넣을 n값을 다시 입력받아 준 후 push 함수를 실행시켜 줍니다. 두 번째 글자가 'o'인 경우는 pop 명령이므로, pop 함수를 실행시켜 줍니다. 

int main() {
    int N;
    scanf("%d", &N);
    
    Queue queue;
    queue.head = 0;
    queue.tail = 0;
    
    char command[20];
    int n;
    for (int i = 0; i < N; i++) {
        scanf("%s", command);
        switch (command[0]) {
            case 's':
                printf("%d\n", size(queue));
                break;
            case 'e':
                printf("%d\n", isEmpty(queue));
                break;
            case 'f':
                printf("%d\n", getFront(queue));
                break;
            case 'b':
                printf("%d\n", getBack(queue));
                break;
            default:
                if (command[1] == 'u') {
                    scanf("%d", &n);
                    push(n, &queue);
                } else printf("%d\n", pop(&queue));
        }
    }
}

 

 

 

이를 모두 이어붙인 전체 코드는 다음과 같습니다. 

#include <stdio.h>

typedef struct QUEUE {
    int ary[10000];
    int head;
    int tail;
} Queue;

void push(int n, Queue *queue);
int pop(Queue *queue);
int size(Queue queue);
int isEmpty(Queue queue);
int getFront(Queue queue);
int getBack(Queue queue);

void push(int n, Queue *queue) {
    queue->ary[(queue->tail)++] = n; 
}

int pop(Queue *queue) {
    if (isEmpty(*queue)) return -1;
    else return queue->ary[(queue->head)++];
}

int size(Queue queue) {
    int size = queue.tail - queue.head;
    if (size <= 0) return 0;
    else return size;
}

int isEmpty(Queue queue) {
    if (queue.head >= queue.tail) return 1;
    else return 0;
}

int getFront(Queue queue) {
    if (isEmpty(queue)) return -1;
    else return (queue.ary[queue.head]);
}

int getBack(Queue queue) {
    if (isEmpty(queue)) return -1;
    else return (queue.ary[queue.tail - 1]);
}

int main() {
    int N;
    scanf("%d", &N);
    
    Queue queue;
    queue.head = 0;
    queue.tail = 0;
    
    char command[20];
    int n;
    for (int i = 0; i < N; i++) {
        scanf("%s", command);
        switch (command[0]) {
            case 's':
                printf("%d\n", size(queue));
                break;
            case 'e':
                printf("%d\n", isEmpty(queue));
                break;
            case 'f':
                printf("%d\n", getFront(queue));
                break;
            case 'b':
                printf("%d\n", getBack(queue));
                break;
            default:
                if (command[1] == 'u') {
                    scanf("%d", &n);
                    push(n, &queue);
                } else printf("%d\n", pop(&queue));
        }
    }
}