数据结构（Java语言） 课件 项目四 队列-模拟银行客户排队

项目四队列---模拟银行客户排队目录项目四5123

典型工作任务4.1队列项目需求分析典型工作任务4.2队列数据结构设计典型工作任务4.3队列软件代码设计典型工作任务4.4队列软件测试执行典型工作任务4.5队列软件文档编写46典型工作任务4.6队列项目验收交付知识目标掌握队列的常用概念和术语掌握队列的逻辑结构及两种不同的存储结构掌握两类存储结构的表示方法：顺序队列和链队列掌握顺序队列的8种算法掌握链队列的8种算法技能目标能进行项目需求分析会进行队列的算法设计及编程能用队列的知识编程解决问题能进行软件测试及项目功能分析能撰写格式规范的软件文档思政目标培养良好的社会秩序和社会公德锻炼发现问题分析问题解决问题的逻辑思维养成严谨、细致、勤学苦练的学术素养学以致用养成严谨求实的学习习惯总体要求

在日常生活中，我们常常去银行办理相关业务，进入银行后首先需要抽号排队，先到的人抽到的号在前，后到的人抽到的号在后，按照抽到的号从小到大依次排队办理业务，即遵循“先来先服务”的原则。本项目以模拟银行客户排队为例，使用顺序队列对客户排队进行管理，如图4-1所示。图4-1模拟银行客户排队功能模块图典型工作任务4.1队列项目需求分析4.2.1队列的定义队列是一种运算受限制的线性表，元素的添加在表的一端进行，而元素的删除在表的另一端进行。允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。队列的特征：先进先出即FIFO（FirstInFirstOut）图4-2

队列示意图典型工作任务4.2队列数据结构设计4.2.1队列的定义队列是一种运算受限制的线性表，元素的添加在表的一端进行，而元素的删除在表的另一端进行。允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。图4-2

队列示意图典型工作任务4.2队列数据结构设计3.2.2栈的基本操作

典型工作任务4.2队列数据结构设计初始化：构造一个空的队列清空：销毁一个已存在的队列入队：销毁一个已存在的队列出队：删除队列队头元素获取：取队列队头元素判空：判断当前队列是否为空求长度：求出队列中数据元素的个数正序遍历：依次访问队列中每个元素并输出加工型引用型4.2.3队列的顺序存储结构1.顺序队列的数组表示顺序存储的队列简称为顺序队列，也就是利用一组地址连续的存储单元依次存放队列中的各个数据元素。一般情况下，使用一维数组作为队列的顺序存储空间，并设立两个下标：一个指向队头元素位置的下标front，另一个为指向队尾元素位置的下标rear。【约定】在非空队列中，队头元素下标front

总是指向队列中实际队头元素的前一个位置，而元素的下标rear总是指向队尾元素。图4-3为队列中首尾元素下标的变化过程示意图。

（a）空队列

（b）元素A入队后

（c）元素B、C、D、E、F入队后

（d）元素A、B、C出队后

图4-3队列中头尾元素下标的变化

典型工作任务4.2队列数据结构设计

在顺序队列中，当队尾元素的下标已经指向了数组的最后一个位置时，此时若再有元素入列，就会发生“溢出”。

典型工作任务4.2队列数据结构设计2.循环队列

为了解决假溢出现象引入循环队列

将顺序队列的存储区假想为是一个头尾相连的圆环，通常把这种特殊结构的队列称为循环队列。队列存放数组被当作首尾相接的表处理。队头、队尾指针加1时从queueArray.length-1直接进到0，可用语言的取模(余数)运算实现。队头指针进1:front=(front+1)%queueArray.length队尾指针进1:rear=(rear+1)%queueArray.length

典型工作任务4.2队列数据结构设计而判断一个队列是否为空可用表达式：rear==front。图4-5循环队列的入队、出队过程示意图（a）空队

（b）A、B、C、D、E、F入队

（c）A、B、C、D、E退队

（d）G入队

（e）H入队

（f）I、J、K、M入队（g）F、G退队

（h）H、I、J退队

（i）K、M退队

典型工作任务4.2队列数据结构设计图4-5循环队列的入队、出队过程示意图（a）空队

（b）A、B、C、D、E、F入队

（c）A、B、C、D、E退队

（d）G入队

（e）H入队

（f）I、J、K、M入队（g）F、G退队

（h）H、I、J退队

（i）K、M退队

典型工作任务4.2队列数据结构设计而判断一个队列是否为空可用表达式：rear==front。图4-6循环队列的队空、队满过程示意图循环队列的判空：rear==front判满：（rear+1）%queueArray.length==front

（a）空队

（b）队满

（c）队满（d）队空图4-6循环队列队空和队满

典型工作任务4.2队列数据结构设计

3.循环队列基本算法publicclasssequenceQueue<T>{ finalintMaxSize=10; privateTqueueArray[]; privateintfront,rear; publicsequenceQueue() { } publicvoidEnQueue(Tobj) { } publicTDeQueue(){}

publicTgetHead(){}

publicintsize(){

publicbooleanisEmpty(){}

publicvoidnextOrder(){}

publicvoidclear(){}}

典型工作任务4.2队列数据结构设计front指示队头，rear指示队尾

(1)构造空的顺序队列publicsequenceQueue(){front=rear=0;//front和rear下标均指向

//只要front和rear指向同一个位置，那队列必为空queueArray=(T[])newObject[MaxSize];//定义一个数组，存储单元个数10，最多存放9个数据

}

典型工作任务4.2队列数据结构设计

(2)入队（从队尾增加数据元素obj)

publicvoidEnQueue(Tobj){if((rear+1)%queueArray.length==front){//队尾元素的下标rear加1后对数组长度求余数刚好等于队头元素下标的前一个位置，表示队列已满T[]p=(T[])newObject[queueArray.length*2];//如果队列满了，重新分配原来存储单元2倍的空间if(rear==(queueArray.length-1))//队尾元素的下标刚好等于数组长度减1{for(inti=1;i<=rear;i++)p[i]=queueArray[i];//将原有数组的数据从下标为1的位置开始复制，一直到rear}else{inti,j=1;for(i=front+1;i<queueArray.length;i++,j++)//复制front以右的数据p[j]=queueArray[i];for(i=0;i<=rear;i++,j++)//复制front以左的数据p[j]=queueArray[i];front=0;//front指向新数组下标为0的位置rear=queueArray.length-1;//rear指向数组下标为数组长度-1的位置}queueArray=p;//将p数组的名称更换为queueArray}rear=(rear+1)%queueArray.length;//队尾元素下标向右移动一个单位queueArray[rear]=obj;//在队尾将添加obj数据}

典型工作任务4.2队列数据结构设计若队满重新分配更大的存储空间

(3)出队（从队头删除数据元素）

publicTDeQueue(){if(isEmpty()){System.out.println("队列为空，无数据可删除");returnnull;}front=(front+1)%queueArray.length;//front向右移动一个位置，使得front指向第一个数据（队头元素）returnqueueArray[front];//直接返回队头元素}

典型工作任务4.2队列数据结构设计

(4)取队头元素（获取队头元素并输出）publicTgetHead(){if(isEmpty()){System.out.println("队列为空，无数据可取");returnnull;}returnqueueArray[(front+1)%queueArray.length];//一定要和删除中的front移动区别开//front没有移动，只是引用front的值而已}

典型工作任务4.2队列数据结构设计

(5)队列的判空（判断队列是否为空）

publicbooleanisEmpty(){returnfront==rear;//队头front和队尾rear指向同一个位置即可//不要限制front=rear=0}(6)计算队列长度（统计队列中数据元素个数）

publicintsize(){return(rear-front+queueArray.length)%queueArray.length;}

典型工作任务4.2队列数据结构设计

(7)遍历（正序输出队列中的数据元素）

publicvoidnextOrder(){inti,j=front;for(i=1;i<=size();i++){j=(j+1)%queueArray.length;System.out.println(queueArray[j]);}}(8)清空（清空队列)publicvoidclear(){front=rear=0;}

典型工作任务4.2队列数据结构设计4.2.4队列的链式存储结构用链表表示的队列称为链队列，链式队列不存在假溢出的问题，所以，下面给出的是一般的(非循环)队列。

典型工作任务4.2队列数据结构设计链队列的中结点泛型类的定义：publicclassNode<T>{Tdata;Node<T>next;publicNode(Node<T>n){next=n;}publicNode(Tobj,Node<T>n){data=obj;next=n;}publicTgetHead(){returndata;}publicNode<T>getNext(){reurnnext;}典型工作任务4.2队列数据结构设计链队列泛型类的定义：publicclasslinkQueue<T>{ privateNode<T>front,rear; privateintlength; publiclinkQueue(){ }

publicvoidEnQueue(Tobj){ }

publicTDeQueue(){}

publicTgetHead(){}

publicintsize(){}

publicbooleanisEmpty(){}

publicvoidnextOrder(){}

publicvoidclear(){}}典型工作任务4.2队列数据结构设计front指示队头，rear指示队尾保存链队的长度初始化（构造空链队列）publiclinkQueue(){length=0;front=rear=newNode<T>(null);//带有头结点的链队列}（2）入队（在队列的队尾增加一个新数据元素）publicvoidEnQueue(Tobj){rear=rear.next=newNode<T>(obj,null);length++;}典型工作任务4.2队列数据结构设计(3)出队（删除队列的队头数据元素）publicTDeQueue(){if(isEmpty()){System.out.println(“队列已空，无法出队！”);returnnull;}Node<T>p=front.next;Tx=p.data;front.next=p.next;length--;if(front.next==null)rear=front;returnx;}典型工作任务4.2队列数据结构设计(4)获取队头数据元素publicTgetHead(){if(isEmpty()){System.out.println(“队列已空，无法获取数据元素！”);returnnull;}returnfront.next.data;}（5）统计链队列中数据元素的个数publicintsize(){returnlength;}典型工作任务4.2队列数据结构设计(6)获取判断链队列是否为空publicbooleanisEmpty(){returnfront.next=null;}（7）访问顺序队列中的每个数据元素并输出

publicvoidnextOrder(){Node<T>p=front.next;While(p!=null)System.out.println(p.data);p=p.next;}(8)清空队列publicvoidclear(){front.next=rear.next=null;}典型工作任务4.2队列数据结构设计

根据队列的特点及模拟银行客户排队办理业务的规则，使用队列中的算法设计本系统的程序，由两部分组成，第一部分为顺序队列的八个算法，第2部分为主程序Test4，该程序实现顺序循环队列操作算法的调用和数据输出及显示，程序框图如图4-9所示。

图4-9模拟银客户排队的程序框图典型工作任务4.3队列软件代码设计

结合前面顺序队列的8种算法（或参考本教材的电子资源包中的源代码），设计主程序如下：

典型工作任务4.3队列软件代码设计publicclassTest4{publicstaticvoidmain(String[]args){ sequenceQueue<Integer>L=newsequenceQueue<Integer>(); inte,i,m; int[]a={01,02,03,04,05};//银行客户办理业务前抽到的号 for(i=0;i<a.length;i++) L.EnQueue(a[i]);//将5位客户的号存储于顺序队列 System.out.println("模拟银行排队中的序号为："); L.nextOrder();//顺序输出5名客户抽到的号 L.EnQueue(6);//第6名客户入队 System.out.println("模拟银行排队中增加一个客户后整个队列的序号为："); L.nextOrder();//输出6名客户抽到的号 L.DeQueue();//队头客户开始办理业务 System.out.println("模拟银行排队中队头客户办理业务后整个队列的序号为："); L.nextOrder();//输出队列中其余客户抽到的号 i=L.getHead();//获取队列中首位客户的号 System.out.println("模拟银行排队中获取首位客户抽取的顺序号为:"+i);}}使用数据结构中的顺序队列编写模拟银行客户排队的程序，通过JDK编译和运行，首次执行后如图4-10所示，队列中有5名客户，可以获取队首客户抽取的号，新来1名客户后队列中显示6名客户，队首客户办理完业务后显示剩余5名客户。图4-10模拟银行客户排队运行的结果图

典型工作任务4.4队列软件测试执行在各输出结果之间添加分隔符“*”和换行符，在对应行增加代码System.out.println("*************")；和System.out.println("\n")；使得各个功能之间有间隔，便于阅读，如图4-11所示。图4-11增加分隔符后模拟银行客户排队运行的结果图

典型工作任务4.4队列软件测试执行在图4-11中未统计队列中数据元素的个数，可增加代码实现，如图4-12所示。图中既实现了顺序队列的入队、出队和获取队头元素的操作，也统计出剩余元素的个数。图4-12统计模拟银行客户排人数队运行的结果图

典型工作任务4.4队列软件测试执行4.5.1

初始化模块测试

使用顺序队列的算法实现模拟银行客户排队功能，在初始化模块中有可能出现未设置数据元素个数的变量、未初始化队头和队尾元素下标等。表4-1初始化模块测试表

典型工作任务4.5队列软件文档编写编号摘要描述预期结果处理结果dl-sch-01数据元素个数变量未设置未受影响不需要增加变量dl-sch-02未指定队头元素下标和队尾元素下标的初值程序报错增加代码：front=rear=0;dl-sch-03未给数组分配存储单元程序报错增加代码：queueArray=(T[])newObject[maxSize]；dl-sch-04未给数组指定存储空间数listArray=(T[])newObject[];程序报错修改代码：listArray=(T[])newObject[maxSize]；4.5.2入队模块测试

典型工作任务4.5队列软件文档编写编号摘要描述预期结果处理结果dl-rd-01未指定入队的数据程序报错在入队方法的参数表里增加入队元素：objpublicvoidEnQueue(Tobj)dl-rd-02未判断队列已满的条件顺序队列已满时无法在队尾位置增加数据元素增加代码：

if((rear+1)%queueArray.length==front){T[]p=(T[])newObject[queueArray.length*2];dl-rd-03未判断队尾元素的下标是否在队列尾部最后一个位置无法确定从数组中哪个位置开始复制数据增加代码：if(rear==(queueArray.length-1)){for(inti=1;i<=rear;i++)p[i]=queueArray[i];}dl-rd-04未判断尾元素在除队尾下标以外的位置对此类数据无法在新空间中复制修改代码：else{inti,j=1;for(i=front+1;i<queueArray.length;i++,j++)p[j]=queueArray[i];for(i=0;i<=rear;i++,j++)p[j]=queueArray[i];front=0;rear=queueArray.length-1;}dl-rd-05未移动队尾元素的下标新数据将原队尾元素覆盖修改代码：rear=(rear+1)%queueArray.length;queueArray[rear]=obj;4.5.3出队模块测试

典型工作任务4.5队列软件文档编写编号摘要描述预期结果处理结果dl-cd-01指定要删除的数据元素不能对队头以外的数据元素删除程序报错修改代码：publicTDeQueue()

dl-cd-02未对队列进行判空队列为空时无数据元素可出队程序报错增加代码：if(isEmpty()){System.out.println("队列为空，无数据可删除");returnnull;dl-cd-03未移动队头元素的下标不能删除队头元素程序报错修改代码：front=(front+1)%queueArray.length;dl-cd-04未返回队头元素无法获取被删除的队头元素程序报错增加代码：returnqueueArray[front];dl-cd-05队头元素出队后统计剩余元素个数不需单独设置变量统计元素个数通过调用计算队列长度的方法获取元素个数4.5.4取队头元素模块测试

典型工作任务4.5队列软件文档编写编号摘要描述预期结果正确代码dl-hq-01指定要获取的数据元素不能获取除队头以外的数据元素程序报错修改代码：publicTgetHead()dl-hq-02未判断队列是否为空顺序队列为空时无数据可获取程序报错增加代码：if(isEmpty()){System.out.println("队列为空，无数据可取");returnnull;}dl-hq-03未移动队头数据元素的下标获取队头数据元素的位置不正确程序报错修改代码：(front+1)%queueArray.lengthdl-hq-04未返回已获取的队头元素无法获取到队头数据元素程序报错增加代码：returnqueueArray[(front+1)%queueArray.length];4.5.5判空模块测试4.5.6计算队列长度模块测试典型工作任务4.5队列软件文档编写编号摘要描述预期结果正确代码dl-pk-01返回值类型不正确程序报错方法首部为：publicbooleanisEmpty()dl-pk-02指定判空时的位置为0不能指定0位置为空队列，只需队头元素下标和队尾元素下标指向同一个位置即可程序报错修改代码：returnfront==rear;编号摘要描述预期结果正确代码dl-tj-01返回值类型不正确数据元素个数的返回值应为整数程序