template <typename Element>

class Deque
{
	private:
		struct Node
		{
			Element data;
			Node *next;
			Node *previous;
			Node(const Element & d = Element(), Node *n = NULL; Node *p = NULL) data(d), previous(p), next(n) {}
		};
		Node *start;
		Node *end;
		
	public:
		Deque() 
		{
			start = new Node;
			end = new Node;
			start -> next = end;
			end -> previous = start; 
		}
		
		void push(Element & x)
		{
			newNext = start -> next;
			newPrev = start;
			Node *newNode = new Node(x, newNext, newPrev);
			start -> next -> previous = newNode;
			start -> next = newNode;
		}
		
		Element pop()
		{
			if(start -> next == end)
			{
				cout << "The deque is empty" << endl;
				return 0;
			}
			else 
			{
				element x = start -> next -> data;
				start -> next = start -> next -> next;
				delete start -> next -> previous;
				start -> next -> previous = start;
				return x;
			}
		}
		
		void inject(Element & x)
		{
			newNext = end;
			newPrev = end -> previous;
			Node *newNode = new Node(x, newNext, newPrev);
			end -> previous -> next = newNode;
			end -> previous = newNode;
		}
		
		Element eject() 
		{
			if(end -> previous == start)
			{
				cout << "The deque is empty" << endl;
				return 0;
			}
			else 
			{
				element x = end -> previous -> data;
				end -> previous = end -> previous -> previous;
				delete end -> previous -> next;
				end -> previous -> next = end;
				return x;
			}
		}
		
	private:
		Node *newNext;
		Node *new Prev;
}