#include<iostream>

using namespace std;

template<typename T>
struct Node{
    Node<T>* prev;
    Node<T>* next;
    T value;
    Node<T>(T value) : prev(nullptr),next(nullptr),value(value) {}
};

template<typename T>
class LinkedDequeue
{
private:
    Node<T>* head;
    Node<T>* tail;
    int size;
//双端队列,队首入队,队首出队,队尾出队,队尾入队,获取队尾队首元素,获取队列长度,打印队列
public:
    LinkedDequeue();
    ~LinkedDequeue();
    void headInsert(T value);
    void headDelete();
    void tailInsert(T value);
    void tailDelete();
    void top();
    void back();
    void getSize();
    void printAllElement();
};

template<typename T>
LinkedDequeue<T>::LinkedDequeue():head(nullptr),tail(nullptr),size(0)
{
}

template<typename T>
LinkedDequeue<T>::~LinkedDequeue()
{
    Node<T>* cur = head;
    while(cur != nullptr){
        Node<T>* temp = cur;
        cur = cur->next;
        delete temp;
    }
}

template<typename T>
void LinkedDequeue<T>::printAllElement(){
    Node<T>* cur = head;
    while(cur != nullptr){
        cout << cur->value << " ";
        cur = cur->next;
    }
    cout << endl;
}

template<typename T>
void LinkedDequeue<T>::headInsert(T value){
    Node<T>* new_node = new Node(value);
    if(size == 0){
        head = new_node;
        tail = new_node;
        size++;
    }else{
    new_node->next = head;
    head->prev = new_node;
    head = new_node;
    size++;
    }
}

template<typename T>
void LinkedDequeue<T>::tailInsert(T value){
    Node<T>* new_node = new Node<T>(value);
    if(size == 0){
        head = new_node;
        tail = new_node;
        size++;
    }else{
    tail->next = new_node;
    new_node->prev = tail;
    tail = new_node;
    size++;
    }
}

template<typename T>
void LinkedDequeue<T>::headDelete(){
    Node<T>* temp = head;
    head = head->next;
    head->prev = nullptr;
    delete temp;
    size--;
}

template<typename T>
void LinkedDequeue<T>::tailDelete(){
    Node<T>* temp = tail;
    tail = tail->prev;
    tail->next = nullptr;
    delete temp;
    size--;
}

//....略

void test0(){
    LinkedDequeue<char> ld;
    ld.tailInsert('S');
    ld.headInsert('I');
    ld.headInsert('B');
    ld.tailInsert('T');
    ld.tailInsert('U');
    ld.printAllElement();
    cout << "------------------------------------" << endl;
    ld.tailDelete();
    ld.headDelete();
    ld.printAllElement();
}