[C / C++] 백준 10845번 - 큐(Queue)

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

10845번: 큐

✅ 문제 설명

말 그대로 큐를 구현하는 문제이다.

 

⚡ 큐란?

간단하게 설명하자면 선입선출 구조!

FIFO (First In First Out) 로,

식당에 가서 줄을 서면 먼저 줄을 선 사람부터 차례로 입장하듯이

가장 먼저 넣은 정보부터 차례로 꺼내는 구조이다.

예를 들어 a -> b -> c 순서대로 넣었다면, 뺄 때는 a -> b -> c 순서로 꺼내게 된다는 것이다.

여기서 넣는 것은 ‘push’, 빼는 것은 ‘pop’이라고 칭한다.

 

1. 초기 상태 (아무것도 없는 공백 상태)

2. push(a) -> push(b) -> push(c)

3. pop() -> pop() -> pop()

1. push X : 정수 X를 큐에 넣는다.

2. pop : 큐에서 가장 앞에 있는 정수를 빼서 출력 (비어있다면 –1 출력)

3. size : 큐에 들어있는 정수의 개수 출력

4. empty : 큐가 비어있으면 1, 아니면 0 출력

5. front : 큐의 가장 앞에 있는(먼저 넣은) 정수 출력 (비어있으면 –1출력)

6. back : 큐의 가장 뒤에 있는(마지막에 넣은) 정수 출력 (비어있으면 –1 출력)

---

✅ 알고리즘 설명

1. 전역변수 idx_f, idx_b을 사용

-1) idx_b은 현재 큐의 마지막 인덱스를 뜻하며, idx_f는 맨 앞 인덱스를 뜻함

-2) 인덱스는 0부터 시작하기 때문에 idx_b을 0이 아니라 –1로 시작함

 

2. front()

-1) empty() == 1이면 –1 반환

-2) 아니면 queue[idx_f] (맨 앞에 있는 값) 반환

 

3. back()

-1) empty() == 1이면 –1 반환

-2) 아니면 queue[idx_b] (맨 뒤에 있는 값) 반환

 

4. push(int x)

-1) idx_b가 -1부터 시작했기 때문에 +1을 한 후 값 x 넣기

 

5. pop()

-1) empty() == 1이면 공백이므로 –1 반환

-2) pop()을 하면 맨 앞 정수를 꺼내기 때문에 idx_f++

-3) 꺼내기 전 정수를 반환해야 하므로 queue[idx_f-1] 반환

 

6. size()

-1) (마지막 인덱스 - 첫 번째 인덱스) + 1을 하면 전체의 개수가 나옴

ex) 첫번째 인덱스 = 1 💛 마지막 인덱스 = 3
(마지막 인덱스 – 첫번째 인덱스 = 3 - 1 = 2) ⏩ 2+1 = 3

idx = 0	idx =1	idx = 2	idx = 3
	a	b	c

 

7. empty()

idx_f > idx_b이면 비어있다고 판단함

---

✅ 코드 [C언어]

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h> 

int queue[10000];
int idx = -1; // idx는 0부터 시작하니까 -1로 설정
int first = 0; // front용

// true가 현재 하나라도 있는 상태, false가 공백
typedef enum {false, true} bool;
bool emp = false;  // 초기상태는 공백으로 처리

void push(int x) {
	idx++; // -1로 설정해서 ++하고 시작
	queue[idx] = x;
	emp = true; // 뭐있다고 바꾸기
}

void pop() {
	if (emp == false)
		printf("-1\n");
	else {
		printf("%d\n", queue[first]);
		if (idx == first)
			emp = false;
		first++; // first ++
	}
}

void front() {
	if (emp == false) // 비어있다면
		printf("-1\n");
	else
		printf("%d\n", queue[first]);
}

void back() {
	if (emp == false) // 비어있다면
		printf("-1\n");
	else
		printf("%d\n", queue[idx]);
}

void size() {
	printf("%d\n", idx + 1 - first);
}

void empty() {
	if (emp == true)
		printf("0\n");
	else
		printf("1\n");
}

int main(void) {
	int n, x;
	scanf("%d", &n);

	char input[6];
	for (int i = 0; i < n; i++) {
		scanf("%s",input);
		if (!strcmp(input, "push")) {
			scanf("%d", &x);
			push(x);
		}
		else if (!strcmp(input, "pop")) {
			pop();
		}
		else if (!strcmp(input, "size"))
			size();
		else if (!strcmp(input, "empty")) {
			empty();
		}
		else if (!strcmp(input, "front")) {
			front();
		}
		else if (!strcmp(input, "back")) {
			back();
		}
	}
	return 0;
}

 

https://github.com/2hyunjinn/Baekjoon/blob/6e155f58b7fdf95083d84ad5e97a3f2798bcbb55/Baekjoon_10845.c

GitHub - 2hyunjinn/Baekjoon

위 코드는 queue의 정확한 알고리즘을 공부하기 위해서 풀어서 구현해보았다.

만약 C++을 통해 쉽게 구현하고 싶다면 이미 queue를 구현해놓은 C++의 내장함수를 사용하면 된다.

---

✅ 코드 [C++ 내장함수]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	queue<int> queue;
	for (int i = 0; i < n; i++) {
		string word;
		cin >> word;
		if (word == "push") {
			int x;
			cin >> x;
			queue.push(x);
		}
		else if (word == "pop") {
			if (queue.empty()) cout << -1 << '\n';
			else {
				cout << queue.front() << '\n';
				queue.pop();
			}
		}
		else if (word == "size") {
			cout << queue.size() << '\n';
		}
		else if (word == "empty") {
			cout << queue.empty() << '\n';
		}
		else if (word == "front") {
			if (queue.empty()) cout << -1 << '\n';
			else cout << queue.front() << '\n';
		}
		else if (word == "back") {
			if (queue.empty()) cout << -1 << '\n';
			else cout << queue.back() << '\n';
		}
	}
	return 0;
}

 

 

https://github.com/2hyunjinn/Baekjoon/blob/7601643deb85a3f83e69779bf15ddef03a9508e7/Baekjoon_10845.cpp

GitHub - 2hyunjinn/Baekjoon