数据结构(Java语言描述)(第2版)课件 3.2 队列_第1页
数据结构(Java语言描述)(第2版)课件 3.2 队列_第2页
数据结构(Java语言描述)(第2版)课件 3.2 队列_第3页
数据结构(Java语言描述)(第2版)课件 3.2 队列_第4页
数据结构(Java语言描述)(第2版)课件 3.2 队列_第5页
已阅读5页,还剩36页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

数据结构主讲人:闾枫常州信息职业技术学院3.2队列队列和栈一样,也是操作受限的线性表。现实生活中队列随处可见,如超市购物排队结账、银行排队等待办理业务、计算机操作系统的作业调度、打印机缓冲区等都是队列应用的体现。引言IntroductionPart01队列的抽象数据类型队列(Queue)是插入和删除操作在线性表的两端进行,一端允许插入操作,而另一端只允许删除操作,允许插入的一端称为队尾(Rear),允许删除的另一端则称为队头(Front)。队列的插入操作通常称为入队或进队,删除操作通常称为出队。如果队列中没有元素,则称为空队列。队列的插入操作在队尾,删除操作在队头,因此最先入队也会最先出队,最后进队的最后出队,队列具有先进先出(FIFO,FirstInFirstOut)的特征。队列(Queue)说明队列的定义a1a2a3……

an队头队尾出队进队队列的插入和删除操作在两端进行,使用队头指针(front)和队尾指针(rear)表示队列的操作的两端。队列的基本操作主要有创建队列、入队、出队、取队头元素、判断队列是否为空等。设计队列的抽象数据类型接口Queue,其中的操作数据元素用泛型描述。队列的抽象数据类型//队列抽象数据类型,其中T表示队列中数据的类型public

interfaceQueue<T>{

public

voidenqueue(Tt);//元素入队,在队尾插入元素T

publicTdequeue();//元素出队,队头元素出队

publicTpeek();//取队头元素值,但队头元素不出队

public

booleanisEmpty();//判断队列是否为空}Part02顺序队列顺序队列的存储结构队列的顺序存储称为顺序队列(SequentialQueue)。顺序队列用一个一维数组存放元素数据,用两个变量front和rear,分别表示队头和队尾的位置。public

classSeqQueue<T>implementsQueue<T>{

privateT[]queue=null;//声明一维数组,存储队列元素

private

int

length;//数组的大小,表示队列的最大容量

private

int

front;//表示队头位置

private

int

rear;//表示队尾位置 //实现队列接口的相关方法 ……}顺序队列的基本操作初始队列中有3个元素01234frontrear一个队列初始有3个元素a、b、c,元素存储在数组的前3个单元中。下标为0的一端为队头,元素d进队时,只要队列未满,直接在队尾增加即可;元素a出队操作时,若要保证队头位置不空,剩下元素仍然在数组的前列,则需要所有剩下元素向前移动一个位置dabc元素d进队元素a出队时间复杂度为O(n)顺序队列的基本操作初始空队列,长度为501234元素a、b、c入队

frontrear若不限定队列的所有元素存储在数组的前n个单元中,即队头不需要固定在下标为0的位置,元素出队时,移动队头的位置,元素进队时,移动队尾的位置初始空队列,队头front和队尾rear值均为-1,并且front定位在队头元素的前一个位置,rear定位在队尾元素位置约定abc元素a、b出队顺序队列的基本操作cde01234frontrear队列中已有3个元素,这时如果再有一个元素f想入队,此时rear值为4,再做加1,值已经超出数组下标范围,出现越界溢出。而此时队列头部元素a、b已出队,队列是有空闲的,这种现象称为“假溢出”。解决假溢出最好的办法是将队列设计成头尾相接的循环结构。顺序循环队列顺序循环队列是将顺序队列设计成逻辑上头尾相接的循环结构cde01234frontrearfrontrear01234cde顺序队列顺序循环队列frear顺序循环队列出队操作时改变front值,计算表达式为:front=(front+1)%lengthfrontrear01234cdefrear循环队列入队或出队操作时,队头和队尾位置移动时,不能简单的执行加1操作,可能会存在越界情况入队操作时改变rear值,计算表达式为:rear=(rear+1)%lengthrear=(4+1)%5可用取模运算使值在0--length-1顺序循环队列约定队列中预留一个空位,在队头位置和队尾位置相差为1时,即认为队列已满,此时队满条件为:front=(rear+1)%length,队列中最多放length-1个元素。队列中有元素c、d、e、ffrontrear01234cdef队空和队满判断元素g入队rearg队空队满队空条件为:front=rear队满条件为:front=(rear+1)%length队列中有元素c、d、efrontrear012dce43frontfrontfront元素c、d、e出队队列为空,队头和队尾相等队空和队满时,front和rear值均相等,那该如何判定队空和队满呢?顺序循环队列队列初始化为空frontrear01243定义顺序循环队列SeqCirQueue类实现队列接口Queue,定义泛型数组queue用于存储数据元素,定义变量length表示队列长度,定义整型变量front和rear分别表示队头和队尾位置。public

classSeqCirQueue<T>implements

Queue<T>{

privateT[]queue=null;//声明一维数组,存储队列元素

private

int

length;//数组的大小,表示队列的最大容量

private

int

front;//表示队头位置

private

int

rear;//表示队尾位置

//队列初始化

publicSeqCirQueue(){

queue=(T[])newObject[16];//构造一维的泛型数组,默认大小为16,存储队列元素

length=16;

front=rear=0;//初始队列为空 }

publicSeqCirQueue(int

length){

queue=(T[])newObject[length];//构造一维的泛型数组,存储队列元素

this.length=length;

front=rear=0;//初始队列为空 }……}顺序循环队列入队操作元素a、b、c入队rear01243front元素d入队,队满rearrearrearrearfront=(rear+1)%length//元素入队@Overridepublic

void

enqueue(Tt){//判断队列是否满,若已满,则抛出异常,若未满,队尾位置向前移动1,插入元素

if(front==(rear+1)%length){

throw

newRuntimeException("队列已满,元素不能入队"); }else{

rear=(rear+1)%length;

queue[rear]=t; }}abcd顺序循环队列出队操作front=rearrear01243cdeffront元素c、d、e、f出队frontfrontfrontfront//元素出队@OverridepublicTdequeue(){//判断队列是否空,若为空,抛出异常,若不为空,队头位置向前移动1,取出元素

if(isEmpty()){

throw

newRuntimeException("队列空,没有元素出队"); }else{

front=(front+1)%length; Tt=queue[front];

queue[front]=null;

return

t; }}时间复杂度为O(1)顺序循环队列//取队头元素@OverridepublicTpeek(){//判断队列是否空,若为空,抛出异常,若不为空,直接取出队头元素

if(isEmpty()){

throw

newRuntimeException("队列空,没有元素获取"); }else{

return

queue[front+1];//直接将队头元素取出 }}判队空取队头元素//判断队列是否为空

@Override

public

boolean

isEmpty(){

//队头和队尾指向同一个位置,表示队列为空

return

front==rear; }获取队头元素和出队操作的区别在于,队头位置不移动。Part03链式队列在循环队列中,若队列已满,再有元素入队,就会出现“真溢出”现象,这时队列可用链式结构存储。队列的链式存储称为链式队列,简称链队。链式队列的存储结构链式队列其实就是单链表,只是操作限制了队尾插入元素,队头删除元素。链队使用带头结点的单链表实现,需要设置队头(front)和队尾(rear)两个指针,分别指向链队的头结点和尾结点。当队头和队尾指针都指向头结点时,表示是一个空队列。a1a2an^front……rearfront^rear链式队列的基本操作//链式队列类public

classLinkedQueue<T>implementsQueue<T>{

privateLinkedNode<T>front,rear;//表示队头,队尾指针

//队列初始化

publicLinkedQueue(){

front=rear=newLinkedNode<T>();//初始空队列,队头和队尾指向一个空的头结点 }

//实现队列接口的相关方法

……}链队类结构链式队列的基本操作入队操作nodefrontreararear(1)创建新结点node初始空队列时,队头front和队尾rear都指向头结点。(2)结点node入队nodeb^^^时间复杂度为O(1)(3)移动队尾指针链式队列的基本操作入队操作实现//元素入队@Overridepublic

voidenqueue(Tt){

//先构造新结点,在队尾处插入新结点,再移动队尾指针指向新结点 LinkedNode<T>node=newLinkedNode<T>(t,null);

rear.setNext(node);//新结点插入队尾

rear=node;//移动队尾指针}链式队列的基本操作出队操作元素出队,就是头结点的后继结点(如为结点node)出队nodefrontarearb^(1)node指向出队的元素结点(2)头结点的后继结点改为node的后继结点只有一个元素时,该元素出队只需要将队尾指针rear指向头结点^node时间复杂度为O(1)链式队列的基本操作出队操作实现//元素出队@OverridepublicTdequeue(){

//先获取队头元素,再移动队头指针指向下一个结点,若队列只有一个元素,出队后队列为空,则移动队尾指针指向头结点

if(isEmpty())

throw

newRuntimeException("队列为空,没有元素可出队"); LinkedNode<T>node=front.getNext();//保存要出队的队头结点

front.setNext(node.getNext());//队头指针指向node的后继结点

if(node.getNext()==null)//若队列中只有一个元素

rear=front;//元素出队后,队列为空,队尾和队头指针都指向头结点

return

node.getData();}链式队列的基本操作判断队空取队头元素//取队头元素@OverridepublicTpeek(){//判断队列是否为空,若为空,则抛出异常,若不为空,则获取队头元素

if(isEmpty()){

throw

newRuntimeException("队列为空"); }else{

return

front.getNext().getData();//取队头元素值返回 }}//判断链队是否为空@Overridepublic

booleanisEmpty(){

if(front==rear)

return

true; else

return

false;}顺序循环队列和链式队列的对比顺序循环队列链式队列操作的时间复杂度为O(1)操作的时间复杂度为O(1)存在空间浪费和溢出问题结点有数据域和引用域,增加引用域的存储开销元素个数变化不大且不会溢出,使用循环队列若个数变化较大,可使用链式队列编写代码实现,将十进制小数转换为二进制小数(使用乘2取整法)课堂实践Part04队列的应用队列的应用队列求解约瑟夫环问题算法分析:用队列存放n个人,从第一个人开始报数,判断若是m,则直接出队,若不是m,则出队后重新入队,即排到队尾,依次判断,直到队列为空。问题描述:n个人围成一圈,从第一个人开始报数,报到m的人出列,再由下一个人重新从1开始报数,报到m的人再出列,依次类推,直到剩下最后一个人,输出每次出列的人的编号。frontrear01234bcda有4个人为a、b、c、d,进入顺序循环队列从a开始,报到3的人出队,若报数不是3,则排到队尾a报数1,出队,不是3,则a再入队rearb报数2,出队,不是3,则b再入队frontrearc报数3,直接出队frontreard报数1,出队,不是3,则d再入队队列的应用队列求解约瑟夫环问题//约瑟夫环问题public

classJosephusRing{//n表示人数,m是所报的数public

voidoutQueue(int

n,int

m){//创建队列存放人LinkedQueue<Integer>rings=newLinkedQueue<Integer>();//n个人按顺序入队for(int

i=1;i<=n;i++){

rings.enqueue(i);}int

count=0;//统计报数while(!rings.isEmpty()){//只要队列不空,一直报数 Integerdeq=rings.dequeue();//元素出队

count++;

if(count%m==0){//如果正好报数的是m,则输出,否则再次入队 System.out.print(deq+"");//输出

count=0; }else{

rings.enqueue(deq);//元素再次入队,到队尾 }}}}public

classTestJR{

public

static

voidmain(String[]args){

//10个人围成一圈,报到3的人出队 System.out.println("出队顺序为:");

newJosephusRing().outQueue(10,3); }}队列的应用舞伴配对问题问题描述:在舞会上男女各自排成一队,每曲开始时,依次从男队和女队各出一人配成舞伴,本曲没成功配对者,坐着等待下一曲找舞伴,舞曲结束,双方可以再次进队,等待新的配对。两队初始人数可以不等,较长的那一队中未配对者等待下一轮舞曲。算法分析:根据性别分别创建两个队列Q1(女生)和Q2(男生),舞会开始时,Q1和Q2的队头元素同时出队,进行配对。配对结束,再次进到队尾,等待再次轮换。F1F2F3rearfrontfrontrear女生队列初始化,设有三人男生队列初始化,设有五人开始配对配对结束,再次进队^M3M4M5M1M2^队列的应用舞伴配对问题M1//舞会配对public

classDancingPartner{//同时读取Q1和Q2的内容,进行配对,n表示配对的轮次,每次配对结束就回到队尾,等待再次轮换

public

voidmatch(LinkedQueue<Dancer>Q1,LinkedQueue<Dancer>Q2,int

n){

int

count=0;

//同时读取Q1和Q2的内容,进行配对

while(!Q1.isEmpty()&&!Q2.isEmpty()){

//元素分别出队 Dancerfemale=Q1.dequeue(); Dancermale=Q2.dequeue();

//输出信息 System.out.println(female+"----"+male);

//元素再次入到队尾

Q1.enqueue(female);

Q2.enqueue(male);

count++;

if(count==n)break; } }}//测试舞会配对public

classTestDancingPartner{

public

static

voidmain(String[]args){

//创建两个队列,用于保存女生和男生信息 LinkedQueue<Dancer>Q1=newLinkedQueue<Dancer>(); LinkedQueue<Dancer>Q2=newLinkedQueue<Dancer>();

//队列进行初始化

for(int

i=1;i<=3;i++){ Dancerdancer=newDancer("lady"+i,"female");

Q1.enqueue(dancer); }

for(int

i=1;i<=5;i++){ Dancerdancer=newDancer("gentlment"+i,"male");

Q2.enqueue(dancer); }

//5首舞曲

newDancingPartner().match(Q1,Q2,5); }}lady1----gentlment1lady2----gentlment2lady3----gentlment3lady1----gentlment4lady2----gentlment5Part05优先队列实际情况中,有些按“先来先服务”原则不能满足需求,还需要将任务的重要或紧急程度作为排队处理的依据。如一般医院急诊室,会以最严重的患者优先诊治,计算机CPU的进程调度管理,优先级高的进程先执行。优先队列优先队列(PriorityQueue)作为一种特殊的队列,不必遵守队列先进先出的特性,而根据元素的优先级决定元素出队操作。优先队列需要保证:每次出队总是队列中优先级最高的元素优先级的含义:由具体应用定义,存入队列中的元素附有表示优先级的数值,标识这个元素的优先程度任务名P1P2P3P4优先级4628设定优先级数值越小优先级越高,数值越大优先级越低出队顺序为:P3、P1、P2、P4优先队列此时入队效率较高,而出队效率较低,且出队不一定在队头。入队时,保证队列中的数据按优先级从大到小排列,则任何时候队头出队的都是优先级最高的元素。入队时,采用直接在队尾入队,不考虑元素优先级,而在出队时进行检索,找到优先级最高的元素出队。基本操作判断是否为空、入队、出队、取队头元素等入队操作为保证优先级的有序,效率可能较低,但出队比较方便。时间复杂度为O(n)优先队列入队时保证元素始终按优先级数据递增排列,保证每次出队的是优先级最高的元素,采用有序单链表存储数据。优先队列实现

//取队头元素

@Override

publicTpeek(){

//取队列中的第一个元素,并不出队

return

priorityQueue.get(0); }

@Override

public

booleanisEmpty(){

//判断链表是否为空

return

priorityQueue.isEmpty(); }

publicStringtoString(){

Node

p=priorityQueue.head.next; StringBufferdatas=newStringBuffer();

while(p!=null){

datas.append(p.data+"");//输出结点的数据域

p=p.next;//指针后移一个结点 }

return

datas.toString(); }}//优先队列public

classMyPriorityQueue<TextendsComparable<T>>implementsQueue<T>{

privateSortedSinglyList<T>priorityQueue;//使用有序单链表表示优先队列,插入队列的元素以递增排列

//队列初始化

publicMyPriorityQueue(){

priorityQueue=newSortedSinglyList(); }

//元素入队

@Override

public

voidenqueue(Tt){

//根据参数值大小,将元素插入到指定位置,此时不是单纯的在队尾入队

priorityQueue.insert(t); }

//元素出队

@Override

publicTdequeue(){

//返回队头元素,并从队列中移除

return

priorityQueue.remove(0); }优先队列优先队列实现public

classMyProcessimplementsComparable<MyProcess>{

privateStringpname;//进程名字

private

int

priority;//进程优先级

publicMyProcess(Stringpname){

this(pname,5); }

//使用名字和优先级构造进程,若优先级不在1-10之间,则抛出异常

publicMyProcess(Stringpname,int

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论