#ifndef STACK_HPP_INCLUDED

#define STACK_HPP_INCLUDED

#include <utility> // std::forward

#include <memory> // std::move

#include <stdexcept> // std::runtime_error

class empty_stack : public std::runtime_error {

public:

empty_stack(std::string const& what_arg) : std::runtime_error{what_arg} {};

};

template<typename T>

class Stack {

public:

Stack() : head{nullptr} {};

~Stack();

template<typename U>

void add(U&&);

T remove();

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

private:

struct Node {

T data;

Node* next;

template<typename U>

Node(U&& d, Node* n) : data{std::forward<U>(d)}, next{n} {};

};

Node* head;

};

template<typename T>

Stack<T>::~Stack() {

// Rewriting functionality of remove here avoids a call to the move

// constructor for each element in the stack. For code golf, use:

// while(!empty()) remove();

while(!empty()) {

auto old_head = head;

head = head->next;

delete old_head;

}

}

template<typename T>

template<typename U>

void Stack<T>::add(U&& t) {

head = new Node{std::forward<U>(t), head};

}

template<typename T>

T Stack<T>::remove() {

if(empty())

throw empty_stack{"Remove called on empty stack."};

auto old_head = head;

auto old_data = std::move(head->data);

head = head->next;

delete old_head;

return old_data;

}

#endif // STACK_HPP_INCLUDED