基于链表的双端队列的类模板的C++实现

/*
用链表实现双端队列(储存整型)
该队列有以下几个功能
											1.Createdeque输入n个元素来初始化队列
											2.cleardeque清空整个队列
											3.f_inde（T e）在队首插入元素e
											4.f_outde()队首元素出队
											5.l_inde（T e）在队尾插入元素e
											6.l_outde队尾元素出队
											7.empty检测队列是否为空
											8.length输出并返回队列长度
											9.display打印从队首到队尾的每一元素
该队列有以下成员：
											1.fp队首指针
											2.lp队尾指针
											3.len队列长度
by chczy
2017/10/16 21:34
*/
#include<iostream>
#include<algorithm>
#include<new>
using namespace std;
template<class T>
struct node {
	node* nx;
	node* pr;
	T data;
};

template<class T>
class linkdeque {
public:
	linkdeque();//构造空队列
	~linkdeque() { cout << "destroy the deque!" << endl; };
	node<T>* Createdeque(int n);//构造长度为n的队列
	void cleardeque();//清空队列
	node<T>* f_inde(T e);//在队首插入元素e
	node<T>* f_outde();//队首元素出队
	node<T>* l_inde(T e);//在队尾插入元素e
	node<T>* l_outde();//队尾元素出队
	bool empty();//检测队列是否为空
	int length();//返回队列长度
	void display();//遍历并打印队列元素

private:
	node<T>* fp;//front pointer
	node<T>* lp;//rare pointer
	int len;
};

template<class T>
linkdeque<T>::linkdeque()
{
	fp = NULL;
	lp = NULL;
	len = 0;
}

template<class T>
node<T>* linkdeque<T>::Createdeque(int n)
{
	len = n;
	node<T> *L = new node<T>;
	L->nx = NULL;
	L->pr = NULL;
	node<T> *h = new node<T>;
	cin >> h->data;
	L->nx = h;
	h->pr = L;
	h->nx = NULL;
	fp = h;
	int i = n-1;
	n -= 1;
	node<T> *prev;
	prev = h;
	while (n--)
	{
		node<T> *p = new node<T>;
		cin >> p->data;
		prev->nx = p;
		p->pr = prev;
		p->nx = NULL;
		prev = p;
		if (n == 0)
			lp = p;
	}
	return fp;
}

template<class T>
void linkdeque<T>::cleardeque()
{
	while (!empty()) l_outde();
}

template<class T>
node<T>* linkdeque<T>::f_inde(T e)
{
	node<T>* p=new node<T>;
	p->data = e;
	p->nx = fp;
	fp->pr = p;
	p->pr = NULL;
	fp = p;
	++len;
	return fp;
}

template<class T>
node<T>* linkdeque<T>::f_outde()
{
	node<T> *p = fp;
	node<T> *s = p->nx;
	s->pr = NULL;
	fp = s;
	delete p;
	--len;
	return fp;
}

template<class T>
node<T>* linkdeque<T>::l_inde(T e)
{
	node<T>* p = new node<T>;
	p->data = e;
	p->pr = lp;
	lp->nx = p;
	p->nx = NULL;
	lp = p;
	++len;
	return lp;
}

template<class T>
node<T>* linkdeque<T>::l_outde()
{
	node<T> *p=lp;
	node<T> *s = p->pr;
	s->nx = NULL;
	lp = s;
	delete p;
	--len;
	return p;
}

template<class T>
bool linkdeque<T>::empty()
{
	if (len == 0)
		return 1;
	else
		return 0;
}

template<class T>
int linkdeque<T>::length()//打印并返回队列的长度
{
	cout << "队列的长度是:" << endl;
	cout << len << endl;
	return len;
}

template<class T>
void linkdeque<T>::display()
{
	if (len == 0)
	{
		cout << "no elem!" << endl;
		return;
	}
	int i = 0;
	node<T> *p = fp;
	cout << "队列长为" << len << endl;
	cout << "队列中的元素为: ";
	while (i != len)
	{
		cout << p->data << " ";
		p = p->nx;
		++i;
	}
	cout << endl;
}