백준 덱(10866) C++ 풀이

알고리즘 영역

자료 구조
덱

문제 해결 아이디어

양방향으로 빠르게 확장시킬 수 있는 자료구조라는 점을 알고 구현을 하면 된다.

코드

#include <iostream>
using namespace std;

class deque
{
private:
	int arr[10001];
	int backIdx = 0;
public:
	void push_front(int x)
	{
		for (int i = backIdx; i > 0; i--)
		{
			arr[i] = arr[i - 1];
		}
		arr[0] = x;
		backIdx++;
	}
	void push_back(int x)
	{
		arr[backIdx] = x;
		backIdx++;
	}
	int pop_front()
	{
		if (empty())
			return -1;

		int temp = arr[0];
		for (int i = 1; i < backIdx; i++)
		{
			arr[i - 1] = arr[i];
		}
		backIdx--;
		return temp;
	}
	int pop_back()
	{
		if (empty())
			return -1;

		backIdx--;
		int temp = arr[backIdx];
		arr[backIdx] = 0;
		return temp;
	}
	int size()
	{
		return backIdx;
	}
	int empty()
	{
		if (backIdx == 0)
			return 1;
		else
			return 0;
	}
	int front()
	{
		if (empty())
			return -1;
		return arr[0];
	}
	int back()
	{
		if (empty())
			return -1;
		return arr[backIdx - 1];
	}
};

int n;

int main()
{
	deque d;

	cin >> n;

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

		if (s == "push_front")
		{
			cin >> num;
			d.push_front(num);
		}
		else if (s == "push_back")
		{
			cin >> num;
			d.push_back(num);
		}
		else if (s == "pop_front")
		{
			cout << d.pop_front() << '\n';
		}
		else if (s == "pop_back")
		{
			cout << d.pop_back() << '\n';
		}
		else if (s == "size")
		{
			cout << d.size() << '\n';
		}
		else if (s == "empty")
		{
			cout << d.empty() << '\n';
		}
		else if (s == "front")
		{
			cout << d.front() << '\n';
		}
		else if (s == "back")
		{
			cout << d.back() << '\n';
		}
	}
}