c语言用链表实现循环队列

循环队列：

1. 循环队列中判断队空的方法是判断front==rear，队满的方法是判断front=（rear+1）%maxSize。

（我曾经想过为什么不用一个length表示队长，当length==maxSize时队满）原因就是，在频繁的队列操作中，多出一个变量会大量的增加执行时间，所以不如浪费一个数组空间来得划算。

2. 用单链表表示的链式队列特别适合于数据元素变动较大的情形，而且不存在溢出的情况。

1 template<class T>2 class SeqQueue{3 protected:4 T *element;5 int front,rear;6 int maxSize;7 public:8 SeqQueue(int sz=10){9 front=rear=0;10 maxSize=sz;11 element=new T[maxSize];12 }13 ~SeqQueue(){14 delete[] element;15 }16 bool EnQueue(const T x){//入队 17 if(isFull()) return false;18 element[rear]=x;19 rear=(rear+1)%maxSize;20 return true;21 }22 bool DeQueue(T x){//出队 23 if(isEmpty()) return false;24 x=element[front];25 front=(front+1)%maxSize;26 return true;27 }28 bool getFront(T x){//获取队首元素 29 if(isEmpty()) return false;30 x=element[front];31 return true;32 }33 void makeEmpty(){//队列置空 34 front=rear=0;35 }36 bool isEmpty()const{//判断队列是否为空 37 return (rear==front) true:false;38 }39 bool isFull()const{//队列是否为满40return ((rear+1)%maxSize==front) true:false;41 }42 int getSize()const{43 return (rear-front+maxSize)%maxSize;44 }45 }; 测试代码如下：1 void menu(){2 cout<<"1.入队"<<endl;3 cout<<"2.获取队首元素"<<endl;4 cout<<"3.出队"<<endl;5 cout<<"4.队列置空"<<endl;6 cout<<"5.获取队中元素数量"<<endl;7 cout<<"6.退出"<<endl;8 } 9 10 void function(int num,SeqQueue<int> *sq){11 switch(num){12 int x;13 case 1:14 cin>>x;15 sq->EnQueue(x);16 break;17 case 2:18 sq->getFront(x);19 cout<<x<<endl;20 break;21 case 3:22 sq->DeQueue(x);23 break;24 case 4:25 sq->makeEmpty();26 break;27 case 5:28 x=sq->getSize();29 cout<<x<<endl;30 break;31 default:32 exit(1);33 }34 }35 int main(int argc, char** argv) {36 SeqQueue<int> *sq=new SeqQueue<int>;37 int num;38 while(true){39 menu();40 cin>>num;41 function(num,sq);42 } 43 delete sq;44 return 0; 45 }之后是链式队列，实现类代码和测试代码如下：1 #include <iostream>2 using namespace std;3 template<class T> 4 struct LinkNode{5 T data;6 LinkNode<T> *link;7 LinkNode(T x,LinkNode<T> *l=NULL){8 data=x;9 link=l;10 }11 };12 template<class T>13 class LinkedQueue{14 protected:15 LinkNode<T> *front,*rear;16 public:17 LinkedQueue(){18 front=rear=NULL;19 }20 ~LinkedQueue(){21 makeEmpty();22 }23 bool enQueue(T x){24 if(front==NULL)25 front=rear=new LinkNode<T>(x);26 else{27 rear=rear->link=new LinkNode<T>(x);28 }29 return true;30 }31 bool deQueue(T x){32 if(isEmpty()) return false;33 LinkNode<T> *p=front;34 x=front->data;35 front=front->link;36 delete p;37 return true;38 }39 bool getFront(T x)const{40 if(isEmpty()) return false;41 x=front->data;42 return true;43 }44 void makeEmpty(){45 LinkNode<T> *p;46 while(front!=NULL){47 p=front;48 front=front->link;49 delete p;50 }51 }52 bool isEmpty()const{53 return (front==NULL) true:false;54 }55 int getSize()const{56 LinkNode<T> *p;57 int count=0;58 p=front;59 while(p!=NULL){60 count++;61 p=p->link;62 } 63 return count;64 }65 }; 66 void menu(){67 cout<<"1.入队"<<endl;68 cout<<"2.获取队首元素"<<endl;69 cout<<"3.出队"<<endl;70 cout<<"4.队列置空"<<endl;71 cout<<"5.获取队中元素数量"<<endl;72 cout<<"6.退出"<<endl;73 } 74 75 void function(int num,LinkedQueue<int> *lq){76 switch(num){77 int x;78 case 1:79 cin>>x;80 lq->enQueue(x);81 break;82 case 2:83 lq->getFront(x);84 cout<<x<<endl;85 break;86 case 3:87 lq->deQueue(x);88 break;89 case 4:90 lq->makeEmpty();91 break;92 case 5:93 x=lq->getSize();94 cout<<x<<endl;95 break;96 default:97 exit(1);98 }99 }100 int main(int argc, char** argv) {101 LinkedQueue<int> *lq=new LinkedQueue<int>;102 int num;103 while(true){104 menu();105 cin>>num;106 function(num,lq);107 } 108 delete lq;109 return 0; 110 }