#include <utility>

template<typename T> class stack {
	struct node {
		T value;
		node* next;

		node( T&& v, node* n ) : value(std::move(v)), next(n) {}
	};
	
	node* head;

public:
	stack() : head(nullptr) {}

	~stack() {
		node* next = head;
		while ( next ) {
			node* crnt = next;
			next = crnt->next;
			delete crnt;
		}
	}

	bool empty() const {
		return head == nullptr;
	}

	void push(T&& value) {
		head = new node{ std::move(value), head };
	}

	T pop() {
		node* n = head;
		head = n->next;
		T x = std::move(n->value);
		delete n;
		return x;
	}
};