//deque/*what is a deque?In Chinese, it's called "双端队列".It's different from a queue.Its elements can be added to or removed from either the front(head) or back(tail) ,called a head-tail linked list.输入限制dequeAn input-restricted deque is one where deletion can be made from both ends, but insertion can be made at one end only.输出限制dequeAn output-restricted deque is one where insertion can be made at both ends, but deletion can be made from one end onlyQueue and stack can be considered spectalizations of deques.There are at least two common ways to efficiently implement a deque: with a modified dynamic arry or with a doubly linked listC++dq1.push_back(x)    insert element at backdq1.push_front(x)    insert element at frontdq1.pop_back(x)      remove last elementdq1.pop_front(x)      remove first elementdq1.back()              return last elementdq1.front()              return first element*///自己写deque //double linked list版template
     
      class Dequeue{private:	struct Node	{		Object data;		Node* next;		Node* prev;		Node(const Object& d = Object(), Node *p = NULL, Node *n = NULL)			:data(d), next(n), prev(p){}	};public:	Dequeue()	{		init();	}	Dequeue(const Dequeue& q)	{		init();		*this = q;	}	const Dequeue& operator=(const Dequeue& q)	{		if (this == &q)			return *this;		clear();		Node *p = q.head->next;		while (p->next != q.tail)		{			this.push_back(p->data);			p = p->next;		}		return *this;	}	~Dequeue()	{		clear();		delete head;		delete tail;	}	//判空	bool isEmpty()	{		return size == 0;	}	//push_back	void push_back(Object item)	{		size++;		Node* p = new Node;		p->data = item;		Node* q = tail->prev;		p->next = tail;		p->prev = q;		q->next = p;		tail->prev = p;	}	//push_front	void push_front(Object item)	{		size++;		Node* p = new Node;		p->data = item;		Node* q = head->next;		p->next = q;		p->prev = head;		head->next = p;		q->prev = p;	}	//pop_back	void pop_back()	{		size--;		Node*p = tail->prev;		Node*q = p->prev;		q->next = tail;		tail->prev = q;		delete p;	}	//pop_front	void pop_front()	{		size--;		Node *p = head->next;		Node *q = p->next;		head->next = q;		q->prev = head;		delete p;	}	//back	Object back()	{		return tail->prev->data;	}	//front	Object front()	{		return head->next->data;	}	//clear	void clear()	{		while (!isEmpty())		{			pop_back();		}	}//getsize	int getSize()	{		return size;	}private:	Node* head;	Node* tail;	int size;	void init()	{		head = new Node;		tail = new Node;		size = 0;		head->next = tail;		tail->prev = head;	}};