pascal队列及应用.ppt

数据结构之队列 王桐林 寿光现代中学 数据结构知识简单回顾 物理结构 逻辑结构、物理结构密切相关 算法的设计取决于所选定的逻辑结构， 算法的实现依赖于所采用的存储结构。 线性表 由n个数据元素的有限序列 除头元素外，每个元素都有一个前趋 除尾元素外，每个元素都有一个后继 栈 栈（堆栈）是一种受限的线性表。 其所有的插入和删除操作均限定在线性表的一端进行，允许插入和删除的一端称为栈顶(表尾)，不允许插入和删除的一端称为栈底(表头)。 栈又称为后进先出 (Last In First Out，简称 LIFO) 表。 栈与栈的顺序存储 栈的实现（一） 栈的实现（二） 栈的基本操作 初始化（init）、 进栈（push）、 出栈（pop）、 读取栈顶元素（top）、 判断栈是否为空或已满。 。 栈的典型应用 表达式求值 括号区配 队列 在日常生活中的排队现象： 购物、订票、打饭、候车 排队所遵循的原则是“先来先服务”，后来者总是加到队尾，排头者总是先离开队伍。 队列就是从日常生活中的排队现象抽象出来的。 队列的定义 队列也是一种受限的线性表。 它的所有插入都在队列的一端进行，所有删除都在另一端进行。 允许插入的一端称为队尾(rear)，允许删除的一端称为队头(front)。 队列的插入和删除我们称为入队和出队，新元素入队就成为新的队尾元素，删除元素后，其后继元素成为新的队首元素。 队列是一种先进先出(FIFO)的线性表 front =rear，则队列空; frontrear，则队列非空。 队列的存储 队列可以采用顺序存储结构和链式存储结构 我们一般采用顺序存储结构来定义队列 ——数组 1、队列的顺序存储 （1）借助记录类型来定义： const maxn=xxxx; //队列的最大长度 type queue=record 　 data:array[1..maxn] of qtype; //qtype表示队列元素的数据类型 　 front,rear:1..maxn //队首指针和队尾指针 　　end; var q:queue; （2）实际编程中可以直接定义成如下格式： const maxn=xxxx; //队列的最大长度 var 　q:array[1..maxn] of qtype; //队列 front,rear:1..maxn; //队首指针和队尾指针 2、队列的链式存储 同栈一样，队列也可以采用链式存储。 队列的基本操作 初始化 入队 出队 1、队列的初始化或置空 将队首指针和队尾指针皆置为0。 procedure setnull； front:=0; rear:=0 end； 2、入队add(x)，也称为进队 首先判断队列q是否已满，若未满，则后移队尾指针，并在队列的尾端插入元素x。 procedure add(x:qtype)； begin if rear=maxn then writeln (queue full!); halt end //队满 else begin rear:=rear+1； //后移队尾指针 q[rear]:=x； //插入元素x end； end； 3、出队del 首先判断队列q是否已空，若未空，则后移队首指针，并取出队列q的队首元素。 function del； begin if front=rear then writeln (queue empty!) ; halt end //队空 else begin front:=front+1; //后移队首指针 del:=q[front]； //取出队首元素 end; end； 如果仅完成删除操作，则只需要后移队首指针（front:=front+1）即可。 小练习 ①已知队列 (13，2，11，34，41，77，5，7，18，26，15)， 第一个进入队列的元素是13， 则第五个出