队列网络版本.pptVIP

第十一章 堆栈与队列（二） 主要内容 队列的定义及其运算 抽象队列类的定义 队列的定义及其实现 队列顺序存储结构 循环队列 链式队列 11.6 队列的概念及其运算 队列的概念 队列的有关运算 队列的概念 队列简称队，是一种只允许在表的一端进行插入操作而在表的另一端进行删除操作的线性表。 允许进行插入的一端称为队尾，允许删除的一端称为队头。队列的插入运算也简称进队，删除运算简称为出队。 队列也称为先进先出表(FIFO)。 队列的概念 假设Q=(a1，a2，…，an-1，an)为一个队结构，则队头为a1，队尾为an。该队列是按a1，a2，…，an-1，an的顺序进入的，退出该队列也只能按这个顺序进行。 队列和堆栈一样，也是动态结构，同样存在溢出问题，在进行插入、删除运算之前，应进行队满、队空的判断。 队列的有关运算 进队：在队列的尾部插入一个新元素 出队：删除队列的队头元素 测试队空：测试队列是否为空 测试队满：测试队列是否为满 清队：创建一个空队列 11.3 抽象队列类 templateclass type class abque //定义抽象队列类模板 { protected : int qsize; //队列长度 public: bool IsEmpty( ) //判队列是否为空 { return (qsize==0)?true:false; } virtual void PushTail(type)=0; //将元素插入队尾 virtual bool PopFront(type)=0; //从对头提取元素 virtual void Clear( )=0; //清空队列 }; 11.7 队列的定义与实现 队列的顺序存储结构 循环队列的定义 循环队列类的定义及常用成员函数的实现 链式队列的定义 链式队列类的定义及常用成员函数的实现 11.7.1 队列的顺序存储结构 队列的顺序存储结构的实现 队列的顺序存储结构的特点 假溢出问题 队列顺序存储结构的实现 可以用一维数组来描述队列的顺序存储结构。 首先定义一维数组elements[maxsize]来存放队列元素，同时还需要设置两个变量front与 rear分别指出队头元素和队尾元素的下标。 约定：队头指针front指出实际队头元素所在位置的前一个位置，而队尾指针rear指出实际队尾元素所在的位置。 队列顺序存储结构的特点 进行插入运算，必须先测试队满与否。若队满，则调用相关算法处理有关溢出问题；否则，将队尾指针加1，然后将新元素插入到当前队尾指针所指的位置。 删除队头元素，必须先测试队列是否为空。若队空，则调用相关算法处理有关信息；否则，删除队头元素(队头指针加1)，如果需要，可以把被删除元素保存起来。 假溢出问题 在队列的插入算法中，当队尾指针rear==maxsize-1时，再做插入运算好象会产生溢出，而实际上这时队列的前端还有许多空的位置，称为“假溢出”。 解决假溢出问题，有两种办法： 1、每次删除队头一个元素后，把整个队列往前移动一个位置，过程如图所示。在这种情况下，队头指针front就没有用处了。 11.7.2 循环队列类的定义及常用成员函数的实现 templateclass type class SeqQuene: public abquetype {protected: int head； //队头指针 int tail; //队尾指针 type *elements; //存放队列元素的数组 int maxsize; //队列最大可容纳元素个数 SeqQuene Copy(SeqQuene q); //队列拷贝函数 public: SeqQuene(int i=10); //构造函数，缺省参数 ~ SeqQuene( ) //析构函数 { Clear( ); } 11.7.2 循环队列类的定义及常用成员函数的实现 构造函数 ：首先将队列设置为空队列，设置队列最大长度，为队列分配空间。 templateclass type SeqQuenetype:: SeqQuene(int i) { head=tail=0; //将队列设置为空队列 maxsize=i10?10:i; //设置队列的最大长度，最小为10 qsize=0;