[C] 백준 BAEKJOON 18258번: 큐 2

 

---

[1] 문제

 

 

 

 

 

문제

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

명령은 총 여섯 가지이다.

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

 

 

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,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

 

 

 

---

[2] 정답

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

int queue[2000001];
int front = 0;
int rear = -1;

void clean(char arr[]); // 초기화용 함수
void push(int x);
void pop(void);
void size(void);
void empty(void);

int main(void) {
	int n, i, x;
	char command[6];
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%s", command); // 명령 입력
		if (!strcmp(command, "push")) {
			scanf("%d", &x);
			push(x);
		}
		else if (!strcmp(command, "pop"))
			pop();
		else if (!strcmp(command, "size"))
			size();
		else if (!strcmp(command, "empty"))
			empty();
		else if (!strcmp(command, "front")) {
			if (rear - front + 1 == 0)
				printf("%d\n", -1);
			else
				printf("%d\n", queue[front]);
		}
		else if (!strcmp(command, "back")) {
			if (rear - front + 1 == 0)
				printf("%d\n", -1);
			else
				printf("%d\n", queue[rear]);
		}
		clean(command); // 초기화
	}
	return 0;
}
void clean(char arr[]) {
	int i;
	for (i = 0; i < 6; i++)
		arr[i] = '\0';
}
void push(int x) {
	queue[++rear] = x;
}
void pop(void) {
	if (rear - front + 1 == 0)
		printf("%d\n", -1);
	else
		printf("%d\n", queue[front++]);
}
void size(void) {
	printf("%d\n", rear - front + 1);
}
void empty(void) {
	if (rear - front + 1 != 0)
		printf("%d\n", 0);
	else
		printf("%d\n", 1);
}

 

---

[3] 해석

 

# 코드 분석

 

1) int queue[2000001];, int front = 0;, int rear = -1;:

 

- 정수형 배열 queue를 선언, 이 큐는 최대 2000001개의 요소를 가질 수 있다.

- front는 큐의 맨 앞을 가리키는 인덱스를 나타낸다.

- rear는 큐의 맨 뒤를 가리키는 인덱스를 나타낸다.

 

 

2) void clean(char arr[]);:
- clean 함수는 배열 arr을 초기화하는 함수. 이 함수는 모든 요소를 널 문자('\0')로 초기화한다.

 

 

3) void push(int x);:

- push 함수는 정수 x를 큐에 삽입하는 함수. rear를 증가시킨 후에 x를 rear 위치에 넣는다.

 

 

4) void pop(void);:

- pop 함수는 큐에서 요소를 제거하고 해당 요소를 출력하는 함수. 만약 큐가 비어있으면 -1을 출력한다.

 

 

5) void size(void);:

- size 함수는 큐의 현재 크기를 출력하는 함수. 큐의 크기는 rear와 front의 차이에 1을 더한 값이다.

 

 

6) void empty(void);:

- empty 함수는 큐가 비어있는지 여부를 출력하는 함수. 만약 큐가 비어있으면 1을, 그렇지 않으면 0을 출력한다.

 

 

7) int main(void):
- 사용자로부터 명령어의 개수 n을 입력받는다.
- 반복문을 통해 n번의 명령어를 입력받고 처리한다.
- 각 명령어에 따라 push, pop, size, empty, front, back 등의 함수를 호출하여 작업을 수행한다.

 

 

# 문제의 포인트

큐 자료구조 구현:
- queue 배열을 사용하여 큐를 구현. front와 rear를 사용하여 큐의 맨 앞과 맨 뒤를 가리킨다.

 

---

[4] 참고

 

https://dalconbox.tistory.com/52

백준 18258번 큐 2 [ C ]