循环队列:
1.循环队列中判断队空的方法是判断front==rear,队满的方法是判断front=(rear+1)%maxSize。(我曾经想过为什么不用一个length表示队长,当length==maxSize时队满)原因就是,在频繁的队列操作中,多出一个变量会大量的增加执行时间,所以不如浪费一个数组空间来得划算。
2.用单链表表示的链式队列特别适合于数据元素变动较大的情形,而且不存在溢出的情况。
![](https://www.89179.net/other_image/aHR0cHM6Ly9wMy1zaWduLnRvdXRpYW9pbWcuY29tL3BnYy1pbWFnZS9jYzk0MjNmY2I4YWM0OWQ3YmJkZGUzZTg4NWMwY2IyOH50cGx2LXR0LW9yaWdpbi5pbWFnZT9faXo9MzA1NzUmZnJvbT1zZWFyY2hfY29udGVudC53ZW5kYV9hcGkmeC1leHBpcmVzPTE2ODU2NzQ1NzgmeC1zaWduYXR1cmU9WmVkJTJCWnVndVNVaUZSekVGdGhJM1lBS1J1Q1ElM0Q.jpg)
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{//队列是否为满
40 return ((rear+1)%maxSize==front)?true:false;
41 }
42 int getSize()const{
43 return (rear-front+maxSize)%maxSize;
44 }
45 };
测试代码如下:
![](https://www.89179.net/other_image/aHR0cHM6Ly9wMy1zaWduLnRvdXRpYW9pbWcuY29tL3BnYy1pbWFnZS9hZjY0ODhmYWY3ZDI0ODM4ODk0ODM5YzUxZTBiNzUyN350cGx2LXR0LW9yaWdpbi5pbWFnZT9faXo9MzA1NzUmZnJvbT1zZWFyY2hfY29udGVudC53ZW5kYV9hcGkmeC1leHBpcmVzPTE2ODU2NzQ1NzgmeC1zaWduYXR1cmU9VSUyQnFLR09lZkdIYkl1eE83ZUFTWEhVayUyRjhlQSUzRA.jpg)
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 }
![](https://www.89179.net/other_image/aHR0cHM6Ly9wMy1zaWduLnRvdXRpYW9pbWcuY29tL3BnYy1pbWFnZS82ZjE4ODQwMjIyZTk0ZGYzYTM5MTNlOWZlOWY1OWQ0MH50cGx2LXR0LW9yaWdpbi5pbWFnZT9faXo9MzA1NzUmZnJvbT1zZWFyY2hfY29udGVudC53ZW5kYV9hcGkmeC1leHBpcmVzPTE2ODU2NzQ1NzgmeC1zaWduYXR1cmU9cFpkb3lXdXVzdTNJeVZ2TWx3amJpUzV1U0VZJTNE.jpg)
之后是链式队列,实现类代码和测试代码如下:
![](https://www.89179.net/other_image/aHR0cHM6Ly9wMy1zaWduLnRvdXRpYW9pbWcuY29tL3BnYy1pbWFnZS8wYjhhYmEwZmE3OGE0ZGJlODE0YTJjMGFlZGJjNTY4M350cGx2LXR0LW9yaWdpbi5pbWFnZT9faXo9MzA1NzUmZnJvbT1zZWFyY2hfY29udGVudC53ZW5kYV9hcGkmeC1leHBpcmVzPTE2ODU2NzQ1NzgmeC1zaWduYXR1cmU9MkFPJTJCbEs4NlJ1UWtPQyUyRlNFdmhjSzhNRElqVSUzRA.jpg)
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 }