struct nood {
    int data;
    nood* next;
    nood* prev;

    nood(int& a):next(NULL), prev(NULL), data(a) {}
    ~nood();
}

class Deck {
public:
    Deck(int n);
    ~Deck();

    void PushEnd(int a);
    void PushBegin(int a);
    int PopEnd();
    int PopBegin();

private:
    int size;
    nood* head;
    nood* tail;
}

Deck:: Deck(int n): size(n), first(NULL), last(NULL) {}
Deck:: ~Deck() {
    nood* tmp;
    while(head) {
        tmp = head;
        head = head->next;
        delete tmp;
    }
    tail = NULL;
    size = 0;
}
void Deck:: PushEnd(int& a) {
    nood* new_nood = new nood(a);
    if (head == NULL) {
        head = tail = new_nood;
    }
    else {
        new_nood->prev = tail;
        tail_next = new_nood;
        tail = new_nood;
    }
    size++;
}
void Deck:: PushBegin(int& a) {
    nood* new_nood = new nood(a);
    if (head == NULL) {
        head = tail = new_nood;
    }
    else {
        head->prev = new_nood;
        new_nood->next = head;
        head = new_nood;
    }
    size++;
}
int Deck:: PopBegin() {
    assert(head != NULL);
    tmp = head->data;
    head = head->next;
    head->prev = NULL;
    size--;
    return tmp;
}
int Deck:: PopEnd() {
    assert(head != NULL);
    tmp = tail->data;
    tail = tail->prev;
    tail_next = NULL;
    size--;
    return tmp;
}