#ifndef stack_h
#define stack_h 1

#include <atomic>
#include <exception>

template<class T> class stack
{
public:
	using empty = std::exception;

	stack(): head{nullptr} {}

	~stack() { while (head) pop(); }

	void push(const T& t)
	{
		node *n = new node{head, t};
		while (!head.compare_exchange_strong(n->next, n))
			n->next = head;
	}

	T pop()
	{
		node *n;
		do {
			n = head;
			if (!n)
				throw empty();
		} while (!head.compare_exchange_strong(n, n->next));
		T t = n->data;
		delete n;
		return t;
	}

private:
	struct node
	{
		node *next;
		T     data;
	};

	std::atomic<node*> head;
};

#endif // stack_h