队列的基本知识及应用.doc

队列的基本知识及应用 [内容提要] 通过本章学习，掌握队列的定义及队列的存储结构 掌握队列的基本操作运算：建队、插入、删除、队列空等，用数组、链接方式所建立队列及操作运算 掌握循环队列概念及运算 能够利用队列解决一些实际问题：广度优先搜索算法 [重点难点] 队列、循环队列概念及存储结构 队列的基本操作 综合运用队列结构解决实际问题 [内容讲授] 一、队列的基本知识 队列(Queue)是一种特殊的线性表。它是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。 1．队列的性质 假设队列为a1,a2,..,an，那么a1就是队头元素，an为队尾元素。队列中的元素是按a1,a2,..,an的顺序进入的，退出队列也只能按照这个次序依次退出。也就是说，只有在a1离开队列之后，a2才能退出队列，只有在a1,a2,..,an-1都离开队列之后，an才能退出队列。图1是队列的示意图。 图1 队列的先进先出示意图 2．队列的存储结构 顺序存储：可用记录数组实现 链接存储：用链接存储方式实现 如图所示： front rear A1 A2 A3 …… …… …… An-1 An 顺序存储结构——数组 3．基本术语： (1) 队空：当队列中没有元素时称为空队列。 (2) 队满：当队列中单元全部被占用 (3) 队列操作规则： 在队列中依次加入元素a1,a2,…an之后，a1是队头元素，an是队尾元素。其出队操作规定从队头进行，进队操作从队尾进行。 即队列的操作是依先进先出的原则进行的。 (4) 上溢、下溢：真溢、假溢 4．队列的基本操作 用顺序队列存储结构的表示方法： type queue=record vec : array[1..m] of elemtype f, r : integer ; end; f, r 分别指向队列的头和尾 （1）进队操作（插入运算） Procedure insert( q, x ) ; begin ① if q.r =m then 输出上溢 ② q.r := q.r+1 ③ q.vec[q.r]:=x ; { 进入队尾 } ④ if q.f= 0 then q.f:=1 end; （2）出队操作：删除操作 procedure dele (q , x) ; begin ① if q.f=0 then 输出下溢 ② x=q.vec[q.f] ③ if q.f=q.r then [ q.f=0; q.r =0 ] else q.f:=q.f + 1 end; （3）置空队算法 procedure setnull (Q) ; begin q.f:=0 ; q.r:=0 ; end; 5. 循环队列 为充分利用向量空间，克服假上溢现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。 else q.r:= [ (q.r mod m)+1 ；q.vec[q.r]:=x ] end; (3) 删除操作 : procedure delete2( q, x ) ; begin if q.f=q.r then 输出队空 else [ q.f = ( q.f mod m ) +1 ；x=q.vec[q.f ] ] end; (4) 循环队列的长度 ： ( r- f+ n ) mod n 6. 链队列? 链队是指队列的链接存储表示，也就是说它只允许在表尾进行插入和在表头进行删除的单链表。一个链队需要队首、队尾两个指针，一个指向表