#include"LinkedList.h"
#include"Queue.h"
template<class T>
class LinkedQueue
{
public:
LinkedQueue():rear(NULL),front(NULL){}
~LinkedQueue(){makeEmpty();}
bool EnQueue(const T& x);
bool DeQueue(T& x);
bool getFront(T& x)const;
void makeEmpty();
bool IsEmpty()const{return(front==rear)?true:false;}
int getSize()const;
// bool IsFull()const{return((rear+1)%maxSize==front)?true:false;}
friend ostream& operator<<(ostream& os,LinkedQueue<T>& Q);
protected:
LinkNode<T> *front, *rear;
};
template<class T>
void LinkedQueue<T>::makeEmpty()
{
LinkNode<T> *p;
while(front!=NULL)
{
p=front;
front=front->link;
delete p;
}
};
template<class T>
bool LinkedQueue<T>::EnQueue(const T& x)
{
if(front==NULL)
{
front=rear=new LinkNode<T>(x);//空队列时，新结点成为队列的第一个结点，既是对头也是队尾
if(front==NULL) return false;
}
else
{
rear->link=new LinkNode<T>(x);//非空时在链尾追加新的结点并更新队尾指针
if(rear->link==NULL) return false;
rear=rear->link;
}
return true;
};
template<class T>
bool LinkedQueue<T>::DeQueue(T& x)
{
if(IsEmpty()==true) return false;
LinkNode<T> *p=front;
x=front->data;
front=front->link;
delete p;
return true;
};
template<class T>
bool LinkedQueue<T>::getFront(T& x)const
{
if(IsEmpty()==true) return false;
x=front->data;
return true;
};
template<class T>
int LinkedQueue<T>::getSize()const
{
LinkNode<T> *p=front;
int k=0;
while(p!=NULL)
{
p=p->link;
k++;
}
return k;
};
template<class T>
ostream& operator<<(ostream& os,LinkedQueue<T>& Q)
{
os<<"队列中的元素个数有"<<Q.getSize()<<endl;
LinkNode<T> *p=Q.front;
int i=0;
while(p!=NULL)
{
os<<++i<<":"<<p->data<<endl;
p=p->link;
}
return os;
}