[백준 C++] 10866 덱

문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

push X: 정수 X를 스택에 넣는 연산이다.
pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 스택에 들어있는 정수의 개수를 출력한다.
empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

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

https://www.acmicpc.net/problem/10828

풀이

포인터를 이용하여 노드단위로 덱을 구성하였다.
가장먼저 노드 클래스이다.

prev, next포인터로 인접한노드들과 연결할것이다.

아래는 덱클래스 본체이다.

제네릭타입을 이용하여 노드와 덱클래스를 구현했는데, 생성자에는 제네릭을 사용하지않는다.

1. push_front / push_back
   
   덱에 처음 데이터를 저장시에는 꼬리노드와 머리노드를 같게 1번과정을,
   덱에 데이터가있던경우, 헤드포인터가 이전최상위 노드를 가리키고있으므로 이 노드의 다음노드를 새로만든노드로 지정하고
   다시 해드노드를 이 노드로 재설정하는과정이다.
   
   
2. pop_front / pop_back
   
   각각 헤드, 테일 노드를 삭제할노드로 지정하고,
   각각의 이전, 다음노드로 헤드, 테일노드를 재설정해주면된다.
   
   
3. empty / size / front / back
   
   
   
4. 마지막 입력받는 부분
   
   문자열을 %s 로 받고, strcmp로 받은문자열을 비교했다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
//제네릭타입으로 구현
template <typename T>
class Node {
public:
	T data = NULL;
	Node<T>* prev = nullptr, * next = nullptr;
	//생성자에는 제네릭X
	Node(T data,
		Node<T>* prev = nullptr,
		Node<T>* next = nullptr)
		: data(data), prev(prev), next(next) {}
};

template <typename T>
class Deque {
private:
	int dataSize = 0;
	Node<T>* tail = nullptr, * head = nullptr;
public:
	//생성자에는 제네릭X
	Deque() {}
	~Deque() {}
	void push_front(const T data);
	void push_back(const T data);
	T pop_front();
	T pop_back();
	T front() const;
	T back() const;
	bool empty() const;
	int size() const;
};

template <class T>
void Deque<T>::push_front(const T data) {
	if (empty()) {
		head = new Node<T>(data);
		tail = head;
	}
	else {
		Node<T>* newNode = new Node<T>(data, head, nullptr);
		head->next = newNode;
		head = newNode;
	}
	dataSize++;
}

template <class T>
void Deque<T>::push_back(const T data) {
	if (empty()) {
		head = new Node<T>(data);
		tail = head;
	}
	else {
		Node<T>* newNode = new Node<T>(data, nullptr, tail);
		tail->prev = newNode;
		tail = newNode;
	}
	dataSize++;
}

template <class T>
T Deque<T>::pop_front() {
	if (empty())
		return -1;
	T data = front();

	Node<T>* delNode = head;
	head = head->prev;
	delete delNode;
	dataSize--;

	if (dataSize == 0)
		head = nullptr;
	return data;
}

template <class T>
T Deque<T>::pop_back() {
	if (empty())
		return -1;
	T data = back();

	Node<T>* delNode = tail;
	tail = tail->next;
	delete delNode;
	dataSize--;

	if (dataSize == 0)
		tail = nullptr;
	return data;
}

template <class T>
bool Deque<T>::empty() const {
	return dataSize == 0;
}

template <class T>
int Deque<T>::size() const {
	return dataSize;
}
template <class T>
T Deque<T>::front() const {
	if (empty())
		return -1;
	return head->data;
}

template <class T>
T Deque<T>::back() const {
	if (empty())
		return -1;
	return tail->data;
}

int main(int n, int num) {
	scanf("%d", &n);
	Deque<int> d;
	for (int i = 0; i < n; i++) {
		char c[12]; //정수앞 공백까지 11자 + \0 = 12
		scanf("%s", c);
		if (!strcmp(c, "push_front")) {
			scanf("%d", &num);
			d.push_front(num);
		}
		else if (!strcmp(c, "push_back")) {
			scanf("%d", &num);
			d.push_back(num);
		}
		else if (!strcmp(c, "pop_front")) {
			printf("%d\n", d.pop_front());
		}
		else if (!strcmp(c, "pop_back")) {
			printf("%d\n", d.pop_back());
		}
		else if (!strcmp(c, "size")) {
			printf("%d\n", d.size());
		}
		else if (!strcmp(c, "empty")) {
			printf("%d\n", d.empty() ? 1 : 0);
		}
		else if (!strcmp(c, "front")) {
			printf("%d\n", d.front());
		}
		else if (!strcmp(c, "back")) {
			printf("%d\n", d.back());
		}
	}
	return 0;
}