韩都衣舍网站建设的改进,电子商务平台定制开发,百度排行榜明星,wordpress 搜索排名顺序队列 顺序队列是一种先进先出的线性表#xff0c;简称FIFO。允许插入的一端称为队尾#xff0c;允许删除的一端称为队头。因为其入队和出队操作均是#xff08;front/rear#xff09;指针向后移动#xff0c;以进行结点的链接和删除#xff0c;这就造成其使用空间不断…顺序队列 顺序队列是一种先进先出的线性表简称FIFO。允许插入的一端称为队尾允许删除的一端称为队头。因为其入队和出队操作均是front/rear指针向后移动以进行结点的链接和删除这就造成其使用空间不断向出队的那一边偏移当出队入队次数频繁时尾指针移动到我们可以进行队列操作的范围之外去了则会产生假溢出。
当使用动态链表创建顺序队列其向后继续不断的申请内存空间即使前面出队操作释放掉了前面的空间但是指针依旧会向后进行移动直到达到系统预留给程序的内存上界被强行终止。 循环队列 循环队列就是为了解决顺序队列的“假溢出”问题即将顺序队列臆造为一个环状的空间。循环队列中指针和队列元素之间的关系不变我们只需要利用模运算就可以很容易实现指针的循环移动。 但是循环队列中存在一个问题在循环队列中只凭头指针front等于尾指针rear无法判别队列空间是“空”还是“满”可有两种处理方法 一设置队列元素个数成员以区别队列是“空”还是“满” 二front指针表示为虚拟头指针即不指向元素队列的实际元素数量要比队列空间maxsize少一个如下图所示队列总长度为8实际元素个数为7个还有一个被front指针使用。 一设置队列元素个数成员以区别队列是“空”还是“满”
// vector实现循环队列#includeiostream
#includevector
using namespace std;class cirQueue
{
public:int maxsize;int front;int rear;int count;vectorint data;public:cirQueue(){this-count 0;this-maxsize 8;this-front 0;this-rear 0;for(int i0; imaxsize; i){this-data.push_back(0);}}cirQueue(int maxsize):count(0),maxsize(maxsize),front(0),rear(0){for(int i0; imaxsize; i){this-data.push_back(0);} }void push_cirQueue(int data);void pop_cirQueue();void show_cirQueue();
};// 入队
void cirQueue::push_cirQueue(int val){//满了(rear的下一个元素是front再继续就溢出 if( (this-rear1)%maxsize this-front ){coutthe cirQueue is full!endl;}//从rear加入元素else{// 判断队列是否为空if(this-count 0){this-data[this-rear] val;}else{this-rear (this-rear1)%maxsize;this-data[this-rear] val; }this-count;}
}// 出队
void cirQueue::pop_cirQueue(){//判断队列是否为空if(this-count 0){coutthe cirQueue is empty!endl;}//front出队else{this-data[this-front] 0;this-front (this-front1)%maxsize;}this-count--;
}void cirQueue::show_cirQueue(){if(this-count 0){coutthe cirQueue is empty!endl;}else{int cur this-front;coutthis-data[cur], ;while(cur ! this-rear){cur (cur1)%maxsize;coutthis-data[cur], ;}coutendl;}
}int main()
{cirQueue myCirQueue(5);myCirQueue.show_cirQueue();coutfront:myCirQueue.front rear:myCirQueue.rearendl;myCirQueue.push_cirQueue(1);myCirQueue.push_cirQueue(2);myCirQueue.push_cirQueue(3);myCirQueue.push_cirQueue(4);myCirQueue.push_cirQueue(5);myCirQueue.show_cirQueue();coutfront:myCirQueue.front rear:myCirQueue.rearendl;myCirQueue.push_cirQueue(6);myCirQueue.show_cirQueue();myCirQueue.pop_cirQueue();myCirQueue.show_cirQueue();coutfront:myCirQueue.front rear:myCirQueue.rearendl;return 0;
} 二 front指针表示为虚拟头指针即不指向元素
// vector实现循环队列#includeiostream
#includevector
using namespace std;class cirQueue
{
public:int maxsize;int front;int rear;int count;vectorint data;public:cirQueue(){this-count 0;this-maxsize 8;this-front 0;this-rear 0;for(int i0; imaxsize; i){this-data.push_back(0);}}cirQueue(int maxsize):count(0),maxsize(maxsize),front(0),rear(0){for(int i0; imaxsize; i){this-data.push_back(0);} }void push_cirQueue(int data);void pop_cirQueue();void show_cirQueue();
};// 入队
void cirQueue::push_cirQueue(int val){//满了(rear的下一个元素是front再继续就溢出 if( (this-rear1)%maxsize this-front ){coutthe cirQueue is full!endl;}//从rear加入元素else{this-rear (this-rear1)%maxsize;this-data[this-rear] val;this-count;}
}// 出队
void cirQueue::pop_cirQueue(){//判断队列是否为空if(this-front this-rear){coutthe cirQueue is empty!endl;}//front出队else{this-data[this-front] 0;this-front (this-front1)%maxsize;}this-count--;
}void cirQueue::show_cirQueue(){if(this-front this-rear){coutthe cirQueue is empty!endl;}else{int cur this-front;while(cur ! this-rear){cur (cur1)%maxsize;coutthis-data[cur], ;}coutendl;}
}int main()
{cirQueue myCirQueue(5);myCirQueue.show_cirQueue();coutfront:myCirQueue.front rear:myCirQueue.rearendl;myCirQueue.push_cirQueue(1);myCirQueue.push_cirQueue(2);myCirQueue.push_cirQueue(3);myCirQueue.push_cirQueue(4);myCirQueue.push_cirQueue(5);myCirQueue.show_cirQueue();coutfront:myCirQueue.front rear:myCirQueue.rearendl;myCirQueue.push_cirQueue(6);myCirQueue.show_cirQueue();myCirQueue.pop_cirQueue();myCirQueue.show_cirQueue();coutfront:myCirQueue.front rear:myCirQueue.rearendl;return 0;
}
