#include <iostream>

#include <fstream>

#include <string>

 

using namespace std;

 

// modify this LinkedNode class

template<class T>

class LinkedNode 

{

public:

   T value;

   LinkedNode* next;

   LinkedNode* prev;

};

 

// modify this Deque class

template<class T>

class Deque 

{

private:

   LinkedNode<T>* head;

   LinkedNode<T>* tail;

public:

   Deque();

   void push_front(T v);

   void push_back(T v);

   T pop_front();

   T pop_back();

};

 

// modify this Constructor

template<class T>

Deque<T>::Deque(){

    head = new LinkedNode<T>();

tail = new LinkedNode<T>();

 

head->next = tail;

tail->prev = head;

}

 

// implement Push front

template<class T>

void Deque<T>::push_front(T v){

LinkedNode<T>* newNode=new LinkedNode<T>();

newNode->value=v;

newNode->next=head->next;

newNode->next->prev=newNode;

head->next=newNode;

newNode->prev=head;

}

 

// implement Push back

template<class T>

void Deque<T>::push_back(T v){

LinkedNode<T>* newNode=new LinkedNode<T>();

newNode->value=v;

newNode->prev=tail->prev;

newNode->next=tail;

newNode->prev->next=newNode;

tail->prev=newNode;

}

 

// implement Pop front

template<class T>

T Deque<T>::pop_front(){

T popvalue=head->next->value;

head=head->next;

head->prev=NULL;

return popvalue;

}

 

// implement Pop back

template<class T>

T Deque<T>::pop_back(){

T popvalue=tail->prev->value;

tail=tail->prev;

tail->next=NULL;

return popvalue;

}

int main()

{

 

int intData[10];

double doubleData[10];

string stringData[10];

 

Deque<int> intDeq;

Deque<double> doubleDeq;

Deque<string> stringDeq;

 

 

ifstream ifs("inputfile.txt");

ofstream ofs("outputfile.txt");

 

 

int i;

for (i=0; i<10; i++)

ifs>>intData[i];

for (i=0; i<10; i++)

ifs>>doubleData[i];

for (i=0; i<10; i++)

ifs>>stringData[i];

 

for(int i=0; i<10; i++) {

if(i%2) {

intDeq.push_back(intData[i]);

doubleDeq.push_back(doubleData[i]);

stringDeq.push_back(stringData[i]);

} else {

intDeq.push_front(intData[i]);

doubleDeq.push_front(doubleData[i]);

stringDeq.push_front(stringData[i]);

}

}

 

for(int i=0; i<10; i++)

ofs << intDeq.pop_front() << " ";

ofs << endl;

 

for(int i=0; i<10; i++)

ofs << doubleDeq.pop_back() << " ";

ofs << endl;

 

for(int i=0; i<10; i++) {

if(i%2) ofs << stringDeq.pop_back() << " ";

else ofs << stringDeq.pop_front() << " ";

}

ofs << endl;

ifs.close();

ofs.close();

return 0;

}