[C++] 백준 10866번 덱

1. 문제이해

10866번: 덱 (acmicpc.net)

10866번: 덱

 

위와 같은 8가지의 명령어를 수행하는 덱을 구현하는 것이 목표이다.

 

 

 

2. 문제풀이

 

위 8가지의 명령어를 수행하는 덱을 구현하면 되는 간단한 문제이다.

덱(deque)이란, double-ended queue의 약자로, 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조이다.

두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생 시킬 수 있으며,

큐와 스택을 합친 구조로도 볼 수 있다.

덱의 구조를 그림으로 보면 다음과 같다.

 

출처 : 네이버 블로그 Sooftware님

 

위 구조에서 볼 수 있듯이, 덱은 양쪽 끝(front, rear/back)에서 삽입과 삭제가 가능하다.

덱 또한 큐, 스택과 마찬가지로 C++에 구현이 되어있다. (<deque>)

덱의 기본적인 함수들은 다음과 같다.

(문제에서 정의된 8가지 명령어들)

 

1. deque <데이터타입> 이름; 형태로 선언해준다.

ex) deque <int> dq;

 

2. dq.push_front(element);

: 덱의 앞부분에 element(원소)를 추가한다.

 

3. dq.push_back(element);

: 덱의 뒷부분에 element(원소)를 추가한다.

 

4. dq.pop_front();

: 덱의 맨 앞의 원소를 삭제한다.

 

5. dq.pop_back();

: 덱의 맨 뒤의 원소를 삭제한다.

 

6. dq.size();

: 덱의 사이즈(원소의 개수)를 반환한다.

 

7. dq.empty();

: 덱이 비어있는지를 확인한다.

: 덱이 비어있다면 1(true), 아니라면 0(false)을 반환한다.

 

8. dq.front();

: 덱의 맨 앞의 원소를 반환한다.

 

9. dq.back();

: 덱의 맨 뒤의 원소를 반환한다.

 

 

 

3. 소스코드

#include <iostream>
#include <deque>	// 덱 헤더파일 추가
using namespace std;

int main() {
	deque<int> dq;
	int N;	// 명령어의 개수
	string command;	// 명령어
	int front_num;	// 덱 앞에 들어갈 정수
	int back_num;	// 덱 뒤에 들어갈 정수

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> command;

		// 1. push_front
		if (command == "push_front") {
			cin >> front_num;
			dq.push_front(front_num);
		}

		// 2. push_back
		else if (command == "push_back") {
			cin >> back_num;
			dq.push_back(back_num);
		}

		// 3. pop_front
		else if (command == "pop_front") {
			if (dq.empty() == 1) { // 덱이 비어있다면, -1 출력
				cout << "-1" << endl;
			}
			else {
				cout << dq.front() << endl; // 앞에서 뺄 원소를 먼저 출력
				dq.pop_front(); // 이후에 pop(삭제)
			}
		}

		// 4. pop_back
		else if (command == "pop_back") {
			if (dq.empty() == 1) { // 덱이 비어있다면, -1 출력
				cout << "-1" << endl;
			}
			else {
				cout << dq.back() << endl; // 뒤에서 뺄 원소를 먼저 출력
				dq.pop_back(); // 이후에 pop(삭제)
			}
		}

		// 5. size
		else if (command == "size") {
			cout << dq.size() << endl;
		}

		// 6. empty
		else if (command == "empty") {
			cout << dq.empty() << endl;
		}

		// 7. front
		else if (command == "front") {
			if (dq.empty() == 1) { // 덱이 비어있다면, -1 출력
				cout << "-1" << endl;
			}
			else {
				cout << dq.front() << endl;
			}
		}

		// 8. back
		else if (command == "back") {
			if (dq.empty() == 1) { // 덱이 비어있다면, -1 출력
				cout << "-1" << endl;
			}
			else {
				cout << dq.back() << endl;
			}
		}
	}

	return 0;
}

명령어의 개수(N)를 입력받은 후, N만큼 for문을 반복한다.

for문 안에는 8가지 덱의 함수들이 구현이 되어있으며,

명령어(command)가 무엇이냐에 따라 다른 작업을 수행한다.

 

1. push_front, 2. push_back의 경우, 원소를 하나 더 입력받아 해당 원소를 각각 덱의 앞, 뒤에 삽입했다.

 

3. pop_front, 4. pop_back의 경우, 덱이 비어있으면 -1을 반환,

그렇지 않으면 각각 맨 앞, 뒤의 원소를 반환 후, pop해주었다.

 

5. size는 덱의 사이즈를 바로 출력해주었고,

6. empty는 덱이 비어있으면 1, 아니면 0을 출력하도록 했다.

(자동적으로 비어있다면 1, 아니면 0을 출력한다.)

 

7. front, 8. back 의 경우에도, 큐가 비어있으면 -1을 출력,

그렇지 않으면 각각의 값을 출력하도록 구현했다.

 

 

---

오늘은 자료구조의 하나인 덱을 구현해보는 연습을 했다.

덱은 사실 처음 구현해보는 건데, 큐나 스택과 거의 유사해서

구현하는데 크게 어렵지 않아서 다행이었다. 😊