队列举例

1队列举例【例1】假设以数组Q[m]存放循环队列中的元素,同时以rear和length分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件,并写出相应的插入(enqueue)和删除(dlqueue)元素的操作。【解答】循环队列类定义templateclassTypeclassQueue{//循环队列的类定义public:Queue(int=10);~Queue(){delete[]elements;}intEnQueue(Type&item);Type*DeQueue();Type*GetFront();voidMakeEmpty(){length=0;}//置空队列intIsEmpty()const{returnlength==0;}//判队列空否intIsFull()const{returnlength==maxSize;}//判队列满否private:intrear,length;//队尾指针和队列长度Type*elements;//存放队列元素的数组intmaxSize;//队列最大可容纳元素个数}构造函数templateclassTypeQueueType::Queue(intsz):rear(maxSize-1),length(0),maxSize(sz){//建立一个最大具有maxSize个元素的空队列。elements=newType[maxSize];//创建队列空间if(elements==NULL){cerr动态存储分配失败!endl;exit(1);}}插入函数templateclassTypeintQueueType::EnQueue(Type&item){if(IsFull()){cerr队列已满，不能入队列!endl;return0;}//判队列满则出错处理length++;//长度加1rear=(rear+1)%maxSize;//队尾位置进1elements[rear]=item;//进队列return1;}删除函数templateclassTypeType*QueueType::DeQueue(){if(IsEmpty())returnNULL;//判断队列是否为空，空则返回NULLlength--;//队列长度减12return&elements[(rear-length+maxSize)%maxSize];//返回原队头元素的地址}读取队头元素值函数templateclassTypeType*QueueType::GetFront(){if(IsEmpty())returnNULL;//判断队列是否为空，空则返回NULLreturn&elements[(rear-length+1+maxSize)%maxSize];//返回队头元素的地址}【例2】假设以数组Q[m]存放循环队列中的元素,同时设置一个标志tag，以tag==0和tag==1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。【解答】循环队列类定义templateclassTypeclassQueue{//循环队列的类定义public:Queue(int=10);~Queue(){delete[]Q;}intEnQueue(Type&item);Type*DeQueue();Type*GetFront();voidMakeEmpty(){front=rear=tag=0;}//置空队列intIsEmpty()const{returnfront==rear&&tag==0;}//判队列空否intIsFull()const{returnfront==rear&&tag==1;}//判队列满否private:intrear,front,tag;//队尾指针、队头指针和队满标志Type*Q;//存放队列元素的数组intm;//队列最大可容纳元素个数}构造函数templateclassTypeQueueType::Queue(intsz):rear(0),front(0),tag(0),m(sz){//建立一个最大具有m个元素的空队列。Q=newType[m];//创建队列空间if(Q==NULL){cerr动态存储分配失败!endl;exit(1);}}插入函数templateclassTypeintQueueType::EnQueue(Type&item){if(IsFull()){cerr队列已满，不能入队列!endl;return0;}//判队列满则出错处理rear=(rear+1)%m;//队尾位置进1,队尾指针指示实际队尾位置Q[rear]=item;//进队列3tag=1;//标志改1，表示队列不空，因为入队只会变满return1;}删除函数templateclassTypeType*QueueType::DeQueue(){if(IsEmpty())returnNULL;//判断队列是否为空，空则返回NULLfront=(front+1)%m;//队头位置进1,队头指针指示实际队头的前一位置tag=0;//标志改0,表示栈不满，因为出队只会变空return&Q[front];//返回原队头元素的地址}读取队头元素函数templateclassTypeType*QueueType::GetFront(){if(IsEmpty())returnNULL;//判断队列是否为空，空则返回NULLreturn&Q[(front+1)%m];//返回队头元素的地址}【例3】若使用循环链表来表示队列，p是链表中的一个指针。试基于此结构给出队列的插入(enqueue)和删除(dequeue)算法，并给出p为何值时队列空。【解答】链式队列的类定义templateclassTypeclassQueue;//链式队列类的前视定义templateclassTypeclassQueueNode{//链式队列结点类定义friendclassQueueType;private:Typedata;//数据域QueueNodeType*link;//链域public:QueueNode(Typed=0,QueueNode*l=NULL):data(d),link(l){}//构造函数};templateclassTypeclassQueue{//链式队列类定义public:Queue():p(NULL){}//构造函数~Queue();//析构函数voidEnQueue(constType&item);//将item加入到队列中TypeDeQueue();//删除并返回队头元素TypeGetFront();//查看队头元素的值voidMakeEmpty();//置空队列，实现与~Queue()相同intIsEmpty()const{returnp==NULL;}//判队列空否private:QueueNodeType*p;//队尾指针（在循环链表中）4};队列的析构函数templateclassTypeQueueType::~Queue(){//队列的析构函数QueueNodeType*s;while(p!=NULL){s=p;p=p-link;deletes;}//逐个删除队列中的结点}队列的插入函数templateclassTypevoidQueueType::EnQueue(constType&item){if(p==NULL){//队列空,新结点成为第一个结点p=newQueueNodeType(item,NULL);p-link=p;}else{//队列不空,新结点链入p之后QueueNodeType*s=newQueueNodeType(item,NULL);s-link=p-link;p=p-link=s;//结点p指向新的队尾}}队列的删除函数templateclassTypeTypeQueueType::DeQueue(){if(p==NULL){cout队列空,不能删除！endl;return0;}if(p-link==p){Typeretvalue=p-data;deletep;//若为唯一一个结点，则删除后队列为空p=NULL;returnretvalue;//返回数据}QueueNodeType*s=p-link;//队头结点为p后一个结点p-link=s-link;//重新链接,将结点s从链中摘下Typeretvalue=s-data;deletes;//保存原队头结点中的值,释放原队头结点returnretvalue;//返回数据}队空条件p==NULL。