語言用鏈表實(shí)現(xiàn)循環(huán)隊(duì)列？
循環(huán)隊(duì)列：
1.循環(huán)隊(duì)列中判斷隊(duì)空的方法是判斷front==rear，隊(duì)滿的方法是判斷front=（rear+1）%maxSize。（我曾經(jīng)想過為什么不用一個length表示隊(duì)長，當(dāng)length==maxSize時隊(duì)滿）原因就是，在頻繁的隊(duì)列操作中，多出一個變量會大量的增加執(zhí)行時間，所以不如浪費(fèi)一個數(shù)組空間來得劃算。
2.用單鏈表表示的鏈?zhǔn)疥?duì)列特別適合于數(shù)據(jù)元素變動較大的情形，而且不存在溢出的情況。
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){//入隊(duì)
17 if(isFull()) return false;
18 element[rear]=x;
19 rear=(rear+1)%maxSize;
20 return true;
21 }
22 bool DeQueue(T& x){//出隊(duì)
23 if(isEmpty()) return false;
24 x=element[front];
25 front=(front+1)%maxSize;
26 return true;
27 }
28 bool getFront(T& x){//獲取隊(duì)首元素
29 if(isEmpty()) return false;
30 x=element[front];
31 return true;
32 }
33 void makeEmpty(){//隊(duì)列置空
34 front=rear=0;
35 }
36 bool isEmpty()const{//判斷隊(duì)列是否為空
37 return (rear==front)?true:false;
38 }
39 bool isFull()const{//隊(duì)列是否為滿
40 return ((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.入隊(duì)"<<endl;
3 cout<<"2.獲取隊(duì)首元素"<<endl;
4 cout<<"3.出隊(duì)"<<endl;
5 cout<<"4.隊(duì)列置空"<<endl;
6 cout<<"5.獲取隊(duì)中元素數(shù)量"<<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 }
之后是鏈?zhǔn)疥?duì)列，實(shí)現(xiàn)類代碼和測試代碼如下：
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.入隊(duì)"<<endl;
68 cout<<"2.獲取隊(duì)首元素"<<endl;
69 cout<<"3.出隊(duì)"<<endl;
70 cout<<"4.隊(duì)列置空"<<endl;
71 cout<<"5.獲取隊(duì)中元素數(shù)量"<<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 }
