문제
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여섯 가지이다.
push X: 정수 X를 큐에 넣는 연산이다.
pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 큐에 들어있는 정수의 개수를 출력한다.
empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
백준 10845번은 스택과 함께 나오는 자료구조 큐에 대한 문제이다. 문제를 풀기 전에 큐에 대한 정보를 먼저 정리하고자 한다.
스택이 먼저 들어간 데이터가 나중에 나오는, 일명 FILO(Fast Input Last Output) 의 구조를 가지고 있었다면, 큐(Queue)는 먼저 들어간 데이터가 먼저 나오는 FIFO(First Input First Output) 의 구조를 가지고 있다.
이와 같은 2차원 배열로 표현할 수 있다. 데이터가 삽입된다면, 왼쪽의 배열부터 삽입되면서, rear을 오른쪽으로 한 칸 옮기게 된다. front가 옮겨지는 것이 아니다.
대신, 데이터를 없애는 작업(pop)을 할 때는 front를 오른쪽으로 한 칸 옮기는 것이다. 마치 빵 반죽을 오른쪽으로 길게 늘린 후, 왼쪽부터 한 덩어리씩 잘라가는 것과 비슷하다고 보면 되겠다.
이를 c언어로 표현하는 방법을 알아보자.
우선, 배열을 표현하는 것은 충분히 가능할 것이다. 그럼 front와 rear을 설정하고, 초기값을 설정해준다 (1번). 초기값은 -1을 해도, 0을 해도 상관 없다. 대신, front와 back을 받았을 때의 출력을 잘 생각해야 할 것이다.
그 다음, 명령어를 받을 char형 배열을 하나 만들고(2번), 총 명령어 수를 받는다 (3번). for 문 안에서 명령어 수 만큼의 반복문을 돌리면서, 명령어에 따른 출력을 만들어내면 된다.
첫 번째로, 만약 입력이 push일 경우(4-1번), 무슨 숫자를 push할지를 입력 받은 후(4-1-1번), pushq라는 함수에 넣어서 배열에 push해준다(4-1-2).
두 번째로, 만약 입력이 pop일 경우(4-2번), popq라는 함수를 실행하여 배열에서 pop해준다 (4-2-1번).
세 번째로, 만약 입력이 size일 경우(4-3번), 이 배열에 들어있는 총 숫자를 계산한다. 이는 맨 뒤와 앞의 차이와 같으므로, 그 해를 출력한다(4-3-1번).
네 번째로, 만약 입력이 empty일 경우(4-4번), 우선 이 배열이 비었는지 아닌지를 확인해야 한다. 배열이 비었다는 것은 front와 rear가 같은 위치에 있음을 의미하므로, front == rear일 경우 비어있다는 것을 확인할 수 있다(4-4-1번).
다섯 번째로, 만약 입력이 front일 경우(4-5번), 배열이 비었을 때 -1, 그렇지 않으면 맨 앞의 정수를 출력해주면 된다(4-5-1번).
마지막으로, 만약 입력이 back일 경우(4-6번), front와 같이 배열이 비었을 때 -1, 그렇지 않으면 맨 뒤의 정수를 출력한다(4-6-1번).
#include <stdio.h>
#include <string.h>
#define SIZE 10000
int queue[SIZE]; // 1
int front = 0;
int rear = 0;
void pushq(int);
void popq();
int main(void) {
char a[10]; // 2
int total, num;
scanf("%d", &total); // 3
for (int i = 0; i < total; i++) {
scanf("%s", a);
if (!strcmp(a, "push")) { // 4-1
scanf("%d", &num); // 4-1-1
pushq(num); // 4-1-2
}
else if (!strcmp(a, "pop")) { // 4-2
popq(); // 4-2-1
}
else if (!strcmp(a, "size")) { // 4-3
printf("%d\n", rear - front); // 4-3-1
}
else if (!strcmp(a, "empty")) { // 4-4
if (front == rear) { // 4-4-1
printf("1\n");
}
else {
printf("0\n");
}
}
else if (!strcmp(a, "front")) { // 4-5
if (front == rear) { // 4-5-1
printf("-1\n");
}
else {
printf("%d\n", queue[front]);
}
}
else if (!strcmp(a, "back")) { // 4-6
if (front == rear) { // 4-6-1
printf("-1\n");
}
else {
printf("%d\n", queue[rear - 1]);
}
}
}
}
void pushq(int num) {
queue[rear] = num;
rear++;
}
void popq() {
if (front == rear){
printf("-1\n");
}
else {
printf("%d\n", queue[front]);
front++;
}
}