template <typename Element>

class Deque
{
	private:
		NodePtr header; //pointer to the header
		NodePtr trailer; //pointer to the trailer
		int noofelements;
	
	struct Node
	{
		Element data;
		Node *prev;
		Node *next;
		Node(const Element & d = Element(), Node *p = NULL, Node *n = NULL): data(d), prev(p), next(n) {}
	}
	
	Node *NodePtr; //pointer to node
	
	public:
		Deque() 
		{
			header = new Node();
			trailer = new Node();
			header -> next = trailer; //trailer follows header
			trailer -> prev = header; //header precedes trailer
			noofelements = 0; 
		}
		
		void push(Element & x)
		{
			NodePtr oldFirst = header -> next;
			NodePtr t = new Node(x, header, oldFirst); //new node to insert
			oldFirst -> prev = t;
			header -> next = t;
			noofelements++;
		}
		
		Element pop()
		{
			NodePtr old = header -> next;
			NodePtr newFirst = old -> next;
			header -> next = newFirst;
			newFirst -> prev = header;
			noofelements--;
			delete old;
		}
		
		void inject(Element & x)
		{
			NodePtr oldLast = trailer -> prev;
			NodePtr t = new Node(x, trailer, oldLast);
			oldLast -> next = t;
			trailer -> prev = t;
			noofelements++;
		}
		
		Element eject() 
		{
			NodePtr old = trailer -> prev; //node to remove
			NodePtr newLast = old -> prev;
			trailer -> prev = newLast;
			newLast -> next = trailer;
			noofelements--;
			delete old;
		}
}

This group also gave pictures of their thinking about how to rearrange
the pointers for each method.  A good strategy overall when dealing with
linked structures.