#include<iostream>
using namespace std;

template<typename T>
struct elem{
	T inf;
	elem * neighbours[2];
};

template<class T>
class Deque
{
public:
	Deque();
	Deque(const Deque &);
	~Deque();
	Deque& operator=(const Deque&);

	void pushBack(const T & value);
	void pushFront(const T & value);

	void popBack();
	void popFront();

	T back() const;
	T front() const;

	bool isEmpty() const;

//	friend ostream& operator<<(ostream&, const Deque&);
//	friend istream& operator>>(istream&, Deque&);
private:
	void pop(int);
	void push(const T &, int);
	T element(int) const;
	elem<T> * link[2];
};

template <typename T>
Deque<T>::Deque()
{
	link[0]= NULL;
	link[1] = NULL;
}

template <typename T>
Deque<T>::~Deque()
{
	while(!isEmpty())
		popFront();
}

template<typename T>
bool Deque<T>::isEmpty() const
{
	return (link[0] == NULL);
}

template<typename T>
void Deque<T>::popFront()
{
	pop(0);
}
template<typename T>
void Deque<T>::popBack()
{
	pop(1);
}

template<typename T>
void Deque<T>::pop(int a)
{
	if ( !isEmpty() && link[a] != link[!a] )
	{
		elem<T> * c = link[a];
		link[a] = link[a]->neighbours[!a];
		delete c;
	}
	else
	{
		delete link[a];
		link[a] = link[!a] = NULL;
	}
}

template<typename T>
void Deque<T>::pushFront(const T & val)
{
	push(val, 1);
}

template<typename T>
void Deque<T>::pushBack(const T & val)
{
	push(val, 1);
}
template<typename T>
void Deque<T>::push(const T & val, int a)
{
	elem<T> * n = new elem<T>();
	n->inf = val;
	n->neighbours[a] = NULL;

	if ( isEmpty() )
	{
		n->neighbours[!a] = NULL;
		link[!a] = link[a] = n;
	}
	else
	{
		n->neighbours[!a] = link[a];
		link[a]->neighbours[a] = n;
		link[a] = n;
	}
}


template<typename T>
T Deque<T>::front() const
{
	return element(1);
}

template<typename T>
T Deque<T>::back() const
{
	return element(0);
}

template<typename T>
T Deque<T>::element(int a) const
{
	return link[!a] -> inf;
}

int main()
{
	Deque<int> d;
	
	
	int all = 50;
	for ( int i = 0 ; i < all ; ++i)
	{
		d.pushBack(i);
	}

	for ( int i = 0; i < 25; ++i )
	{
		cout << d.front() << " ";
		d.popFront();
	}

	while (!d.isEmpty())
	{
		cout << d.back() << " ";
		d.popBack();
	}

	return 0;
}