队列--课件(PPT演示稿).ppt

1队列队列 2主要内容主要内容 u队列的定义及主要特性 u队列的存储结构 u队列的运算/操作 u环形队列 u队列的应用 3队列的定义队列的定义 u队列(queue) 简称队,也是一种运算受限的线性表,即只允许在表的一端进行插入,而在表的另一端删除。把进行插入的一端称作队尾( rear ), 进行删除的一端称为队首(front 或 head )。 u向队列中插入新元素称为进队或入队,新元素进队后,就成为新的队尾元素; 4队列的定义队列的定义 u从队列中删除元素称为出队。出队后,其后继元素成为队首元素。由于队列的插入和删除分别在表的两端进行,所以要删除的元素是队列中最先进入的元素,因此,又把队列称为先进先出( First In First Out ,简称 FIFO )表。 u与栈的比较:底层存储结构可能是一样的,但上层的处理或应用含义方面存在着差别。 5队列的顺序存储结构队列的顺序存储结构 u队列的一种最简单的存储结构为顺序存储,所使用的记录类型可以如下定义: type queue = record vec : array [1..m0] of elemtype ; f, r : integer end; var sq: queue; 6队列的顺序存储结构队列的顺序存储结构 u其中 vec 域用来顺序存储队列的所有元素,f和r域分别用来存储队首元素和队尾元素所在单元的编号,因此,又把 f和r 分别称作队首指针和队尾指针。 7队列的顺序存储结构队列的顺序存储结构 u每次向队列中插入一个元素时,都将使队尾指针后移一个位置; u当队尾指针指向最后一个位置 m0时,表明队列已满(实际上,若 f不等于 1的话,队首前面仍有空闲的单元可以再被利用),若再进行插入,则溢出(把这种溢出叫做“假溢出”); 8队列的顺序存储结构队列的顺序存储结构 u每次删除队列中的一个元素,也同样使队首指针向后移动一个位置。 u当队首指针指向最后一个元素(即队尾指针所指的元素)并被删除后,表明队列已空,此时应把 f和r同时置为 0,以便从第一个单元开始,重新利用整个存储空间。 9队列的链式存储结构队列的链式存储结构( (略略) ) 10 循环队列循环队列 u为了克服假溢出,可以把队列设计/设想为一个循环的表,即可以把 [1] 设想成接在 [m0] 之后,形成了一个环,供队列循环使用