10866번: 덱

문제:

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

명령은 총 여덟 가지이다.

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

입력:

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

풀이:

• 이 문제는 이전에 풀었던 #10828: 스택과 #10845: 큐를 참고하면 쉽게 풀 수 있다. push_front는 모든 data들을 오른쪽으로 한칸 옮긴 뒤 0번째에다가 넣는 방식으로 구현하면 된다. push_back은 이전에 위에 두 문제를 참고하여 만들고 pop_front는 큐의 방식을 참고하여 풀면 되며 pop_back은스택에서 사용한 방식을 이용하여 풀면 된다.

코드:

#include <iostream>

using namespace std;

int n, deque[10000] = {}, back_idx = -1;

void push_front(int number){
	if(back_idx != -1){
		//모든 값들 한칸 오른쪽으로 이동
		for(int i = back_idx; i > -1; i--){
			deque[i+1] = deque[i];
		}
	}
	deque[0] = number;
	back_idx++;
	return;
}

void push_back(int number){
	for(int i = 0; i < n; i++){
		if(deque[i]==0){
			deque[i] = number;
			back_idx = i;
			break;
		}
		else continue;
	}
	return;
}

void pop_front(){
	if(back_idx == -1) cout << -1 << "\\n";
	else{
		cout<< deque[0] << "\\n";
		//pop한 이후 앞으로 값들을 하나씩 땡겨오는 반복문
		for(int i = 0; i < back_idx; i++){
			deque[i] = deque[i+1];
			deque[i+1] = 0;
		}
		back_idx--;
		//비웠을 경우에 마지막 남은 값까지 0으로 처리
		if(back_idx == -1) deque[0] = 0;
	}
	return;
}
void pop_back(){
	if(back_idx == -1) cout << -1 << "\\n";
	else{
		cout<< deque[back_idx] << "\\n";
		deque[back_idx] = 0;
		back_idx--;
	}
	return;
}

void size(){
	cout << back_idx+1 << "\\n";
	return;
}

void empty(){
	if(back_idx == -1) cout << 1 <<"\\n";
	else cout << 0 <<"\\n";
	return;
}

void front(){
	if(back_idx == -1) cout << -1 <<"\\n";
	else{
		cout<< deque[0] << "\\n";
	}
	return;
}

void back(){
	if(back_idx == -1) cout << -1 <<"\\n";
	else{
		cout<< deque[back_idx] << "\\n";
	}
	return;
}

int main(void){
	cin >> n;
	for(int i = 0; i < n; i++){
		string temp;
		cin >> temp;
		if(temp == "push_front"){
			int number;
			cin >> number;
			push_front(number);
		}
		else if(temp == "push_back"){
			int number;
			cin >> number;
			push_back(number);
		}
		else if(temp == "pop_front") pop_front();
		else if(temp == "pop_back") pop_back();
		else if(temp == "size") size();
		else if(temp == "empty") empty();
		else if(temp == "front") front();
		else if(temp == "back") back();
	}
	
}