循环队列和链式队列（C++实现）

时间：2022-04-08 17:43:09

循环队列：

　　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{//队列是否为满
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.入队"<<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 }

 

标签：

相关文章