队列基本操作与应用.ppt

队列的基本操作及应用 队列的定义 队列（queue）简称队，是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。我们把进行插入的一端称作队尾（rear），进行删除的一端称作队头（front）。 队列也称作先进先出表（First In First Out，简称FIFO表）。 基本术语 队空：当队列中没有元素时称为空队列； 队满：当队列中单元全部被占用； 进队：向队列中插入新元素； 出队：从队列中删除元素； （假）溢出：队尾指针指向最后一个位置，但队头前面仍有空闲的单元可被利用。 队列操作示意图 队列的存储结构 1．顺序存储 顺序存储的队称为顺序队列 type queue=record data:array[0..maxsize-1] of elemtype 　 front, rear : integer ; end; front指向队列中第一个元素的前一个单元； rear指向队列中最后一个元素单元。 队列的存储结构 2．链式存储 链式存储的队列称为链队 队列的基本运算 （1）初始化：设定Q为一空队列： procedure iniqueue(var Q:queue); begin Q.front:=-1; Q.rear:=-1; end; 队列的基本运算 （2）判队列空：若队列Q为空，则返回值true，否则返回值false： function qempty(Q:queue):Boolean; begin qempty:=(Q.front=Q.rear) end; 队列的基本运算 （3）判队满：若队列满，则返回值true，否则返回值false： function qfull(Q:queue):Boolean; begin Qfull:=（Q.rear＝maxsize-1); end; 队列的基本运算 （4）元素进队：若队列Q不满时，把元素X插入到队列Q的队尾，否则返回信息“Overflow”： procedure inqueue(var Q:queue;X:elemtype); begin if qfull(Q) then writeln(‘Overflow’) else begin Q.rear:=Q.rear+1; 　　　 Q.data[Q.rear]:=X; end end; 队列的基本运算 （5）元素出队：若队列Q不空，则把队头元素删除并返回值给X，否则输出信息“Underflow”： procedure delqueue(var Q:queue;var X:elemtype); begin if qempty(Q) then writeln(‘Underflow’) else begin Q.front:=Q.front+1; X:=Q.data[Q.front]; end; end; 队列的基本运算 （6）取队头元素：若队列不空，返回队头元素的值，否则返回信息“Underflow”： function gethead(Q:queue):elemtype; begin if qempty(Q) then writeln(‘Underflow’) else gethead:=Q.data[Q.front+1]; end; 循环队列 所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用，循环队列的定义如队列。 循环队列的基本运算 （1）初始化： procedure iniqueue(var Q:queue); begin 　 Q.front:=0; 　 Q.rear:=0; end; 循环队列的基本运算 （2）判队列空： function qempty(Q:queue):Boolean; begin qempty:=(Q.front=Q.rear) end; 循环队列的基本运算 （3）判队满： function qfull(Q:queue):Boolean; begin qfull:=((Q.rear+1) mod maxsize=Q.front); end; 循环队列的基本运算 （4）元素进队： procedure inqueue(var Q:queue;X:elemtype); begin if qfull(Q) then writeln(‘Overflow’) else begin Q.rear:=(Q.re