백준 28279 - 덱 2

덱(Deque) 자료구조에 대해 이해하고 있어야 해결할 수 있는 문제입니다. 만약 아직 큐(Queue) 자료구조를 모른다면 먼저 큐에 대해 학습하고 이 문제에 도전하시는 것을 추천드립니다.

덱 자료구조는 큐 자료구조의 형태를 띄지만 양 끝에서 삽입과 삭제가 가능하다는 특징이 있습니다.

저는 덱 클래스를 하나 직접 만들어 구현했습니다. 백준 문제를 풀기 위해 만들어서 int 자료형밖에 되지 않지만 템플릿을 활용하면 더 확장성있는 형태의 덱 클래스로 만들 수 있을 듯 합니다.

#include <iostream>

class Deque			// 양방향 삽입, 삭제가 가능한 queue
{
public:
	Deque(int n);
	~Deque();

	void Add_Front(const int val);
	void Add_Rear(const int val);

	int Delete_Front();
	int Delete_Rear();

	int Get_Front();
	int Get_Rear();

	int Size() const
	{
		int size = _front - _rear;
		int temp = size >> 31;
		return (size ^ temp) + (temp & 1);
	}

	friend std::ostream& operator << (std::ostream& os, const Deque& deque)
	{
		int size = deque.Size();
		if (size == 0) return os;

		for (int i = deque._front -1 ; i >= deque._rear; i--)
			os << deque._deque[i % deque._maxSize] << " ";

		return os;
	}

private:
	int* _deque;

	int _front;
	int _rear;

	int _maxSize = 0;
};

Deque::Deque(int n)
{
	_deque = new int[n];

	for (int i = 0; i < n; i++)
		_deque[i] = -1;

	_front = n - 1;
	_rear = n - 1;

	_maxSize = n;
}

Deque::~Deque()
{
	delete[] _deque;
}

void Deque::Add_Front(const int val)
{
	_deque[_front % _maxSize] = val;
	_front++;
}

void Deque::Add_Rear(const int val)
{
	_rear--;
	_deque[_rear % _maxSize] = val;
}

int Deque::Delete_Front()
{
	int result = -1;
	if (Size() == 0)
		result = -1;
	else
	{
		_front--;
		result = _deque[_front % _maxSize];
		_deque[_front % _maxSize] = -1;
	}

	return result;
}

int Deque::Delete_Rear()
{
	int result = -1;
	if (Size() == 0)
		result = -1;
	else
	{
		result = _deque[_rear % _maxSize];
		_deque[_rear % _maxSize] = -1;
		_rear++;
	}

	return result;
}

int Deque::Get_Front()
{
	int result = _deque[(_front - 1) % _maxSize];
	if (Size() == 0)
		result = -1;

	return result;
}

int Deque::Get_Rear()
{
	int result = _deque[_rear % _maxSize];
	if (Size() == 0)
		result = -1;

	return result;
}

int main()
{
	std::cin.tie(NULL);
	std::ios_base::sync_with_stdio(false);

	int n;
	std::cin >> n;

	Deque deque(n);

	for (int i = 0; i < n; i++)
	{
		int temp;
		std::cin >> temp;
		int x;
		switch (temp)
		{
		case 1:
		{
			std::cin >> x;
			deque.Add_Front(x);
		}
		break;
		case 2:
		{
			std::cin >> x;
			deque.Add_Rear(x);
		}
		break;
		case 3:
			std::cout << deque.Delete_Front() << "\n";
		break;
		case 4:
			std::cout << deque.Delete_Rear() << "\n";
		break;
		case 5:
			std::cout << deque.Size() << "\n";
		break;
		case 6:
		{
			int size = deque.Size();
			if (size == 0)
				std::cout << "1\n";
			else
				std::cout << "0\n";
		}
		break;
		case 7:
			std::cout << deque.Get_Front() << "\n";
		break;
		case 8:
			std::cout << deque.Get_Rear() << "\n";
		break;
		default:
			break;
		}
	}

	return 0;
}