백준 / 덱(Deque) / 10866번 / 덱 / C++

문제

정수를 저장하는 덱(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보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

예제 입력 1 

15

push_back 1

push_front 2

front

back

size

empty

pop_front

pop_back

pop_front

size

empty

pop_back

push_front 3

empty

front

예제 출력 1 

2

1

2

0

2

1

-1

0

1

-1

0

3

예제 입력 2 

22

front

back

pop_front

pop_back

push_front 1

front

pop_back

push_back 2

back

pop_front

push_front 10

push_front 333

front

back

pop_back

pop_back

push_back 20

push_back 1234

front

back

pop_back

pop_back

예제 출력 2 

-1

-1

-1

-1

1

1

2

2

333

10

10

333

20

1234

1234

20

 

#include <iostream>
using namespace std;

class Deque {
private:
	int* deque = {};
	int begin, end;
public:
	Deque(int n) {
		deque = new int[n];
		begin = -1;
		end = -1;
	}

	void push_front(int num);
	void push_back(int num);
	void pop_front();
	void pop_back();
	void size();
	bool empty();
	void front();
	void back();

	~Deque() {
		delete[] deque;
	}
};

void Deque::push_front(int num) {
	if (empty()) {
		begin = 0;
		end = 0;
		deque[begin] = num;
	}
	else {
		for (int i = end; i >= begin; i--) {
			deque[i + 1] = deque[i];
		}
		deque[begin] = num;
		end++;
	}
}

void Deque::push_back(int num) {
	if (empty()) {
		begin = 0;
		end = 0;
		deque[begin] = num;
	}
	else {
		end++;
		deque[end] = num;
	}
}

void Deque::pop_front() {
	if (empty()) {
		cout << -1 << endl;
	}
	else {
		cout << deque[begin] << endl;
		deque[begin] = NULL;
		begin++;
	}
}

void Deque::pop_back() {
	if (empty()) {
		cout << -1 << endl;
	}
	else {
		cout << deque[end] << endl;
		deque[end] = NULL;
		end--;
	}
}

void Deque::size() {
	if (empty()) {
		cout << 0 << endl;
	}
	else {
		cout << end - begin + 1 << endl;
	}
}

bool Deque::empty() {
	if (begin == -1 || begin > end) {
		return true;
	}
	else {
		return false;
	}
}

void Deque::front() {
	if (empty()) {
		cout << -1 << endl;
	}
	else {
		cout << deque[begin] << endl;
	}
}

void Deque::back() {
	if (empty()) {
		cout << -1 << endl;
	}
	else {
		cout << deque[end] << endl;
	}
}

int main() {
	int n;
	cin >> n;
	Deque d(n);

	for (int i = 0; i < n; i++) {
		string cmd;
		cin >> cmd;

		if (cmd == "push_front") {
			int num;
			cin >> num;

			d.push_front(num);
		}

		else if (cmd == "push_back") {
			int num;
			cin >> num;

			d.push_back(num);
		}

		else if (cmd == "pop_front") {
			d.pop_front();
		}

		else if (cmd == "pop_back") {
			d.pop_back();
		}

		else if (cmd == "size") {
			d.size();
		}

		else if (cmd == "empty") {
			cout << d.empty() << endl;
		}

		else if (cmd == "front") {
			d.front();
		}

		else if (cmd == "back") {
			d.back();
		}
	}

	return 0;
}

---

스택과 큐를 구현해보았다면 단순하게 할 수 있다.

왜냐하면 DEQUE = Double Ended QUEue 이기 때문이다.

한마디로 큐가 한쪽만 연산을 했었다면, 덱은 큐가 양쪽이 다 뚫려있다고 생각하면 된다.

물론 stl deque을 이용하는 방법도 있지만 그냥 짜보았다.

 

스택과 큐에서는 사용하지 않았던 클래스의 생성자와 소멸자를 이용해보았다.

그리고 덱의 크기도 동적으로 할당받아서 했다.

 

다만 한가지 아쉬웠던 것은 nullptr를 써보고싶었는데 포인터에 익숙하지 않아서 쓰는데 실패했다.

C++에서는 이제 NULL보단 nullptr를 쓰는게 좋다고한다.

NULL을 들여다보면 단지 #define NULL 0 과 같다.

따라서 만약 덱에 0이있다면 숫자 0과 NULL을 구분할 수가 없다.

하지만 nullptr는 말그대로 null을 가리키는 포인터이기 때문에 가독성도 좋고 좋은 효율의 코드를 작성할 수 있다.

 

그리고 stl deque에 대해서 이야기해보면, stl vector와 비슷한점이 많다고 한다.

인덱스로도 접근할 수 있고, erase 메서드도 지원한다고 한다.

그래서 양쪽으로 접근해야 할땐 vector대신 deque를 쓰면 좋다고한다.

다른점은 vector는 메모리상에 연속적으로 저장되어 있지만, deque는 아니라고 한다.

(이건 운영체제나 컴퓨터구조에서 알아보자...)