循环队列：
1.循环队列中判断队空的方法是判断front==rear，队满的方法是判断front=（rear+1）%maxSize。（我曾经想过为什么不用一个length表示队长，当length==maxSize时队满）原因就是，在频繁的队列操作中，多出一个变量会大量的增加执行时间，所以不如浪费一个数组空间来得划算。
2.用单链表表示的链式队列特别适合于数据元素变动较大的情形，而且不存在溢出的情况。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
template<class T>class SeqQueue{ protected: T *element; int front,rear; int maxSize; public: SeqQueue(int sz=10){ front=rear=0; maxSize=sz; element=new T[maxSize]; } ~SeqQueue(){ delete[] element; } bool EnQueue(const T& x){//入队 if(isFull()) return false; element[rear]=x; rear=(rear+1)%maxSize; return true; } bool DeQueue(T& x){//出队 if(isEmpty()) return false; x=element[front]; front=(front+1)%maxSize; return true; } bool getFront(T& x){//获取队首元素 if(isEmpty()) return false; x=element[front]; return true; } void makeEmpty(){//队列置空 front=rear=0; } bool isEmpty()const{//判断队列是否为空 return (rear==front)?true:false; } bool isFull()const{//队列是否为满 return ((rear+1)%maxSize==front)?true:false; } int getSize()const{ return (rear-front+maxSize)%maxSize; }}; |
测试代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
void menu(){ cout<<"1.入队"<<endl; cout<<"2.获取队首元素"<<endl; cout<<"3.出队"<<endl; cout<<"4.队列置空"<<endl; cout<<"5.获取队中元素数量"<<endl; cout<<"6.退出"<<endl;} void function(int num,SeqQueue<int> *sq){ switch(num){ int x; case 1: cin>>x; sq->EnQueue(x); break; case 2: sq->getFront(x); cout<<x<<endl; break; case 3: sq->DeQueue(x); break; case 4: sq->makeEmpty(); break; case 5: x=sq->getSize(); cout<<x<<endl; break; default: exit(1); }}int main(int argc, char** argv) { SeqQueue<int> *sq=new SeqQueue<int>; int num; while(true){ menu(); cin>>num; function(num,sq); } delete sq; return 0; } |
之后是链式队列，实现类代码和测试代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
#include <iostream>using namespace std;template<class T> struct LinkNode{ T data; LinkNode<T> *link; LinkNode(T& x,LinkNode<T> *l=NULL){ data=x; link=l; }};template<class T>class LinkedQueue{ protected: LinkNode<T> *front,*rear; public: LinkedQueue(){ front=rear=NULL; } ~LinkedQueue(){ makeEmpty(); } bool enQueue(T& x){ if(front==NULL) front=rear=new LinkNode<T>(x); else{ rear=rear->link=new LinkNode<T>(x); } return true; } bool deQueue(T& x){ if(isEmpty()) return false; LinkNode<T> *p=front; x=front->data; front=front->link; delete p; return true; } bool getFront(T& x)const{ if(isEmpty()) return false; x=front->data; return true; } void makeEmpty(){ LinkNode<T> *p; while(front!=NULL){ p=front; front=front->link; delete p; } } bool isEmpty()const{ return (front==NULL)?true:false; } int getSize()const{ LinkNode<T> *p; int count=0; p=front; while(p!=NULL){ count++; p=p->link; } return count; }}; void menu(){ cout<<"1.入队"<<endl; cout<<"2.获取队首元素"<<endl; cout<<"3.出队"<<endl; cout<<"4.队列置空"<<endl; cout<<"5.获取队中元素数量"<<endl; cout<<"6.退出"<<endl;} void function(int num,LinkedQueue<int> *lq){ switch(num){ int x; case 1: cin>>x; lq->enQueue(x); break; case 2: lq->getFront(x); cout<<x<<endl; break; case 3: lq->deQueue(x); break; case 4: lq->makeEmpty(); break; case 5: x=lq->getSize(); cout<<x<<endl; break; default: exit(1); }}int main(int argc, char** argv) { LinkedQueue<int> *lq=new LinkedQueue<int>; int num; while(true){ menu(); cin>>num; function(num,lq); } delete lq; return 0; } |
以上这篇C++实现循环队列和链式队列的示例就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持服务器之家。
原文链接：https://www.cnblogs.com/ytz1996/p/6339162.html
