循环队列的C++实现

时间:2022-06-09 03:59:50

    队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。允许插入的一端为队尾(入队),允许删除(出队)的一端为队头。

    顺序存储的队列是采用数组来实现的,但由于数组是静态的,在队列的出队和入队的操作下会出现整个队列后移逐渐占用下标加大位置而下标较小位置为空的“假溢出”现象,所以采用了将存储队列的数组看成是头尾相接的循环结构,即允许队列直接从数组的下标最大的位置延续到下标最小的位置。具体图示大家上网查查吧,在这里就不画了。

    判断队列的状态的标准是头指针与尾指针的关系。约定队头指针front指向队头元素的前一个位置,队尾指针rear指向队尾元素。为了区分队满与队空,采取浪费一个数组元素的空间的策略:

队空:front==rear

队满:(rear+1)%QueueSize==front

具体实现如下:

/*************************************************************************
> File Name: CirQueue.cpp
> Author: Shorey
> Mail: shoreybupt@gmail.com
> Created Time: 2015年03月23日 星期一 14时38分12秒
************************************************************************/

#include<iostream>
using namespace std;
const int QueueSize=100;

class CirQueue
{
public:
CirQueue() //构造函数,置空队列
{
front=rear=0;
}
~CirQueue(){cout<<"destory";} //析构函数
void EnQueue(int x); //元素x入队
int DeQueue(); //队头元素出队
int GetQueue(); //获取队头元素,不删除队头
bool Empty() //判断队列是否为空
{
if(front==rear)
return 1;
else
return 0;
}
private:
int data[QueueSize]; //存放队列的数组
int front,rear; //头指针与尾指针
};

void CirQueue::EnQueue(int x)
{
if((rear+1)%QueueSize==front) //判断队列是否已满
cout<<"queue is full,can't put "<<x<<" into it"<<endl;
else
{
rear=(rear+1)%QueueSize; //移动尾指针指向下一个空间
data[rear]=x; //元素x入队
}
}

int CirQueue::DeQueue() //队头元素出栈
{
if(Empty()) //判断队列是否为空
cout<<"queue is empty"<<endl;
else
{
front=(front+1)%QueueSize; //移动队头指针指向下一个空间,即被删元素所在位置
return data[front]; //返回被删除的元素的值
}
}

int CirQueue::GetQueue()
{
if(Empty())
cout<<"queue is empty"<<endl;
else
{
return data[(front+1)%QueueSize];
}
}
int main()
{
CirQueue Q;
Q.EnQueue(5);
Q.EnQueue(9);
Q.EnQueue(7);
cout<<Q.DeQueue()<<endl;
cout<<Q.GetQueue()<<endl;
cout<<Q.DeQueue()<<endl;
cout<<Q.DeQueue()<<endl;
Q.DeQueue();
return 0;
}