[백준/C,C++] 10866번: 덱

www.acmicpc.net/problem/10866

10866번: 덱

hackids.tistory.com/3

[백준/C,C++] 10828번: 스택

hackids.tistory.com/42

[백준/C,C++] 18258번: 큐 2

10828번: 스택과 18258번: 큐 2와 비슷한 문제인데요. 덱의 개념을 익히고 직접 구현해보는 문제입니다. 스택과 큐가 합쳐진 형태가 덱이라고 생각하시면 쉬운데, 직접 구현할 때 헷갈리는 부분이 몇 있습니다. 큐와 같이 인덱스가 front, rear 두 개 존재하는데, 두 곳 모두에서 삽입과 삭제 연산이 이루어집니다. 인덱스의 관리 자체는 원형 큐와 유사하게 이루어집니다.

void Deque::push_front(int n)
{
	if (full()) cout << "덱이 가득 차 " << n << "을 덱에 삽입할 수 없습니다." << endl;
	else {
		deque[f] = n;
		f = (f - 1 + SIZE) % SIZE;
	}
}

void Deque::push_back(int n)
{
	if (full()) cout << "덱이 가득 차 " << n << "을 덱에 삽입할 수 없습니다." << endl;
	else {
		r = (r + 1) % SIZE;
		deque[r] = n;
	}
}

push 부분입니다. front는 (f - 1 + SIZE) % SIZE, r은 (r + 1) % SIZE의 식으로 다음 인덱스를 가리키게 하는데요. % 연산을 통해 쉽게 말해 원형으로 인덱스를 가리킨다고 보시면 됩니다. front는 0, 9999, 9998 ... 0 다시 9999 이런 순으로 돌 거고 rear는 0, 1, 9999 ... 0 다시 1 이런 순으로 돌게 될 겁니다. front에 나머지 연산 전 SIZE를 한번 더해주는 건 음수가 되었을 때 SIZE를 더해줌으로써 다시 끝쪽부터 순환되게 하기 위함입니다. 여기서 또 보셔야 할 것은 push_front와 push_back 간 인덱스값 갱신, 값 삽입의 과정이 서로 달라야 한다는 것입니다. f와 r이 같은 곳을 가리킬 때 같은 곳에 값을 넣는 것을 방지하기 위함입니다.

int Deque::pop_front()
{
	if (empty()) return -1;
	else {
		f = (f + 1) % SIZE;
		return deque[f];
	}
}

int Deque::pop_back()
{
	if (empty()) return -1;
	else {
		int ret = deque[r];
		r = (r - 1 + SIZE) % SIZE;
		return ret;
	}
}

pop 부분인데요. 특별한 건 없고 push 부분과 마찬가지로 인덱스값 갱신, 값 삽입의 과정을 push의 순서와 맞게 코딩해주시면 됩니다.

int Deque::size()
{
	return (r - f + SIZE) % SIZE;
}

bool Deque::full()
{
	if (size() == SIZE - 1) return true;
	else return false;
}

bool Deque::empty()
{
	if (f == r) return true;
	else return false;
}

size, full, empty 함수 부분입니다. full에서 size() == SIZE가 아닌 SIZE - 1로 식을 써놓은 이유는 마지막 한 칸을 비우지 않으면 front와 rear가 가리키는 지점이 같아지기 때문입니다.

#include<iostream>
#include<string>

using namespace std;

#define SIZE 10000

class Deque
{
private:
	int* deque = new int[SIZE];
	int f = 0;
	int r = 0;
public:
	void push_front(int n);
	void push_back(int n);
	int pop_front();
	int pop_back();
	int size();
	bool full();
	bool empty();
	int front();
	int back();
};

void Deque::push_front(int n)
{
	if (full()) cout << "덱이 가득 차 " << n << "을 덱에 삽입할 수 없습니다." << endl;
	else {
		deque[f] = n;
		f = (f - 1 + SIZE) % SIZE;
	}
}

void Deque::push_back(int n)
{
	if (full()) cout << "덱이 가득 차 " << n << "을 덱에 삽입할 수 없습니다." << endl;
	else {
		r = (r + 1) % SIZE;
		deque[r] = n;
	}
}

int Deque::pop_front()
{
	if (empty()) return -1;
	else {
		f = (f + 1) % SIZE;
		return deque[f];
	}
}

int Deque::pop_back()
{
	if (empty()) return -1;
	else {
		int ret = deque[r];
		r = (r - 1 + SIZE) % SIZE;
		return ret;
	}
}

int Deque::size()
{
	return (r - f + SIZE) % SIZE;
}

bool Deque::full()
{
	if (size() == SIZE - 1) return true;
	else return false;
}

bool Deque::empty()
{
	if (f == r) return true;
	else return false;
}

int Deque::front()
{
	if (empty()) return -1;
	else return deque[(f + 1) % SIZE];
}

int Deque::back()
{
	if (empty()) return -1;
	else return deque[r];
}

int main(void)
{
	Deque deque;
	int n; cin >> n;

	int num;
	for (int i = 0; i < n; i++) {
		string str; cin >> str;
		if (str == "push_front") {
			cin >> num; deque.push_front(num);
		}
		else if (str == "push_back") {
			cin >> num; deque.push_back(num);
		}
		else if (str == "pop_front") {
			cout << deque.pop_front() << "\n";
		}
		else if (str == "pop_back") {
			cout << deque.pop_back() << "\n";
		}
		else if (str == "size") {
			cout << deque.size() << "\n";
		}
		else if (str == "empty") {
			cout << deque.empty() << "\n";
		}
		else if (str == "front") {
			cout << deque.front() << "\n";
		}
		else {
			cout << deque.back() << "\n";
		}
	}

	return 0;
}