template <typename T>
class Stack {
public:
  struct Node {
    T data;
    Node *next = nullptr;
    Node(T data) : data(data) {}
    Node(T data, Node *next) : data(data), next(next) {}
  };
  Node *top;
  int size_;

  Stack() : size_(0), top(nullptr) {}

  bool empty() {
    return top == 0;
  }

  void push(T data) {
    if(empty()) {
      top = new Node(data);
      size_++;
    } else {
      top = new Node(data, top);
      size_++;
    }
  }

  T pop() {
    if(!empty()) {
      T ret = top->data;
      Node *tmp = top->next;
      delete top;
      top = tmp;
      size_--;
      return ret;
    }

    return -1;
  }

  int size() {
    return size_;
  }

  ~Stack() {
    if(empty()) return;

    if(size_ == 1) {
      delete top;
      return;
    }

    Node *current = top;
    Node *next;
    while( current != 0 ) {
        next = current->next;
        delete current;
        current = next;
    }
    top = nullptr;

  }