数据结构6_顺序队列(循环队列)
本文实现了顺序队列,与链队列不同的是,顺序队列需要考虑一个问题,
问题情况如下,
解决办法:循环队列,当rear到分配的数组空间末尾时,转到数组头
但是当q.rear==q.front时,又如何区分一种是空队列,一种是满队列的情况呢
这里有两种方案
本次代码实现了第一种方法,同时设置了一个技术变量length,稍加改动便可实现第二个方法
代码如下:
#include<iostream>
using namespace std;
//该顺序队列为循环队列,解决队尾指针达到最大值,队列中有空闲单元,但新元素无法进入队列的情况
//
class SeqQueue
{
int *data;
int front;
int rear;
int cap; //存储队列容量
int length; //当前队列长度
public:
SeqQueue(int length)
{
data=NULL;//data初始化为NULL,用于后面的if语句判断
data=new int[length]; //分配数组空间
this->cap=length;
if(!data)
{
cout<<"OVERFLOW"<<endl;
return;
}
front=rear=0;
this->length=0; //当前长度初始化为0
cout<<"The Queue is constructed"<<endl;
}
void EnQueue(int e) //入列函数
{
if((rear+1)%cap==front)
{
cout<<"The queue is full"<<endl;
return;
}
length++;
data[rear]=e;
rear=(rear+1)%cap; //判断是否超出最大值,超出时回到起点
}
void DeQueue(int &e) //出列
{
if(front==rear)
{
cout<<"The queue is empty"<<endl;
return;
}
e=data[front];
length--;
front=(front+1)%cap;
}
void show() //显示队列所有节点,
{
if(front==rear)
{
cout<<"The queue is empty"<<endl;
return;
}
int q=front;
int i=1;
while(q!=rear)
{
cout<<"The"<<i<<"th queue node is: "<<data[q]<<endl;
q=(q+1)%cap;
i++;
}
cout<<"_________________________________"<<endl;
}
};
void main()
{
SeqQueue a(4);
int num;
a.EnQueue(1);
a.DeQueue(num);
a.DeQueue(num);
a.EnQueue(2);
a.DeQueue(num);
a.EnQueue(3);
a.EnQueue(4);
a.EnQueue(5);
a.EnQueue(6);
a.show();
}