使用c++实现队列基本功能

#include <iostream.h> #include <stdlib.h> //定义队列 typedef struct QNode{ char data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; } LinkQueue; bool InitQueue(LinkQueue &Q){ Q.front=Q.rear=(QueuePtr) malloc (sizeof(QNode));//分配大小为QNode的内存，让Q.front和Q.rear指向这片内存 if(!Q.front) return false; //分配失败时返回false Q.front->next = NULL; //使Q.front->next指向空 return true; //分配成功返回true } void DestroyQueue(LinkQueue &Q){ while (Q.front){ //如果队列存在，执行以下语句 Q.rear=Q.front->next; //用Q.rear保存Q.front->next free(Q.front); //释放Q.front，当释放所有节点时，将不再执行循环 Q.front=Q.rear; //使Q.front=Q.front->next } } bool QueueEmpty(LinkQueue Q){ if(Q.front==Q.rear) //如果头指针和尾指针都指向头结点，则返回true，否则返回false {return true;} else {return false;} } bool EnQueue(LinkQueue &Q ,char e){ QueuePtr p=(QueuePtr) malloc (sizeof(QNode));//分配一片大小为QNode的内存，由p指向这片内存 if(!p) return false;//分配失败则返回false p->data=e; //将e的值存入p->data p->next=NULL; //将p->next设为空 Q.rear->next=p; //将p接到队尾 Q.rear=p; //将尾指针移到p上 return true; //执行成功返回true } bool DeQueue(LinkQueue &Q){ if(Q.front==Q.rear)return false;//判断队列是否为空，空则返回false QueuePtr p=Q.front->next; //用p保存头元素 Q.front->next=p->next; //将头指针移到第二个元素 if(Q.rear==p)Q.rear=Q.front; //如果头元素是最后一个元素,则令尾指针指向头结点 free (p); //释放头元素 return true; //操作成功返回true } void ClearQueue(LinkQueue &Q){ while(!(Q.front==Q.rear)){ //判断队列是否为空，不空则执行以下语句 QueuePtr p=Q.front->next; //用p保存头元素， Q.front->next=p->next; //将头指针移到第二个元素 if(Q.rear==p)Q.rear=Q.front;//如果头元素是最后一个元素,则令尾指针指向头结点,当头尾指针都指向头结点时，跳出循环 free (p); //释放头元素 } } bool GetHead(LinkQueue Q,char &e){ if(Q.front==Q.rear)return false;//判断队列是否为空，空则返回false e=(Q.front->next)->data; //获取头元素内容 return true; } int QueueLength(LinkQueue Q){ if(Q.front==Q.rear) return 0;//判断队列是否为空，空则返回0 int i=1; QueuePtr p=Q.front->next; //将指针p移到头结点上 while (!(p==Q.rear)){ //将p逐个后移，每后移一次，计数器加一 i++; p=p->next; } return i; //返回计数器的值 } bool QueueTraverse(LinkQueue Q){ if(Q.front==Q.rear) return false;//判断队列是否为空，空则返回false QueuePtr p=Q.front; //将指针p移到头结点上 do{ p=p->next; cout<<(p->data)<<endl; }while (!(p==Q.rear)); //逐个输出队列的元素 } void menu(){ cout<<"1.构造空队列\n"; cout<<"2.销毁队列\n"; cout<<"3.判断队列是否为空\n"; cout<<"4.添加元素到队头\n"; cout<<"5.删除队头\n"; cout<<"6.清空队列\n"; cout<<"7.输出队头\n"; cout<<"8.获取队列长度\n"; cout<<"9.输出队列所有元素\n"; cout<<"0.退出\n"; } void main(){ char choice; bool a; LinkQueue Q; menu(); cin>>choice; while(choice!='0') { switch(choice){ case '1': a=InitQueue(Q); if(a) cout<<"构造成功\n";else cout<<"内存分配失败\n"; menu(); break; case '2': DestroyQueue(Q); cout<<"队列已销毁\n"; menu(); break; case '3': a=QueueEmpty(Q); if(a)cout<<"队列为空\n";else cout<<"队列不为空\n"; menu(); break; case '4': cout<<"请输入要加入队列中的元素："; char e; cin>>e; a=EnQueue(Q,e); if(a)cout<<"添加成功\n";else cout<<"添加失败\n"; menu(); break; case '5': a=DeQueue(Q); if(a)cout<<"删除队头成功\n";else cout<<"队列为空\n"; menu(); break; case '6': ClearQueue (Q); cout<<"队列清空\n"; menu(); break; case '7': char e1; a=GetHead(Q,e1); if(a)cout<<"队头元素为"<<e1<<endl;else cout<<"队列为空\n"; menu(); break; case '8': cout<<"队列长度为"<<QueueLength(Q)<<endl; menu(); break; case '9': a=QueueTraverse(Q); if(!a)cout<<"队列为空\n"; menu(); break; default: cout<<"输入出错，请重新输入\n"; break; } cin>>choice; } }