《数据结构》课件-项目四 队列

用队列实现排队叫号项目概述生活中有很多种排队的场景，比如中午去食堂打饭，需要排队，排在队头的同学肯定是先去的，所以先打上饭。计算机中也有很多这样的场景，比如作业调度系统，如果同时来几个任务需要用到输入输出系统，但是输入输出设备只有一套，谁先用呢，也是谁先来谁用，也需要排队。再比如我们的锁机制，如果出现多线程竞争同一把锁，那么同时只有一个线程获得了锁资源，剩下的线程怎么办呢，那如果是公平锁，肯定也是排队，等锁被释放了，那个最先来的线程优先获得锁资源。项目目标序号学习目标知识要点1理解队列的逻辑结构队列的基本概念、基本操作、抽象数据类型2理解队列的顺序与链式存储结构及其算法实现队列的顺序存储：顺序队列、顺序循环队列队列的链式存储：链式队列3熟悉Java中队列的实现类队列的链式存储实现类：LinkedList<E>4能在实际问题中找出队列并用队列解决实际问题使用队列解决排队叫号问题项目情境-银行排队叫号系统

1．情境描述

目前，在以银行营业大厅为代表的窗口行业，大量客户的拥挤排队已成为了这些企事业单位改善服务品质、提升营业形象的主要障碍。排队（叫号）系统的使用己成为改变这种状况的有力手段。排队系统完全模拟了人群排队全过程，通过取票进队、排队等待、叫号服务（出队）等功能，代替了人们站队的辛苦，把顾客排队等待的烦恼变成一段难得的休闲时光，使客户拥有了一个自由的空间和一份美好的心情。2．基本要求

编写程序模拟排队叫号系统的工作过程，要求如下：

（1）程序运行后，当看到“按回车键取号码:”的提示，只要按回车键，即可显示“您的号码是:XXX,你前面有YYY位”的提示，其中XXX是所获得的服务号码，YYY是在XXX之前来到的正在等待服务的人数。

（2）用多线程技术模拟服务窗口（可模拟多个），具有服务员工呼叫顾客的行为，假设每个顾客服务的时间是10秒，时间到后，显示“请XXX号到YYY号窗口!”的提示用队列实现排队叫号项目概述生活中有很多种排队的场景，比如中午去食堂打饭，需要排队，排在队头的同学肯定是先去的，所以先打上饭。计算机中也有很多这样的场景，比如作业调度系统，如果同时来几个任务需要用到输入输出系统，但是输入输出设备只有一套，谁先用呢，也是谁先来谁用，也需要排队。再比如我们的锁机制，如果出现多线程竞争同一把锁，那么同时只有一个线程获得了锁资源，剩下的线程怎么办呢，那如果是公平锁，肯定也是排队，等锁被释放了，那个最先来的线程优先获得锁资源。项目目标序号学习目标知识要点1理解队列的逻辑结构队列的基本概念、基本操作、抽象数据类型2理解队列的顺序与链式存储结构及其算法实现队列的顺序存储：顺序队列、顺序循环队列队列的链式存储：链式队列3熟悉Java中队列的实现类队列的链式存储实现类：LinkedList<E>4能在实际问题中找出队列并用队列解决实际问题使用队列解决排队叫号问题项目情境-银行排队叫号系统

1．情境描述

目前，在以银行营业大厅为代表的窗口行业，大量客户的拥挤排队已成为了这些企事业单位改善服务品质、提升营业形象的主要障碍。排队（叫号）系统的使用己成为改变这种状况的有力手段。排队系统完全模拟了人群排队全过程，通过取票进队、排队等待、叫号服务（出队）等功能，代替了人们站队的辛苦，把顾客排队等待的烦恼变成一段难得的休闲时光，使客户拥有了一个自由的空间和一份美好的心情。2．基本要求

编写程序模拟排队叫号系统的工作过程，要求如下：

（1）程序运行后，当看到“按回车键取号码:”的提示，只要按回车键，即可显示“您的号码是:XXX,你前面有YYY位”的提示，其中XXX是所获得的服务号码，YYY是在XXX之前来到的正在等待服务的人数。

（2）用多线程技术模拟服务窗口（可模拟多个），具有服务员工呼叫顾客的行为，假设每个顾客服务的时间是10秒，时间到后，显示“请XXX号到YYY号窗口!”的提示任务一

分析队列的逻辑结构学习目标熟悉队列的逻辑结构熟悉队列的基本操作12熟悉队列的抽象数据类型3

为完成迷宫探路编程任务，首先对问题抽象，建立问题的抽象数据类型。一是确定数据对象的逻辑结构，找出构成数据对象的数据元素之间的关系。二是确定为求解问题需要对数据对象进行的操作或运算。最后将数据的逻辑结构及其在该结构上的运算进行封装得到抽象数据类型。任务描述步骤一：分析队列的逻辑结构任务实施

队列(queue)是一种特殊的线性表，是一种只允许在表的一端进行插入操作而在另一端进行删除操作的线性表。进行插入操作的端称为队尾(rear)，进行删除操作的端称为队头(front)。队列中没有数据元素时称为空队列(emptyqueue)。队列通常记为Q=(a0,a1,…,an-1)，Q是英文单词queue的第1个字母。a0为队头元素，an-1为队尾元素。这n个元素是按照a0,a1,…,an-1的次序依次入队的，出队的次序与入队相同，a0第一个出队，an-1最后一个出队。a0a1﹍an-1入队出队队头队尾队列的定义队列的特征：先进先出或后进后出步骤二：分析队列的的基本运算任务实施初始队列：创建一个空队列入队:在队尾添加一个新的数据元素出队:删除队头的数据元素取队头元素:获取队头的数据元素求队列长度:获取队列中数据元素的个数判断队列是否为空:判断队列中是否有数据元素判断队列是否为满:判断队列中数据元素是否超过了队列可容纳的最大的数据元素个数ABCD入队队头队尾出队队尾队列的基本操作步骤三：定义队列的抽象数据类型任务实施队列抽象数据类型ADT队列（queue）数据对象：

D={ai|0≤i≤n-1,n≥0,ai为E类型}数据关系:

R={<ai,ai+1>|ai,ai+1∈D,i=0,...,n-2}数据操作：将对队列的基本操作定义在接口IQueue中，代码如下:public

interfaceIQueue<E>{booleanenqueue(Eitem);//入队

Edequeue();//出队

Epeek();//取队头元素

intsize();//求队列的长度

voidclear();//清空队列

booleanisEmpty();//判断队列是否为空

boolean

isFull();//判断队列是否为满

}队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。银行取号、客户服务、消息发送、到处都有队列的应用！任务二

用顺序队列实现排队叫号学习目标理解队列的顺序存储结构理解顺序队列的实现方法12能用顺序队列实现排队叫号3

在任务一中，己分析出排队叫号问题的顾客服务号的逻辑结构为队列，并定义了队列的抽象数据类型。接下来考虑将逻辑结构为队列的服务号存储到计算机中去，进行存储结构的设计。存储结构有顺序存储结构和链式存储结构两种，本任务将队列的逻辑结构映射成顺序存储结构，并基于顺序存储结构实现队列的基本运算，最后，将己实现的顺序队列应用到排队叫号问题中，编写程序实现排队叫号。任务描述步骤一：将队列的逻辑结构映射成顺序存储结构任务实施队列的顺序存储结构用一片连续的存储空间来存储队列中的数据元素，这样的队列称为顺序队列(sequencequeue)。队头设置在最近一个己经离开队列的元素所占的位置，用front表示；队尾设置在最近一个进入队列的元素位置，用rear表示。front和rear随着插入和删除而变化。当队列为空时，front=rear=-1。队尾指示器rear到达数组的上限处而front为-1时，队列为满。

队列的顺序存储结构将顺序队列看成是首尾相接的循环结构，头尾指示器的关系不变，这种队列叫循环顺序队列(circularsequencequeue)。队尾指示器的加1操作修改为：rear=(rear+1)%maxsize，队头指示器的加1操作修改为：front=(front+1)%maxsize判断队空的条件是rear==front，判断队满的条件是(rear+1)%maxsize==front（少用一个空间）。求循环队列中数据元素的个数可由(rear-front+maxsize)%maxsize公式求得创建一个顺序队列创建一个顺序队列类SeqQueue<E>，该类实现接口IQueue<E>。定义4个类变量data、maxsize、front和rear：data：为一维数组，用来存储队列中的数据元素，元素类型为泛型。maxsize：为表示顺序队列的最大容量，预先为顺序栈队列分配最大存储空间。front：最近一个己经离开队列的元素所占的位置。rear:最近一个进行入队列的元素的位置public

classSeqQueue<E>implementsIQueue<E>{

private

int

maxsize;

privateE[]data;

private

int

front;

private

int

rear;

//初始化队列

……

//IQueue接口中定义的运算方法……

}初始化顺序队列初始化顺序队列就是创建一个空队列，即调用SeqQueue<E>的构造函数，申请顺序存储空间：maxsize：初始化maxsize为实际值。data：为数组申请可以存储maxsize个数据元素的存储空间，数据元素的类型由实际应用而定。front：初始化front的值为-1rear：初始化rear的值为-1

public

classSeqQueue<E>implementsIQueue<E>{

private

int

maxsize;

privateE[]data;

private

int

front;

private

int

rear;

//初始化队列publicSeqQueue(Class<E>type,int

maxsize){this.maxsize=maxsize;

data=(E[])Array.newInstance(type,maxsize);

front=rear=-1;}

//IQueue接口中定义的运算方法……

}顺序存储队列，像一列紧密排列、纪律严明的队伍。它按顺序存储，数据规整有序。入队如新人依次加入，位置紧凑；出队似排头率先离开，整体依次前移。操作简单高效，存储空间连续稳定，精准高效地完成数据的进出管理，为程序稳定运行默默贡献力量。步骤二：基于顺序表存储结构实现队列的基本运算任务实施求队列长度、判断为空、判断为满//求队列的长度public

intsize(){

return(rear-front+maxsize)%maxsize;

}//判断队列是否为空public

booleanisEmpty(){

return

front==rear;} //判断循环顺序队列是否为满public

booleanisFull(){

if((rear+1)%maxsize==front)

return

true;

else

return

false;}求表长度：返回队列中所有数据元素的个数。循环顺序队列的长度取决于队尾指示器rear和队头指示器front。一般情况下，rear大于front，因为入队的元素肯定比出队的元素多。特殊的情况是rear到达数组的上限之后又从数组的低端开始，此时，rear是小于front的。所以rear的大小要加上maxsize。

判断为空：如队列中不包含任何数据元素，则返回true，否则返回false。

front指向队列的队头，rear指向队列的队尾。当front等于rear时，意味着队列中没有元素，方法返回true，表示队列为空；反之，若不相等则返回false，表示队列不为空。判断为满：如队列中数据元素个数己达到最大容量，返回true，否则返回false。循环顺序队列为满的条件是（rear+1)%maxsize==front，实际上此时队列还有一个空位置，就是front所指示的位置。这样队列存储区有效空间比定义的最大空间少一个单元。

入队操作是将一个给定的元素保存在队列的尾部入队操作offer(Ea))（1）判断队列是否是满的，如果是，返回false；否则执行下面的步骤。（2）设置rear的值为(rear+1)%maxsize，使rear指向要插入元素的位置。（3）设置数组下标为rear位置的值为入队元素的值。//入队列操作public

booleanoffer(Ea){

if(isFull())

return

false;

rear=(rear+1)%maxsize;

data[rear]=a;

return

true; }top-1出队操作是指在队列不为空的情况下，删除队列的前端元素。出队操作poll()（1）检查队列是否为空，如果为空，返回null；否则执行下面的步骤。（2）设置front的值为(front+1)%maxsize,使front指向要删除元素的位置。（3）返回队头指示器front所在位置的元素。//出队列操作publicEpoll(){

if(isEmpty())

return

null;

front=(front+1)%maxsize;

return

data[front];}取队头元素操作与出队操作相似，只是取队头元素操作不改变原有队列，不删除取出的队头元素。取队头元素：peek()（1）检查队列是否为空，如果为空，返回null；否则执行下面的步骤。（2）返回队头指示器front所在位置的元素。//取对头元素

publicEpeek(){

if(isEmpty())

return

null;

return

data[(front+1)%maxsize];} 步骤三：对循环顺序队列实现的基本操作进行测试任务实施使用队列数据结构进行元素的入队和出队操作。测试顺序栈public

static

voidmain(String[]args){

int[]data={23,45,3,7,6,945};

//注意给定的循环队列长度至少要比实际长度大1

IQueue<Integer>queue=new

SeqQueue<Integer>(Integer.class,data.length+1);

//入队操作

System.out.println("*******入队操作*******");

for(inti=0;i<data.length;i++){ queue.offer(data[i]);System.out.println(data[i]+"入队");}

intsize=queue.size();

//出队操作

System.out.println("*******出队操作*******");

for(inti=0;i<size;i++){System.out.println(queue.poll()+"出队");

}

}}类定义:定义了一个名为TestQueue的公共类。主方法:定义了程序的入口点，即主方法。数据初始化:定义并初始化了一个整型数组data，包含六个整数。队列的创建:创建一个队列实例。入队操作:通过一个for循环，代码遍历data数组，并使用queue.offer(data[i])将每个元素依次入队。同时，每次入队后都会打印出当前入队的元素值。获取队列的大小:获取队列中当前元素的数量，并将其存储在变量size中。出队操作:通过另一个for循环，代码执行出队操作size次。每次出队后，都会打印出被移除的元素值。基于顺序队列实现入队与出队，宛如一场有序接力赛。入队时，新元素如同活力选手依次就位，为队列注入新能量，增添无限可能。出队时，元素如先锋般率先出发，勇敢担当，引领后续进程。这一进一出间，秩序井然，高效协作，尽显规则之美与奋进之力，助力系统稳定运转，迈向成功彼岸。任务三

用链队列实现排队叫号学习目标理解队列的链式存储结构掌握链队列基本操作的实现方法12能用链队列实现排队叫号3

在任务二中用顺序队列实现了排队叫号，但在用顺序队列存储顾客的服务序号时，是有容量限制的，最大容量为maxsize，如果超过了这个容量，新来的顾客就不能申请到服务序号。有时，一些排队软件不需要这个限制，为了解决这个问题，可以采用链式存储结构存储服务序号队列，本任务将队列的逻辑结构映射成链式存储结构，基于链式存储结构实现队列的基本运算，并将链队列应用在排队叫号问题中。。任务描述步骤一：将队列的逻辑结构映射成链式存储结构任务实施队列的链式存储结构用链式存储结构存储的队列称为链队列(linkedqueue)。链队列通常用单链表来表示。链队列结点的结构与单链表结点的结构一样，由数据域data和引用域next两部分组成。设队头指针为front指向链队列的第一个数据元素，队尾指针rear指向链队列的最后一个数据元素。链队列的结构示意图链队列的结点结构创建一个链队列创建一个链队列类LinkQueue<E>，该类实现接口IQueue<E>，接口中定义的基本操作的算法实现在步骤二完成。创建一个内部类Node,表示链队列的结点类型，包含两个成员变量：data是结点数据域，类型为泛型，next是下一个结点的引用域，类型为Node。定义三个类变量front、rear、maxsize，其中front为队头指针，rear为队尾指针，maxsize为队列的容量，假如为0，不限容量。public

classLinkQueue<E>implementsIQueue<E>{

private

classNode{Edata;Nodenext;

publicNode(Edata){

this.data=data;}}

privateNodefront;//队头指针

privateNoderear;//队尾指针private

int

maxsize;//队列的容量，假如为0，不限容量//初始化队列

……//IQueue接口中定义的运算方法

……}初始化链队列初始化链队列就是创建一个空队列，在Java中通过调用类的构造函数进行初如化。将队头指针front和队尾指针rear设为null。根据队列是否限容时将其设为0或指定的容量数值。

public

classLinkQueue<E>implementsIQueue<E>{

private

classNode{Edata;Nodenext;

publicNode(Edata){

this.data=data;}}

privateNodefront;//队头指针

privateNoderear;//队尾指针private

int

maxsize;//队列的容量，假如为0，不限容量//初始化不限容量的链队列publicLinkQueue(){

front=rear=null;

maxsize=0;}

//初始化限容量的链队列

publicLinkQueue(int

maxsize){

this.maxsize=maxsize;}//IQueue接口中定义的运算方法

……}链队列以其灵活的内存分配和高效的元素管理著称。它采用链表形式，节点间通过指针相连，头尾指针分别指向队列的首尾元素，实现了元素的先进先出。这种存储结构不仅节省空间，还能在动态环境中保持高性能，展现出强大的适应性和稳定性，是数据处理中的优选方案。。步骤二：完成链队列类中队列的基本运算算法任务实施求队列长度、判断为空、判断为满//求队列的长度public

intsize(){

int

n=0;

Nodep=front;

while(p!=null){

n++;

p=p.next;

}

return

n;}//判断队列是否为空public

booleanisEmpty(){

return

front==null;} //判断循环顺序队列是否为满public

booleanisFull(){

if(maxsize!=0&&size()==maxsize){

return

true;

}else{

return

false;

}}求表长度：返回队列中所有数据元素的个数。使用一个while循环来遍历链表。循环的条件是p不等于null，意味着只要p还指向一个有效的结点，循环就继续。n++;:在循环体内，每次迭代都将n的值增加1。这表示访问了一个结点，因此链表的结点数量增加1。p=p.next;:将p更新为当前结点的下一个结点。这是通过访问当前结点的next属性实现的，该属性存储了对下一个结点的引用判断为空：如队列中不包含任何数据元素，则返回true，否则返回false。

队空时，队头指针front=null和队尾指针rear=null，只要front=null，就可断定队列中没有元素。判断为满：如队列中数据元素个数己达到最大容量，返回true，否则返回false。从理论上讲链队列是没有容量限制的，但在实际应用中有时需要对队列的容量进行限制，这里使用maxsize属性，如果该属性为0，说明没有容量限制。因此判断队列为满的条件是如果maxsize不为0并且队列的长度等于maxsize，则返回true，否则返回false。

入队操作是将一个给定的元素保存在队列的尾部入队操作offer(Ea))（1）创建一个新结点，为新结点分配内存和值（2）如果队列为空，将front和rear都指向新结点。（3）如果队列不为空，将rear的next指向新结点,rear指向新结点//入队列操作public

booleanoffer(Ea){

if(!isFull())

return

false;Nodenewnode=newNode(a);

if(isEmpty()){

front=newnode;

rear=newnode;}else{rear.next=newnode;

rear=newnode;}

return

true;}top-1出队操作是指在队列不为空的情况下，删除队列的前端元素。出队操作poll()（1）如果队列为空，返回null。（2）将front指向拟出队结点存放在一个临时变量node里。（3）将front指向链队列中的下一个结点，使之成为队列头结点。（4）如果front为null，将rear也设为null。（5）将出队结点的node的数据返回给调用者。//出队列操作publicEpoll(){

if(isEmpty())

return

null;Nodenode=front;

front=front.next;

if(front==null){

rear=null;}

return

node.data;}取队头元素操作与出队操作相似，只是取队头元素操作不改变原有队列，不删除取出的队头元素。取队头元素：peek()//取对头元素

publicEpeek(){

if(!isEmpty())

return

null;

else

return

front.data;}

（1）如果队列为空，返回null。（2）否则将出队结点的node的数据返回给调用者。步骤三：对链队列实现的基本运算的算法进行测试任务实施使用队列数据结构进行元素的入队和出队操作。测试顺序栈public

static

voidmain(String[]args){

int[]data={23,45,3,7,6,945};

//注意给定的循环队列长度至少要比实际长度大1

IQueue<Integer>queue=newLinkQueue<Integer>();

//入队操作

System.out.println("*******入队操作*******");

for(inti=0;i<data.length;i++){ queue.offer(data[i]);System.out.println(data[i]+"入队");}

intsize=queue.size();

//出队操作

System.out.println("*******出队操作*******");

for(inti=0;i<size;i++){System.