#include <thread>
#include <list>
#include <mutex>
#include <algorithm>
#include <stack>
#include <exception>
#include <memory>

struct empty_stack : std::exception {
    const char* what() const noexcept;
};

template<typename T>
class thread_safe_stack {
private:
    std::stack<T> data;
    mutable std::mutex m;
public:
    thread_safe_stack() {}
    // copy construct
    thread_safe_stack(const thread_safe_stack& other) {
        std::lock_guard<std::mutex> guard(other.m);
        data = other.data;
    }
    
    thread_safe_stack& operator=(const thread_safe_stack& other) = delete;
    
    void push(T& new_value) {
        std::lock_guard<std::mutex> guard(m);
        data.push(std::move(new_value));
    }
    
    std::shared_ptr<T> pop() {
        std::lock_guard<std::mutex> guard(m);
        if (data.empty()) throw empty_stack();
        std::shared_ptr<T> const res(std::make_shared<T>(data.top()));
        data.pop();
        return res;
    }
    
    void pop(T& value) {
        std::lock_guard<std::mutex> guard(m);
        if (data.empty()) throw empty_stack();
        value = data.top();
        data.pop();
    }
    
    bool empty() const {
        std::lock_guard<std::mutex> guard(m);
        return data.empty();
    }
    
};