[백준] 10845. 큐

: solved.ac class 2 - silver 4

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

10845번: 큐

 

 

예제 입력

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

 

예제 출력

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

 

정답

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>

int queue[10001]; 
int size = 0;


void PUSH(int n) {
	queue[size] = n;
	size++; 
}

void POP() {
	if (size == 0) printf("-1 \n"); 
	else {
		size--; 
		printf("%d \n", queue[0]); 
	}
}

void SIZE() {
	printf("%d \n", size); 
}

void EMPTY() {
	if (size == 0) printf("1 \n");
	else printf("0 \n");
}

void FRONT() {
	if (size == 0) printf("-1 \n"); 
	else printf("%d \n", queue[0]); 
}

void BACK() {
	if (size == 0) printf("-1 \n"); 
	else printf("%d \n", queue[size - 1]);
}

void SET() {
	for (int i = 0; i < size; i++) queue[i] = queue[i + 1];
}

int main() {

	int n, num;
	char cmd[10] = { '\0' };

	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%s", cmd);

		if (strcmp(cmd, "push") == 0) {
			scanf("%d", &num);
			PUSH(num);
		}
		else if (strcmp(cmd, "pop") == 0) {
			POP();
			SET();
		}
		else if (strcmp(cmd, "size") == 0) SIZE();
		else if (strcmp(cmd, "empty") == 0) EMPTY();
		else if (strcmp(cmd, "front") == 0) FRONT();
		else if (strcmp(cmd, "back") == 0) BACK();
	}
	return 0;
}

---

해설

 

• 1주차 문제 10828. 스택 참고

 

1. 헤더파일과 전역변수 부분이다. 스택 문제와 유사하게 명령어를 받고 수행하는 형식의 문제이므로, 유사한 기능을 구현하기 위해 string.h 헤더파일을 가져왔다.

마찬가지로 큐 공간으로 사용할 정수 배열과, 배열에 몇 개의 원소가 push되었는지 표시해 줄 정수 변수 또한 선언해 준다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>

int queue[10001]; //큐가 될 배열
int size = 0; //큐의 크기 (큐에 들어간 원소의 개수)

 

 

2. 역시 main 함수부터 작성해 두도록 하겠다. 명령 개수인 n과 push 명령에 필요한 정수를 받을 변수, 그리고 명령을 받을 배열을 선언한다.

int main() {

	int n, num;
	char cmd[10] = { '\0' };

	scanf("%d", &n);

 

 

3. 명령이 들어올 때마다 strcmp 함수를 이용해 입력값과 명령을 비교한다.

	for (int i = 0; i < n; i++) {
		scanf("%s", cmd);

		if (strcmp(cmd, "push") == 0) {
			scanf("%d", &num);
			PUSH(num);
		}
		else if (strcmp(cmd, "pop") == 0) {
			POP();
			SET();
		}
		else if (strcmp(cmd, "size") == 0) SIZE();
		else if (strcmp(cmd, "empty") == 0) EMPTY();
		else if (strcmp(cmd, "front") == 0) FRONT();
		else if (strcmp(cmd, "back") == 0) BACK();
	}
	return 0;
}

strcmp 함수에 대한 내용 역시도 스택 문제를 풀 때 간략히 설명해 두었으니 참고해 주길 바란다.

전체적으로 스택 문제와 유사한 구조이나, 스택의 top이 큐에서는 front와 back 두 개로 늘어났다.

+ 자세히 보면 문제에서 제시한 명령어에 없는 SET이라는 함수가 하나 있는 것이 보일 것이다. 아래에서 설명하겠다.

 

 

4. void형 함수로 명령 처리 부분을 구현한다.

상세한 내용은 주석을 통해 설명하겠다.

//push X: 정수 X를 큐에 넣는 연산이다.
void PUSH(int n) {
	queue[size] = n; //큐의 rear에 정수를 받아 넣고
	size++; //큐 크기를 1 증가시킴
}

//pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다.
//만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
void POP() {
	if (size == 0) printf("-1 \n"); //큐가 비어있으면 -1 출력
	else {
		size--; //큐 크기를 1 감소시키고
		printf("%d \n", queue[0]); //front에 들어있는 원소 출력
	}
}

//size: 큐에 들어있는 정수의 개수를 출력한다.
void SIZE() {
	printf("%d \n", size); //큐 크기 출력
}

//empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
void EMPTY() {
	if (size == 0) printf("1 \n");
	else printf("0 \n");
}

//front: 큐의 가장 앞에 있는 정수를 출력한다.
//만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
void FRONT() {
	if (size == 0) printf("-1 \n"); //큐가 비어있으면 -1 출력
	else printf("%d \n", queue[0]); //아니면 front의 원소 출력
}

//back: 큐의 가장 뒤에 있는 정수를 출력한다.
//만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
void BACK() {
	if (size == 0) printf("-1 \n"); //큐가 비어있으면 -1 출력
	else printf("%d \n", queue[size - 1]); //아니면 rear의 원소 출력
}

 

 

5. 이 문제는 스택이 아닌 큐를 구현하는 문제이기 때문에 추가적으로 구현해 주어야 할 기능이 있다.

스택은 후입선출(LIFO) 구조로, 마지막에 입력받은 원소를 가장 먼저 pop하는 자료구조이나

큐는 선입선출(FIFO) 구조다. 가장 먼저 입력받은 원소를 먼저 pop한다.

때문에 배열을 이용해 구현한다면 pop할 때마다 배열 앞쪽(front)은 비고, 배열 뒤쪽(rear)은 점점 차오르는 현상이 생길 수 있다.

이를 방치하면 배열의 크기가 10000이라 할지라도 10000개의 원소를 다 채우기도 전에 배열이 꽉 차버릴 수 있다!

이러한 현상을 막기 위해서는 별도의 조치를 취해 줄 필요가 있다. 내가 구현한 것은 그 중 가장 간단한 방법이다.

 

바로 pop 연산을 할 때마다 배열의 원소들을 앞쪽으로 한 칸씩 당겨 주는 방법이다.

pop은 배열 앞쪽의 원소를 꺼내는 연산이므로, 수행하고 나면 queue[0]이 있던 자리가 비었을 것이고

대신 queue[1]에 있던 값을 queue[0]에 넣어 주는 것이다.

queue[2]를 queue[1] 자리에, [3]을 [2] 자리에...

이렇게 한 칸씩 당기면 배열 앞쪽에 빈 공간이 생길 일은 없을 것이다.

//pop 연산 후 배열의 원소들을 front 방향으로 한칸씩 당겨 주는 함수
void SET() {
	for (int i = 0; i < size; i++) queue[i] = queue[i + 1];
	//항상 큐의 0번 인덱스가 front가 될 수 있도록 유지시켜 줌
}

다만 이 방법은 해당 시점에서 큐에 들어 있는 원소의 갯수만큼 대입연산을 시행해 주어야 하기 때문에

자료의 갯수가 늘어나면 그만큼 연산 시간의 낭비를 초래하게 된다.

이를 해결하기 위해 원통형 큐를 구현하는 방법도 있으나 이 문제에서는 위의 방법으로도 충분했기 때문에 구태여 구현하지는 않았다.