数据结构—队列及其应用.ppt

队列及其应用队列及其应用 队列队列 所谓队列所谓队列, ,就是允许在一端进行插入就是允许在一端进行插入, ,在另一端进行删除的在另一端进行删除的 线性表。允许插入的一端称为队尾。线性表。允许插入的一端称为队尾。 队列是一种先进先出队列是一种先进先出(FIFO)(FIFO)的线性表的线性表 队列的顺序存储结构和链式存储结构队列的顺序存储结构和链式存储结构 队列必须构造成循环队列的形式队列必须构造成循环队列的形式, ,否则会出现否则会出现“ “假溢出假溢出” ” #define #define maxsizemaxsize 队列最大容量；队列最大容量； structstruct line line intint amaxsize-1; amaxsize-1; intint rear, front;/front rear, front;/front队头队头;rear;rear队尾队尾 队列操作队列操作 举例举例 食堂排队食堂排队 排队买票排队买票 吸管里的饮料吸管里的饮料 作用：维持顺序作用：维持顺序 数组实现：元素数组实现：元素a0maxn-1a0maxn-1，队首队首frontfront，队尾队尾rearrear 入队：入队：rear+; rear+; areararear=x;=x; 出队：出队：eleele= =afront;frontafront;front+;+; 队空条件：队空条件：frontrearfrontrear 问题：出队的元素还在数组里，不是很浪费吗？问题：出队的元素还在数组里，不是很浪费吗？ 循环队列循环队列 把队列看成环行的，则把队列看成环行的，则 入队：入队：rear= (rear + 1)%maxn; rear= (rear + 1)%maxn; 不定义为不定义为a1maxna1maxn的原因的原因 出队：出队：front= (front + 1) %front= (front + 1) %maxnmaxn; ; 可能存在队满的情况：条件也是可能存在队满的情况：条件也是front rearfront rear 用队列实现图的宽度优先搜索算法用队列实现图的宽度优先搜索算法 我们要对图进行分层次遍历,遍历的序列为1，2， ，7， 宽度优先搜索算法遍历序列图 分析分析 要对图进行按层次遍历，我们可采用逐层标号法进要对图进行按层次遍历，我们可采用逐层标号法进 行。方法如下：行。方法如下： 第一步：将初始点放入队列，并将该点设置为已标第一步：将初始点放入队列，并将该点设置为已标 号的点。号的点。 第二步：从队列中取出已标号而未检查的点，访问第二步：从队列中取出已标号而未检查的点，访问 该点的所有邻接顶点，放入队列，并进行标号，该该点的所有邻接顶点，放入队列，并进行标号，该 顶点为已检查的点。顶点为已检查的点。 第三步：检查队列中是否还有未标号的点，若有，第三步：检查队列中是否还有未标号的点，若有， 转第二步，否则，图便历完毕，算法终止。转第二步，否则，图便历完毕，算法终止。 void void bfs(vbfs(v); /); /从从v v开始宽度有先遍历图开始宽度有先遍历图 inicycque(qinicycque(q); /); /初始化队列初始化队列q q q.encycque(vq.encycque(v); ); vistedvvistedv:=true; /:=true; /初始点初始点v v放入队列放入队列, ,并标号并标号 while(! while(! q.emptyq.empty) /) /直到队列不为空直到队列不为空 while(vwhile(v的邻接顶点存在的邻接顶点存在) ) q.encycque(vq.encycque(v的邻接顶点的邻接顶点); ); vistedvvistedv的邻接顶点的邻接顶点:=true;:=true; q.dlcycque(vq.dlcycque(v); ); 已知队列已知队列(13,2,11,34,41,77,5,7,18,26,15),(13,2,11,34,41,77,5,7,18,26,15),第一个进入队第一个进入队 列的元素是列的元素是13,13,则第五个出队列的元素是则第五个出队列的元素是( )( )。(NOIP9)(NOIP9) A)5 B)41 C)77 D)13 E)18 A)5 B)41 C)77 D)13 E)18 设栈设栈S S和队列和队列QQ的初始状态为空的初始状态为空, ,元素元素e 1 ,e 2 ,e 3 ,e 4 ,e e 1 ,e 2 ,e 3 ,e 4 ,e 5 ,e 65 ,e 6依次通过栈依次通过栈S,S,一个元素出栈后即进入队列一个元素出栈后即进入队列Q,Q,若出队的若出队的 顺序为顺序为e 2 ,e 4 ,e 3 ,e 6 ,e 5 ,e 1 ,e 2 ,e 4 ,e 3 ,e 6 ,e 5 ,e 1 ,则栈则栈S S的容量至少应该为的容量至少应该为( ( ) )。(NOIP8)(NOIP8) A)2 B)3 C)4 D)5 A)2 B)3 C)4 D)5 队列练习试题队列练习试题 【培训试题培训试题】细胞统计细胞统计16111611 DescriptionDescription：一矩形阵列由数字：一矩形阵列由数字0 0到到9 9组成组成, ,数字数字1 1到到9 9代表细胞代表细胞, , 细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细 胞胞, ,求给定矩形阵列的细胞个数。求给定矩形阵列的细胞个数。 InputInput：第一行为整数：第一行为整数m,n(m 0 建立一个顺序栈S，栈的每个元素代表深度优先遍 历路径中的一个结点位置，记录该位置当前扩展到 的方向矢量的序号，再用一对变量Current_x， Current_y记录栈顶元素所代表的具体位置，就可 以以非递归的方式完成深度优先遍历了。 PROC Dfs(startX, startY : integer); 初始化栈 Current_xstartX Current_ystartY top1; stop0; 初始结点入栈 标记(Current_x, Current_y)为已扩展结点 while top0 do 【 stopsttop+1 if （stop0 then 【 Current_xCurrent_x dstop, 1 Current_yCurrent_y dstop, 2 】 】 】ENDP 【培训试题培训试题】最大子序和最大子序和 问题描述 输入一个长度为的整数序 列（A1,A2,An），从中找出 一段连续的长度不超过M的子序 列，使得这个序列的和最大。 最大子序和 例如： 序列 1， -3， 5， 1， -2， 3 当M=2或3时 S=5+1=6 当M=4时 S=5+1+(-2)+3=7 数据范围: 50%的数据N,M=S(j)，则我们可以删掉S(i)（ 因为S(i)永远不会被用到）。此时的队列 中的元素构成了一个单调递增的序列，即 ： S1=i-m为 止。 若当前队尾元素S(k)=S(i-1)，则S(k) 出队；直到S(k)S(i-1)为止。 在队尾插入S(i-1) 取出队列中的最小值