数据结构之队列

1、数据结构之队列1、定义队列也是一种线性表，但就像堆栈一样，它的操作也受到限制。队列的所有插入操作都在表的一端进行，所有的删除操作都在表的另一端进行。它的所有操作都遵循“先进先出”原则，即先进入队列的元素一定是先离开队列。进行删除的一端叫做“队头”（Front），进行插入的一端叫做“队尾”（Rear）。2、队列的基本操作向队尾插入元素：QInsert()/入队一个元素删除队首元素：QDelete()/出队一个元素获取队首元素：QRead()/读取队首元素判断队列是否空：IsEmpty()判断队列是否满：IsFull()清空队列：QClear()3、队列的实现方法按照存储方式的不同队列分为两种，一

2、种采用顺序存储方式存储称为顺序队列，另一种采用链式存储方式存储称为链式队列。3.1、顺序队列1顺序队列删除队头元素有以下两种方式。（1）不要求队头元素必须存放在下标为零的数组元素中每次删除队头元素，只需修改队头指针的位置，令front=front+1。该方式的优点是无须改变其它队列元素的地址，缺点是front值随着队头元素的删除而不断增加，整个队列向数组的后端移动。随着队尾元素的不断加入，必须出现数组后端没有可用空间的情况，而数组前端的大量空间却被闲置。（2）要求队头元素必须存放在下标为零的数组元素中每次删除队头元素，令所有元素都向前移动一个位置。该方式的优点是不浪费空间，缺点是所有元素的地址

3、都必须改变，效率低下。为了克服上述缺点，可以假定数组是循环的，即采用环状模型来实现顺序队列。之和模型将队列在逻辑上置于一个圆环上，如下图所示，用整形变量front存放队头位置，每删除一个队头元素，就将front顺时针移动一个位置。整形变量rear存放新元素要插入的位置，每插入一个元素，rear将顺时针移动一个位置。整形变量count存放队列中元素的个数。当count等于数组规模size时，说明队列已满；当count等于0时，说明队列为空。环状队列的实现要用到求余运算：Front顺时针移动1位：front=(front+1)MOD sizerear顺时针移动1位：rear=(rear+1)MOD

4、 size以下是顺序队列的C+代码：/实现顺序队列#ifndef mod#define mod(x, y) (x%y)#endif#include <iostream>using namespace std;/类声明template <class T>class AQueuepublic:AQueue(int MaxQueueSize);/构造函数AQueue();/析构函数bool QInsert(const T &item);/向队尾插入元素itembool QDelete(T &item);/删除队首元素并将该元素值保存到itembool QRea

5、d(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>AQueue<T>:AQueue(int MaxQueueSize)front = 0;rear = 0;count = 0

6、;size = MaxQueueSize;QArray = new TMaxQueueSize;template <class T>AQueue<T>:AQueue()delete QArray;template <class T>bool AQueue<T>:QInsert(const T &item)if (IsFull()/* code */cout<<"Queue is full, can't insert data."<<endl;return false;QArrayrear

7、 = item;rear = mod(rear + 1, size);count+;return true;template <class T>bool AQueue<T>:QDelete(T &item)if (IsEmpty()/* code */cout<<"Queue is empty, can't delete."<<endl;return false;item = QArrayfront;front = mod(front + 1, size);count-;return true;template

8、 <class T>bool AQueue<T>:QRead(T &item)constif (IsEmpty()/* code */cout<<"Queue is empty, can't read."<<endl;return false;item = QArrayfront;return true;template <class T>bool AQueue<T>:IsEmpty()constreturn (count = 0);template <class T>boo

9、l AQueue<T>:IsFull()constreturn (count = size);template <class T>void AQueue<T>:QClear()front = 0;rear = 0;count = 0;3.2、链式队列采用链式存储方式实现的队列称为链式队列。链式队列也用单链表结构，限定在表头（队列头）进行出队操作，在表尾（队列尾）进行入队操作。在实现过程中需要建立结点结构，定义分别指向队头和队尾的指针front和rear。首先建立结点结构LQueueNode，如下：template <class T>struct

10、LStackNodeT data;/存储数据LStackNode<T> *next; /指向下一个结点LStackNode(LStackNode* nextNode = NULL)next = nextNode;LStackNode(const T &item, LStackNode* nextNode =NULL)data = item;next = nextNode;以下是链式队列LQueue类的C+代码：/实现链式队列#include "stdafx.h"#include <iostream>using namespace std;/建

11、立结点结构template <typename _InputIter>struct LQueueNode_InputIter data;LQueueNode<_InputIter> *next;LQueueNode(LQueueNode<_InputIter> *nextNode = NULL)next = nextNode;LQueueNode(const _InputIter &item, LQueueNode<_InputIter> *nextNode = NULL)data = item;next = nextNode;/类声明t

12、emplate <typename _InputIter>class LQueuepublic:LQueue();LQueue();bool QInsert(const _InputIter &item);bool QDelete(_InputIter &item);bool QRead(_InputIter &item)const;bool IsEmpty()const;void QClear();void QShow()const;private:LQueueNode<_InputIter> *front;LQueueNode<_Inp

13、utIter> *rear;/类实现template <typename _InputIter>LQueue<_InputIter>:LQueue()front = NULL;rear = NULL;template <typename _InputIter>LQueue<_InputIter>:LQueue()QClear();template <typename _InputIter>bool LQueue<_InputIter>:QInsert(const _InputIter &item)if (Is

14、Empty()/* code */front = new LQueueNode<_InputIter>(item);rear = front;return true;rear->next = new LQueueNode<_InputIter>(item);rear = rear->next;return true;template <typename _InputIter>bool LQueue<_InputIter>:QDelete(_InputIter &item)/注意此处容易忽略释放内存if (IsEmpty()/*

15、 code */cout << "LQueue is empty, can't delete." << endl;return false;LQueueNode<_InputIter> *q = front;item = q->data;front = front->next;delete q;/此处较容易忽略，当front=null时，rear=nullif (IsEmpty()/* code */rear = NULL;return true;template <typename _InputIter>

16、bool LQueue<_InputIter>:QRead(_InputIter &item)constif (IsEmpty()/* code */cout << "LQueue is empty, can't read." << endl;return false;item = front->data;return true;template <typename _InputIter>bool LQueue<_InputIter>:IsEmpty()constreturn (front = NULL);template <typename _InputIter>void LQueue<_InputIter>:QClear()while(!IsEmpty()LQueueNode<_InputIter> *q = front;fr