#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);//空隊(duì)列時(shí)，新結(jié)點(diǎn)成為隊(duì)列的第一個(gè)結(jié)點(diǎn)，既是對(duì)頭也是隊(duì)尾
if(front==NULL) return false;
}
else
{
rear->link=new LinkNode<T>(x);//非空時(shí)在鏈尾追加新的結(jié)點(diǎn)并更新隊(duì)尾指針
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<<"隊(duì)列中的元素個(gè)數(shù)有"<<Q.getSize()<<endl;
LinkNode<T> *p=Q.front;
int i=0;
while(p!=NULL)
{
os<<++i<<":"<<p->data<<endl;
p=p->link;
}
return os;
}