数据结构之队列讲述.docx

数据结构之队列 1、定义 队列也是一种线性表，但就像堆栈一样，它的操作也受到限制。队列的所有插入操作都在表的一端进行，所有的删除操作都在表的另一端进行。它的所有操作都遵循“先进先出”原则，即先进入队列的元素一定是先离开队列。进行删除的一端叫做“队头”（Front），进行插入的一端叫做“队尾”（Rear）。 2、队列的基本操作 向队尾插入元素：QInsert() //入队一个元素 删除队首元素：QDelete() //出队一个元素 获取队首元素：QRead() //读取队首元素 判断队列是否空：IsEmpty() 判断队列是否满：IsFull() 清空队列：QClear() 3、队列的实现方法 按照存储方式的不同队列分为两种，一种采用顺序存储方式存储称为顺序队列，另一种采用链式存储方式存储称为链式队列。 3.1、顺序队列[1] 顺序队列删除队头元素有以下两种方式。 （1）不要求队头元素必须存放在下标为零的数组元素中 每次删除队头元素，只需修改队头指针的位置，令front=front+1。该方式的优点是无须改变其它队列元素的地址，缺点是front值随着队头元素的删除而不断增加，整个队列向数组的后端移动。随着队尾元素的不断加入，必须出现数组后端没有可用空间的情况，而数组前端的大量空间却被闲置。 （2）要求队头元素必须存放在下标为零的数组元素中 每次删除队头元素，令所有元素都向前移动一个位置。该方式的优点是不浪费空间，缺点是所有元素的地址都必须改变，效率低下。 为了克服上述缺点，可以假定数组是循环的，即采用环状模型来实现顺序队列。之和模型将队列在逻辑上置于一个圆环上，如下图所示，用整形变量front存放队头位置，每删除一个队头元素，就将front顺时针移动一个位置。整形变量rear存放新元素要插入的位置，每插入一个元素，rear将顺时针移动一个位置。整形变量count存放队列中元素的个数。当count等于数组规模size时，说明队列已满；当count等于0时，说明队列为空。 环状队列的实现要用到求余运算： Front顺时针移动1位：front=(front+1)MOD size rear顺时针移动1位：rear=(rear+1)MOD size 以下是顺序队列的C++代码： //实现顺序队列 #ifndef mod #define mod(x, y) (x%y) #endif #include iostream using namespace std; //类声明 template class T class AQueue { public: AQueue(int MaxQueueSize); //构造函数 ~AQueue(); //析构函数 bool QInsert(const T item); //向队尾插入元素item bool QDelete(T item); //删除队首元素并将该元素值保存到item bool QRead(T item)const; //读取队首元素值 bool IsEmpty()const; //判断队列是否空 bool IsFull()const; //判断队列是否满 void QClear(); //清空队列 private: int front; //队首元素在数组中的位置 int rear; //新元素要插入的位置 int count; //队列中元素的个数 int size; //队列的规模 T *QArray; //存放元素的数组 }; //类实现 template class T AQueueT::AQueue(int MaxQueueSize) { front = 0; rear = 0; count = 0; size = MaxQueueSize; QArray = new T[MaxQueueSize]; } template class T AQueueT::~AQueue() { delete []QArray; } template class T bool AQueueT::QInsert(const T item) { if (IsFull()) { /* code */ coutQueue is full, cant insert data.endl; return false; } QArray[rear] = item; rear = mod(rear + 1, size); count++; return true; } template class T bool AQueueT::QDelete(T item) { if (IsEmpty()) { /