template <class T> class Stack
{
private:
    struct Node
    {
        T value;
        Node* prev;
        Node *next;
    };
    Node *first;
    Node *last;
public:
    Stack();
    Stack(const Stack &L);
    const Stack<T>& operator = (const Stack &L);
    T pop();
    void push(const T val);
    int Size();
    void clear();
    ~Stack();
};

template <class T> Stack<T>::Stack(void)
{
    first = NULL;
    last = NULL;
};

template <class T> Stack<T>::Stack(const Stack &L)
{
    first = NULL;
    last = NULL;
    Node *current = L.first;
    Node *tmp;
    while (current)
    {
        tmp = new Node;
        if (first==NULL)
            first = tmp;
        else
            last->next = tmp;
        tmp->value = current->value;
        tmp->next = NULL;
        tmp->Prev = last;
        last = tmp;
        current = current->next;
    }
}

template <class T> const Stack<T>& Stack<T>::operator = (const Stack &L)
{
    first = NULL;
    last = NULL;
    Node *current = L.first;
    Node *tmp;
    while (current)
    {
        tmp = new Node;
        if (first==NULL)
            first = tmp;
        else
            last->next = tmp;
        tmp->value = current->value;
        tmp->next = NULL;
        tmp->Prev = last;
        last = tmp;
        current = current->next;
    }
    return *this;
}
template <class T> T Stack<T>::pop()
{
    T val = last->value;
    last = last->prev;
    return val;
}
template <class T> void Stack<T>::push(const T val)
{
    Node *tmp = new Node;
    if (first==NULL)
        first = tmp;
    else
        last->next = tmp;
    tmp->value = val;
    tmp->next = NULL;
    tmp->prev = last;
    last = tmp;
};

template <class T> void Stack<T>::clear()
{
    while (first!=NULL)
    {
        Node *tmp = first;
        first = first->next;
        delete tmp;
    }
};

template <class T> Stack<T>::~Stack()
{
    clear();
};