/*
 * Portions of this code have been borrowed from
 * http://ww3.datastructures.net/
 * Copyright © 2003, Michael T. Goodrich, Roberto Tamassia, and David M. Mount. 
 */

#ifndef DEQUE_H
#define DEQUE_H

#include <iostream>
#include <cstdlib>

using namespace std;

template <typename Object>
class Deque {
protected:                                     

	struct Node {				
		Object  element;		
		Node*   prev;			
		Node*   next;			
		Node(const Object& e = Object(), Node* p = NULL, Node* n = NULL)
			: element(e), prev(p), next(n) { }
	};
	typedef Node* NodePtr;		

private:                                
	NodePtr header;			
	NodePtr trailer;		
	int sz;				

public:
	Deque() {			
		header = new Node;
		trailer = new Node;
		header->next = trailer;	
		trailer->prev = header;	
		sz = 0;
	}

	void insertFirst(const Object& e);

	void print();
};
#endif