[Baekjoon/백준][18258][C/C++] 큐 2

『목차』
0. 개요
1. 문제
2. 풀이
3. 코드

0. 개요

자료구조, 큐 문제. '백준 10845 큐' 문제와 동일하지만 입력값의 수가 훨씬 크다.

1. 문제

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

18258번: 큐 2

[문제]

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

명령은 총 여섯 가지이다.

• 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. 풀이

큐 Class를 만든 후, 큐의 ADT를 직접 구현하는 방식으로 만들었다.

STL의 Queue를 이용해도 좋았겠지만, 공부 목적으로 직접 구현을 선택했다.

3. 코드

#include <iostream>
#include <string>
using namespace std;

class queue {
private:
	int* arr;

	int F;
	int R;

	const int max = 2000001;
public:
	/* Constructor & Destructor */
	queue() : F(0), R(0) {
		arr = new int[max]();
	}
	~queue() {
		delete[] arr;
	}
	/* Method */
	void push(int elem) {
		arr[++R] = elem;
	}
	int pop(void) {
		if (F == R)
			return -1;
		else
			return arr[++F];
	}
	int size(void) {
		return R - F;
	}
	int empty(void) {
		if (F == R)
			return 1;
		else
			return 0;
	}
	int front(void) {
		if (F == R)
			return -1;
		else
			return arr[F + 1];
	}
	int back(void) {
		if (F == R)
			return -1;
		else
			return arr[R];
	}
};

int main(int argc, char* argv[]) {
	/* Faster */
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	/* Init */
	queue q;

	/* Input */
	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		string str; cin >> str;

		if (str == "push") {
			int elem; cin >> elem;
			q.push(elem);
		}
		else if (str == "pop") {
			cout << q.pop() << '\n';
		}
		else if (str == "size") {
			cout << q.size() << '\n';
		}
		else if (str == "empty") {
			cout << q.empty() << '\n';
		}
		else if (str == "front") {
			cout << q.front() << '\n';
		}
		else if (str == "back") {
			cout << q.back() << '\n';
		}
	}

	/* End */
	return 0;
}

/* 원형 큐 이용 안함 */
/* 10845 문제와 동일 (입력값 크기 차이) */