deque.h

此代码运行于visual c++ 6.0的环境下

// Deque.h: interface for the CDeque class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_DEQUE_H__D9C8E23C_01BD_4B66_A89C_E3B172AB838F__INCLUDED_)
#define AFX_DEQUE_H__D9C8E23C_01BD_4B66_A89C_E3B172AB838F__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#define NULL 0

template<class T>
class CNode{                    //队列元素类
public:
	CNode(){ m_pnext = NULL;}	//构造函数
	CNode( const T& content, CNode<T>* next = NULL):m_src(content),m_pnext(next){}//构造函数
	T m_src;                    //元素值 
	CNode<T> * m_pnext;			//元素类对象指针
	virtual ~CNode(){			//析构函数
		if(m_pnext!= NULL)
			delete m_pnext;		
	}
};

template<class T>				//队列类
class CDeque{
	int m_nsize;						//队列元素个数
	CNode<T>* m_phead;					//队列头指针
	CNode<T>* m_ptail;					//队列尾指针
public:	
	int size()const{return m_nsize;}	//返回队列中的元素个数	
	
	void push_back(const T& src){		//向队列尾插入一个元素
		if(m_phead == NULL){
			m_phead = m_ptail = new CNode<T>(src);
			m_nsize++;
			return;
		}
		m_ptail->m_pnext = new CNode<T>(src);
		m_ptail = m_ptail->m_pnext;
		m_nsize ++;
		return;
	}
	
	void push_front(const T& src){		//向队列头插入一个新元素
		if(m_phead == NULL){
			m_phead = m_ptail = new CNode<T>(src);
			m_nsize++;
			return;
		}
		CNode<T>* temp = m_phead;
		m_phead = new CNode<T>(src);
		m_phead->m_pnext = temp;
		m_nsize++;
		return;
	}
	void pop_back(){					//队列尾删除一个元素
		if(m_phead == NULL)
			return;
		CNode<T>* temp = m_phead;
		if(m_phead == m_ptail){
			delete m_phead;
			m_phead = m_ptail = NULL;
			m_size = 0;
			return;
		}
		while(temp->m_pnext!= m_ptail)
			temp = temp->m_pnext;
		delete m_ptail;
		m_ptail = temp;
		m_nsize--;
		return;
	}
	void pop_front(){					//队列头删除一个元素
		if(m_phead == NULL)
			return;
		if(m_phead == m_ptail){
			delete m_phead;
			m_phead = m_ptail = NULL;
			m_nsize =0;
			return;
		}
		CNode<T>* temp = m_phead;
		m_phead = m_phead->m_pnext;
		m_nsize--;
		return;
	}
	
	T& front(){return at(0);}			//返回队列头元素的值
	
	T& at(const int serial)const{		//返回指定位置上的元素的值
		static CNode<T> rvalue;
		if(serial >= m_nsize)
			return rvalue.m_src;
		CNode<T> * temp = m_phead;
		for(int i=0;i<serial;i++)
			temp = temp->m_pnext;
		return temp->m_src;
	}
	
	T& operator [](const int serial){return at(serial);}//重载[]运算符
	
	bool empty(){return m_nsize == 0?true:false;}//返回队列是否为空
	
	CDeque():m_nsize(0),m_phead(NULL),m_ptail(NULL){}//构造函数
	
	CDeque(const CDeque<T>& src){               //拷贝构造函数
		if(src.size() == 0)
			return;
		for(int i=0;i<src.size();i++)
			push_back(src.at(i));
	}
	
	void clear(){								//清空队列的函数
		if( m_phead != NULL )
			delete m_phead;
		m_nsize =0;
	}
	
	CDeque<T> & operator = (const CDeque<T>& src){//重载等号运算符
		if(src.size() == 0)
			return *this;
		clear();
		for(int i=0;i<src.size();i++)
			push_back(src.at(i));
		return *this;
	}

	virtual ~CDeque(){							//析构函数
		if( m_phead != NULL )
			delete m_phead;
	}

};



#endif // !defined(AFX_DEQUE_H__D9C8E23C_01BD_4B66_A89C_E3B172AB838F__INCLUDED_)