1.队列的特点:
队列也是一种线性表,对于它所有的插入都在队列的一端进行,所有的删除都在另一端进行,进行删除的一端叫队列的“头”,进行插入的一端叫队列的“尾”,其操作特点是“先进先出”。
2.队列的一般定义:
type
queue=record
data:array[1..m] of datatype;
head,tail:1..m
end;
var
q:queue;
3.队列的基本操作:
(1)队列的插入enq(q,x):在队列q中插入一个值为x的元素,也称为进队;
q[tail]:=x;
若tail=m则tail:=1
否则tail:=tail+1;
若tail=head则print('overflow')
(2)队列的删除deq(q):从队列q中删除一个元素,也称为出队;
若tail=head则print('underflow')
否则
若head=m则head:=1否则head:=head+1;
(3)读队头元素head(q,x):将队列q中头部元素的值读到x中;
若tail=head则print('error')
否则x:=q[head];
(4)判队列是否为空qempty(q):这是一个布尔函数,当q是空队列时,取真值,否则取假值。
若tail=head则qempty:=true
否则qempty:=false;
3.队列的应用:
例:设有一个表,记为L=(a1,a2,a3,...,an),其中
L——表名
a1,a2,a3,..,an——表中元素。
当ai为数值时表示元素,当ai为大写字母时,表示另一个表,但不能循环定义。例如,下列的定义是合法的(约定L是第一个表的表名):
L=(3.4,3,4,K,8,0,8)
K=(15,5,8,P,9,4)
P=(4,7,8,9)
程序要求:当全部表给出后,示出所有元素的最大元素。
思路:
(1)可以建立两种队列,一种队列是存放数值的数值队列Q1,并有Q1[A]到Q1[Z]共26条数值队列,另一种队列Q2存放字母,表示将要向该字母所对应的数值队列输入数值的事件队列。
(2)根据题目要求,事件队列Q2中应先放入字母L,表示首先输入L数值队列的数据。
(3)从事件队列Q2中取出一个字母,并招待该字母对应的数值队列的数值输入,如果输入的数据中包含字母,则把字母放入事件队列中,并记录输入的数值中的最大值。
(4)重复(3)步骤,直到事件队列中为空。