程序代码:
#ifndef _DoubleQueue_H_
#define _DoubleQueue_H_
#include <iostream>
using namespace std;
template<class T> class CDoubleQueue;
template<class T>
class CNode
{
friend class CDoubleQueue<T>;
public:
CNode():m_front(NULL),m_after(NULL),m_type(0){};
CNode(const CNode<T> &t):m_front(t.m_front),m_after(t.m_after),m_type(t.m_type){}
CNode<T>& operator =(const CNode<T> &t)
{
if(this == &t)
return *this;
m_front = t.m_front;
m_after = t.m_after;
m_type = t.m_type;
return *this;
}
friend ostream & operator<<(ostream &out,const CNode<T> &t)
{
out<<t.m_type;
return out;
}
CNode<T> *GetAfter(){return m_after;}
CNode<T> *GetFront(){return m_front;}
private:
CNode<T>* m_front;
CNode<T>* m_after;
T m_type;
};
template<class T>
class CDoubleQueue
{
public:
CDoubleQueue():m_end1(NULL),m_end2(NULL),m_Num(0){}
~CDoubleQueue()
{
DeleteAll(m_end1);
}
bool CreateHead(const T &t)
{
if(m_end1 != NULL)
return false;
CNode<T> *Phead = new CNode<T>();
Phead->m_type = t;
m_end1 = Phead;
m_end2 = Phead;
m_Num ++;
return true;
}
bool InsertHead(const T &t)
{
if(m_end1 == NULL)
return CreateHead(t);
CNode<T> *Ph= new CNode<T>();
Ph->m_type = t;
Ph->m_after = m_end1;
m_end1->m_front = Ph;
m_end1 = Ph;
m_Num ++;
return true;
}
bool InsertEnd(const T &t)
{
if(m_end2 == NULL)
return CreateHead(t);
CNode<T> *PE= new CNode<T>();
PE->m_type = t;
PE->m_front = m_end2;
m_end2->m_after = PE;
m_end2 = PE;
m_Num ++;
return true;
}
bool DeleteHead()
{
if(m_end1 == NULL)
return false;
if(m_end1 == m_end2)
{
delete m_end1;
m_end1 = NULL;
m_end2 = NULL;
}
else
{
CNode *PH = m_end1->m_after;
delete m_end1;
m_end1 = PH;
}
m_Num --;
return true;
}
bool DeleteEnd()
{
if(m_end2 == NULL)
return false;
if(m_end1 == m_end2)
{
delete m_end2;
m_end1 = NULL;
m_end2 = NULL;
}
else
{
CNode *PE = m_end2->m_front;
delete m_end2;
m_end2 = PE;
}
m_Num --;
return true;
}
CNode<T> * GetHead(){return m_end1;}
CNode<T> * GetEnd(){return m_end2;}
private:
CDoubleQueue<T>(const CDoubleQueue<T> &t);
CDoubleQueue<T> & operator=(const CDoubleQueue<T> &t);
CNode<T> *m_end1;
CNode<T> *m_end2;
__int32 m_Num;//用此变量限制
void DeleteAll(CNode<T> *P)
{
if(P != NULL)
{
DeleteAll(P->m_after);
delete P;
}
}
};
#endif
测试用例
程序代码:
#include "DoubleQueue.h"
int _tmain(int argc, _TCHAR* argv[])
{
CDoubleQueue<int> m_test;
for(int i=0;i<100;i++)
{
if(i%2 == 0)
m_test.InsertEnd(i);
else
m_test.InsertHead(i);
}
CNode<int> *m_head = m_test.GetHead();
while(m_head != NULL)
{
cout<<*m_head<<endl;
m_head = m_head->GetAfter();
}
return 0;
}