做个慷慨的人,以下是LinkedQueue.h的内容,是链式的队列,是个完整的队列,
这回你可以运行了:
#ifndef LINKEDQUEUE_H
#define LINKEDQUEUE_H
#include<iostream.h>
#include<stdlib.h>
#include<assert.h>
////////////////////////////////////////////////
//链队的结点结构体定义
////////////////////////////////////////////////
template <class T>
struct LinkQNode//:public Queue<T>
{
//数据域
T data;
//指针域
LinkQNode<T>* link;
//结点构造函数,只用指针初始化
LinkQNode(LinkQNode<T>* ptr=NULL)
{
//用参数初始化
link=ptr;
};
//结点构造函数,用数据和指针初始化
LinkQNode(const T& item,LinkQNode<T>* ptr=NULL)
{
//初始化数据
data=item;
//初始化指针
link=ptr;
};
};
////////////////////////////////////结点定义结束
////////////////////////////////////////////////
//链队LinkedQueue类模板的声明和定义
////////////////////////////////////////////////
template<class T>
class LinkedQueue
{
public:
//构造函数
LinkedQueue():rear(NULL),front(NULL){};
//析构函数
~LinkedQueue()
{makeEmpty();cout<<"内存释放完毕!"<<endl;};
//将x进入队列的尾部
bool EnQueue(const T& x);
//删除队头元素,其删除的值用x返回
bool DeQueue(T& x);
//读取队头元素的值,把读取的值放入x
bool getFront(T& x)const;
//把队列置空
void makeEmpty();
//判断队列是否为空
bool IsEmpty()const{return (front==NULL)?true:false;};
//得到队列中元素的个数
int getSize()const;
//友元重载<<运算符输出队列中的所有元素
friend ostream& operator<<(ostream& os,LinkedQueue<T>& LQ);
protected:
//队头指针
LinkQNode<T>* front;
//队尾指针
LinkQNode<T>* rear;
};
///////////////////////////LinkedQueue类声明结束
////////////////////////////////////////////////
//makeEmpty()公有成员函数
清空链队并释放内存
////////////////////////////////////////////////
template<class T>
void LinkedQueue<T>::makeEmpty()
{
//游标指针
LinkQNode<T>* ptr=front;
//暂存要删除的结点的指针
LinkQNode<T>* del;
while(ptr!=NULL)
{
del=ptr;
ptr=ptr->link;
delete del;
}
//队头队尾指针置空
front=NULL;
rear=NULL;
};
/////////////////////////////makeEmpty()函数结束
////////////////////////////////////////////////
//EnQueue()公有成员函数
//将x进入队列的尾部
////////////////////////////////////////////////
template<class T>
bool LinkedQueue<T>::EnQueue(const T& x)
{
//如果队列为空,则要新建一个结点
if(front==NULL)
{
//以x为数据新建一个结点
front=new LinkQNode<T>(x);
//断言内存分配成功
assert(front!=NULL);
//同时该结点也是队尾结点
rear=front;
}
//如果队列不空
else
{
//为数据x新建一个结点
//并把结点挂入尾结点的后面
rear->link=new LinkQNode<T>(x);
//断言结点内存分配成功
assert(rear->link!=NULL);
rear=rear->link;
}
return true;
};
////////////////////////////////////////////////
////////////////////////////////////////////////
//DeQueue()公有成员函数
队头元素出队
////////////////////////////////////////////////
template<class T>
bool LinkedQueue<T>::DeQueue(T& x)
{
LinkQNode<T>* del;//暂存待删除的结点的指针
//如果队列为空
if(front==NULL)
{
cout<<"队列为空!"<<endl;
return false;
}
//如果队列不空
else
{
del=front;
//取出要删除的结点的数据
x=front->data;
front=front->link;
delete del;
}
return true;
};
///////////////////////////////DeQueue()函数结束
////////////////////////////////////////////////
//getFront()公有成员函数
读取队头元素
////////////////////////////////////////////////
template<class T>
bool LinkedQueue<T>::getFront(T& x)const
{
if(IsEmpty())
{
cout<<"队列为空!"<<endl;
return false;
}
else
{
x=front->data;
return true;
}
};
//////////////////////////////getFront()函数结束
////////////////////////////////////////////////
//友元重载<<运算符输出队列中的所有元素
////////////////////////////////////////////////
template<class T>
ostream& operator<<(ostream& os,LinkedQueue<T>& LQ)
{
//如果队列为空
if(LQ.IsEmpty())
{
os<<"队列为空!"<<endl;
}
else
{
//游标指针
LinkQNode<T>* ptr=LQ.front;
cout<<"(front)"<<" ";
while(ptr!=NULL)
{
os<<ptr->data<<" ";
ptr=ptr->link;
}
cout<<"(rear)"<<endl;
}
return os;
};
//////////////////////////////////运算符重载结束
////////////////////////////////////////////////
//getSize()公有成员函数
得到队列中元素的个数
////////////////////////////////////////////////
template<class T>
int LinkedQueue<T>::getSize()const
{
if(IsEmpty())
{
cout<<"队列为空!"<<endl;
return 0;
}
else
{
int count=0;
//游标指针
LinkQNode<T>* ptr=front;
//计数
while(ptr!=NULL)
{
count++;
ptr=ptr->link;
}
return count;
}
};
///////////////////////////////getSize()函数结束
#endif