백준 18258 큐2

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

문제 요약

1. 자료 구조 덱을 구현하는 문제
2. push - 덱에 정수를 넣어준다.
3. pop - 덱 가장 앞에 수를 빼주고, 출력하고, 덱이 비어있으면 -1을 출력한다.
4. size - 덱에 들어있는 정수의 개수를 출력한다.
5. empty - 덱이 비어있으면 1, 아니면 0을 출력한다.
6. front - 덱 가장 앞에 정수를 출력해주고, 덱이 비어있으면 -1을 출력한다.
7. back - 덱 가장 뒤에 있는 정수를 출력해주고, 덱이 비어있으면 -1을 출력한다.

풀이

1. 가장 기본적으로 큐, 덱에 대한 이해가 필요하다.
2. 큐는 FIFO(First In First Out)의 구조를 가진 자료구조이다.
3. 덱은 vector의 단점을 보안하기 위하여 만들어진 container
   3-1 vector는 새로운 원소를 추가 할때 메모리 재할당
   3-2 그 후 이전 원소를 복사, 삽입시 성능 저하가 된다.
   3-3 덱은 메모리 블록을 이용하여 새로운 메모리 블록 할당.
   3-4 front, back 모두 삽입 가능

코드

deque<int> dq;

void push() {
	int t;
	cin >> t;
	dq.push_back(t);
}

int pop() {
	if (dq.empty()) {
		return -1;
	}
	else {
		int t = dq.front();
		dq.pop_front();
		return t;
	}
}

int size() {
	return dq.size();
}

int empty() {
	if (dq.empty()) return 1;
	return 0;
}

int front() {
	if (dq.empty()) return -1;

	int t = dq.front();
	return t;
}

int back() {
	if (dq.empty()) return -1;

	int t = dq.back();
	return t;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);	

	int N;
	cin >> N;

	string t;
	while (N--) {
		cin >> t;
		
		if (t == "push") {
			push();
		}
		else if (t == "pop") {
			cout << pop() << '\n';
		}
		else if (t == "size") {
			cout << size() << '\n';
		}
		else if (t == "empty") {
			cout << empty() << '\n';
		}
		else if (t == "front") {
			cout << front() << '\n';
		}
		else if (t == "back") {
			cout << back() << '\n';
		}
	}

	return 0;
}

후기

1. deque이 아니라 queue이용해서 가장 최근에 push 된 녀석들만 back으로 저장해도 될 것 같다.