数据结构 |
您所在的位置：网站首页 › 循环队列中至少有一个数组空间是空闲的怎么办 › 数据结构 |
数据结构
|
4.2.循环队列功能实现
循环队列特点 为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。 循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。 [1] 循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。 在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件是front=rear，而队列判满的条件是front=（rear+1)%MaxSize。 0.循环队列类的定义实现 //队列的顺序存储 #include using namespace std; typedef int Elemtype; #define MAX_SIZE 25 class queue{ private: int head; int rear; Elemtype *data; int size; int cnt;//计数 public: //1.队列的无参构造函数 queue(); //2.队列的有参构造函数 queue(int s); //3.队列的析构函数 ~queue(); //4.入队操作 void push(Elemtype t); //5.出队操作 bool pop(Elemtype&k); //6.判断队列是否为空 bool isEmpty(); //7.判断队列是否满了 bool isFull(); //8.返回队尾元素 Elemtype GetRear(); //9.返回队头元素 Elemtype GetHead(); //10.清空队列 void Clear(); //11.打印队列 void PrintQueue(); }; 1.循环队列的无参构造函数 //1.队列的无参构造函数 queue::queue() { cnt=0; head=0; rear=-1; size=MAX_SIZE; data=new Elemtype[size]; } 2.循环队列的有参构造函数 //2.队列的有参构造函数 queue::queue(int s) { head=0; rear=-1; cnt=0; if(size>MAX_SIZE) { size=MAX_SIZE; data=new Elemtype[size]; } else { size=s; data=new Elemtype[size]; } } 3.循环队列的析构函数 //3.队列的析构函数 queue::~queue() { delete []data; } 4.循环队列入队操作 //4.入队操作 void queue::push(Elemtype t) { if(!isFull()) { rear=(rear+1)%size; data[rear]=t; cnt++; } else { cout k=data[head]; head=(head+1)%size; cnt--; return true; } else return false; } 6.循环队列判断队列是否为空 //6.判断队列是否为空 bool queue::isEmpty() { return cnt==0; } 7.循环队列判断队列是否满了 //7.判断队列是否满了 bool queue::isFull() { return cnt==MAX_SIZE; } 8.循环队列返回队尾元素 //8.返回队尾元素 Elemtype queue::GetRear() { if(!isEmpty()) { return data[rear]; } return 0; } 9.循环队列返回队头元素 //9.返回队头元素 Elemtype queue::GetHead() { if(!isEmpty()) { return data[head]; } return 0; } 10.循环队列清空队列 //10.清空队列 void queue::Clear() { head=-1; rear=-1; cnt=0; } 11.循环队列打印队列 //11.打印队列 void queue::PrintQueue() { if(!isEmpty()) { int p=head; int q=rear; while(p%size!=q) { cout private: int head; int rear; Elemtype *data; int size; int cnt;//计数 public: //1.队列的无参构造函数 queue(); //2.队列的有参构造函数 queue(int s); //3.队列的析构函数 ~queue(); //4.入队操作 void push(Elemtype t); //5.出队操作 bool pop(Elemtype&k); //6.判断队列是否为空 bool isEmpty(); //7.判断队列是否满了 bool isFull(); //8.返回队尾元素 Elemtype GetRear(); //9.返回队头元素 Elemtype GetHead(); //10.清空队列 void Clear(); //11.打印队列 void PrintQueue(); }; //1.队列的无参构造函数 queue::queue() { cnt=0; head=0; rear=-1; size=MAX_SIZE; data=new Elemtype[size]; } //2.队列的有参构造函数 queue::queue(int s) { head=0; rear=-1; cnt=0; if(size>MAX_SIZE) { size=MAX_SIZE; data=new Elemtype[size]; } else { size=s; data=new Elemtype[size]; } } //3.队列的析构函数 queue::~queue() { delete []data; } //4.入队操作 void queue::push(Elemtype t) { if(!isFull()) { rear=(rear+1)%size; data[rear]=t; cnt++; } else { cout k=data[head]; head=(head+1)%size; cnt--; return true; } else return false; } //6.判断队列是否为空 bool queue::isEmpty() { return cnt==0; } //7.判断队列是否满了 bool queue::isFull() { return cnt==MAX_SIZE; } //8.返回队尾元素 Elemtype queue::GetRear() { if(!isEmpty()) { return data[rear]; } return 0; } //9.返回队头元素 Elemtype queue::GetHead() { if(!isEmpty()) { return data[head]; } return 0; } //10.清空队列 void queue::Clear() { head=-1; rear=-1; cnt=0; } //11.打印队列 void queue::PrintQueue() { if(!isEmpty()) { int p=head; int q=rear; while(p%size!=q) { cout test01(); }循环队列测试结果 |
【本文地址】
今日新闻 |
推荐新闻 |