[BAEKJOON] 10866번 : 덱

문 제

 

소 스  코 드

#include <iostream>
#include <string>

template<typename T>
class NODE {
private:
	T		value;			// 값
	NODE*	next;			// 다음
	NODE*	prev;			// 이전

public:
	NODE() = delete;
	NODE(T v, NODE * n, NODE *p) : value{ v }, next{ n }, prev{ p } {}
	~NODE() {};

public:
	void SetNext(NODE<T> * n)	 { next = n; }
	void SetPrev(NODE<T> * p)	 { prev = p; }
	NODE* GetNext() const	 { return next; }
	NODE* GetPrev() const	 { return prev; }
	T GetValue() const		 { return value; }

};

template<typename T>
class DEQUE {
private:
	NODE<T>* head;
	NODE<T>* tail;
	int size;

public:
	DEQUE() : head{ nullptr }, tail{ nullptr }, size{ 0 } {}
	~DEQUE() {
		NODE<T>* temp_0{ head };
		while (nullptr != temp_0) {
			NODE<T> * temp_1{ temp_0->GetNext() };
			delete temp_0;
			temp_0 = temp_1;
		}

	}

public:
	void Push_Front(const T& v);
	void Push_Back(const T& v);

	int Pop_Front();
	int Pop_Back();

	int Size() const;

	bool Empty() const;

	int Front() const;
	int Back() const;
};


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

	int N, Index;
	std::string s;
	DEQUE<int> dq;
	std::cin >> N;
	for (int i = 0; i < N; ++i) {
		std::cin >> s;
		if ('p' == s[0]) {
			if ('u' == s[1]) {
				std::cin >> Index;
				if ('f' == s[5]) {
					// PUSH FRONT
					dq.Push_Front(Index);
				}
				else {
					// PUSH BACK
					dq.Push_Back(Index);
				}
			}
			else {
				if ('f' == s[4]) {
					// POP FRONT
					std::cout << dq.Pop_Front() << '\n';
				}
				else {
					// POP BACK
					std::cout << dq.Pop_Back() << '\n';
				}
			}
		}
		else if ('s' == s[0]) {
			std::cout << dq.Size() << '\n';
		}
		else if ('f' == s[0]) {
			std::cout << dq.Front() << '\n';
		}
		else if ('e' == s[0]) {
			std::cout << dq.Empty() << '\n';
		}
		else if ('b' == s[0]) {
			std::cout << dq.Back() << '\n';
		}
		else {
			std::cout << " INPUT Error \n";
		}
	}



	return 0;
}

template<typename T>
void DEQUE<T>::Push_Front(const T & v)
{
	NODE<T>* temp{ new NODE<T>(v, head, nullptr) };
	if (DEQUE<T>::Empty()) tail = head = temp;
	else {
		head->SetPrev(temp);
		head = temp;
	}
	++size;

}

template<typename T>
void DEQUE<T>::Push_Back(const T & v)
{
	NODE<T>* temp{ new NODE<T>(v, nullptr, tail) };
	if (DEQUE<T>::Empty()) tail = head = temp;
	else {
		tail->SetNext(temp);
		tail = temp;
	}
	++size;
}

template<typename T>
int DEQUE<T>::Pop_Front()
{
	if (DEQUE<T>::Empty()) return -1;
	NODE<T> *temp{ head };
	T value{ head->GetValue() };
	if (tail == head) head = tail = nullptr;
	else {
		head = temp->GetNext();
		head->SetPrev(nullptr);
	}
	if(nullptr != temp) delete temp;
	--size;
	return value;
}

template<typename T>
int DEQUE<T>::Pop_Back()
{
	if (DEQUE<T>::Empty()) return -1;
	NODE<T> *temp{ tail };
	T value{ tail->GetValue() };
	if (tail == head) head = tail = nullptr;
	else {
		tail = temp->GetPrev();
		tail->SetNext(nullptr);
	}
	if (nullptr != temp) delete temp;
	--size;
	return value;
}

template<typename T>
int DEQUE<T>::Size() const
{
	return size;
}

template<typename T>
bool DEQUE<T>::Empty() const
{
	if (1 > size) return true;
	else		  return false;
}

template<typename T>
int DEQUE<T>::Front() const
{
	if (nullptr == head) return -1;
	return head->GetValue();
}

template<typename T>
int DEQUE<T>::Back() const
{
	if (nullptr == tail) return -1;
	return tail->GetValue();
}

 

풀 이

 

• [18258번] 큐 2 Queue와 다르게 단일 연결 리스트가 아닌 이중 연결 리스트로 구현이 되었다.
  덱의 경우 push_front, push_back, pop_front, pop_back으로 앞쪽과 뒷쪽에서 추가, 제거가 가능하도록 만들어진 
  자료 구조 이기 때문에, Queue와 다르게 다른 방향에서 추가하기 위하여 노드의 이중에서 연결이 가능하도록
  만들어 져야 한다.

 

출 력 값

 

 

문 제  출 처

문제 링크 : [ BAEKJOON ] :  https://www.acmicpc.net/problem/10866

10866번: 덱