数据结构(牛小飞)6队列.ppt

队列的定义,队 列(Queue),小结,队列的应用,复习,链式队列及基本操作的实现,顺序队列及基本操作的实现,复习-栈,1、特殊的线性表：插入和删除操作发生在表尾 的线性表,2、特点：先进后出(Last In First Out),3、基本操作：,构造函数、push，pop，isEmpty，makeEmpty,4、用途：常用的数据结构,复习-顺序栈,public class ArrayStack private AnyType theArray;private int topOfStack;private static final int MAXSIZE=10;成员方法：,栈顶,复习-链式栈,栈顶,栈底,public class SingleLinkedStack private Node top;private int theSize;成员方法；,队列模型,队列是线性表的特例。,队列(queue)同栈一样，也是特殊表。,(a1,a2,a3,an-1,an),表头(队头),表尾(队尾),是插入在一端（队尾）进行而删除在另一端（队头）进行的表。,队列模型,队列的基本操作：enqueue(入队)：dequeue(出队)：,插入操作在队尾(back),删除操作在队头(front),(a1,a2,a3,an-1,an),队头,队尾,队列模型,队列模型：通过enqueue向队列中输入，通过dequeue从队列中输出,队列模型：在删除端进行插入操作，在back端进行插入操作,将n个数a1,a2,a3,an-1,an按照下标的次序进队，然后再出队,(),(a1),(a1,a2),(a1,a2,a3),(a1,a2,a3,),(a1,a2,a3,an-1),(a1,a2,a3,an-1,an),入队过程,出队过程,队的特点：先进先出（First In First Out）,(a2,a3,an-1,an),(a1,a2,a3,an-1,an),an,an-1,a1,a2,a3,(a3,an-1,an),(an-1,an),(an-1,an),(an),(),队列模型,队列的数组实现,a1,a2,a3,front,back,0 1 2 3 4 5,每一个队列的数据结构，用一个数组theArray以及位置front和back来表示，同时还需记录实际存于队列中的元素的个数currentSize。,队列的逻辑形态,队列的基本操作：入队，出队,队列的数组实现,5,2,7,1,入队：theArrayback=x;back+;currentSize+;,出队：return theArrayfront;front+;currentSize-;,x,顺序队列的假溢出问题,顺序队列的假溢出问题,队列上溢：真上溢：队列真正满时再入队。假上溢：back已指向队尾，但队列前端仍有空位置。,解决假上溢的方法：方法一：每次删除队头一个元素后，把整个队列往前移一个位置（造成时间浪费）。方法二：循环队列,循环队列-基本思想,首尾相连：把a0和a5想象成邻居,循环队列-满与空的判定,队空：front=back队满：front=back,循环队列-满与空的判定,队空：front=back&currentSize=0队满：currentSize=MAXSIZE,public class ArrayQueue private AnyType theArray;/存储空间基址 private int front,back;/队头、队尾的下标 private int currentSize;/队列中存放的元素个数 private static final int MAXSIZE=5;/队列能存放的最大元素个数 成员方法：,构造函数,isEmpty,enQueue,deQueue,java语言描述：,循环队列的数组实现,其他方法,ArrayQueue,原形：ArrayQueue(),作用：形成一个空队列,public ArrayQueue()theArray=(AnyType)new ObjectMAXSIZE;front=back=0;currentSize=0;,isEmpty,bool isEmpty(),原形：boolean isEmpty(),作用：测试队列中是否有数据元素,if(front=back,enQueue,原形：public void enQueue(AnyType x),作用：在队尾添加数据元素,public void enQueue(AnyType x),if(currentSize=MAXSIZE)/队列已满,theArrayback=x;,currentSize+;,back=(back+1)%MAXSIZE;,enQueue,deQueue,原形：public AnyType deQueue(),作用：将队头数据元素删除，并返回该元素的值,public AnyType deQueue(),if(front=back)/空队列 isEmpty（）,AnyType deQueueVal=theArrayfront;,currentSize-;,front=(front+1)%MAXSIZE;,return deQueueVal;,deQueue,其他成员方法,public void makeEmpty()back=front=0;currentSize=0;,public AnyType getFront()if(isEmpty()return theArrayfront;,链表的选用,单链表,双向链表,链表的选用,链式队列的逻辑形态,队空?,front=null,back=null,队满?,似乎无限,队中数据元素的个数?,队头,队尾,public class SingleLinkedQueue,java语言描述：,private Node front,back;/队头、队尾,public void makeEmpty()front=back=null;currentSize=0;,public SingleLinkedQueue()front=back=null;currentSize=0;,public boolean isEmpty()return currentSize=0;,private int currentSize;,public AnyType deQueue(),public void enQueue(AnyType x),链式队列的实现,循环链式队列的讨论,enQueue,public void enQueue(AnyType x),Node p=new Node(x);,else,if(front=null),back.next=p;,back=p;,front=back=p;,deQueue,public AnyType deQueue(),if(front=null),oldVal=front.data;,return null;,front=front.next;,if(front=null),return oldVal;,else,currentSize-;,back=front=null;,讨论,rear,讨论-enQueue,rear.next=p;,p.next=rear.next;,rear=p;,rear,讨论-enQueue,p.next=p;,rear=p;,EnQueue,public void enQueue(AnyType x),Node p=new Node(x);,else,if(rear!=null)p.next=rear.next;rear.next=p;rear=p;,p.next=p;rear=p;,rear,L,讨论deQueue,rear.next=p.next;,p=rear.next;,return p.data;,rear,L=null,讨论deQueue,只有一个节点时：,deQueue,public AnyType deQueue(),if(rear=null)return null;/空表,p=rear.next;,return deQueueVal;,deQueueVal=p.data;,else rear.next=p.next;,if(p.next=rear)rear=null;,rear,rear,队列的应用,队列是一个十分重要的数据结构，应用很广泛。,最典型的是：生活中的排队问题基本都是队列问题。,银行业务的抽象,服务柜台,角色和过程,顾客,何时来到银行？,需要多长的办理时间？,事件,顾客到来,顾客离开,加入最短的队列,下一个顾客得到服务,小 结,链式队列,队列的基本概念,特殊的线性表,主要的操作：入队、出队,先进先出,队列应用,带头结点的单链表,入队、出队等操作的实现,顺序队列,循环队列解决假溢出,队空和队满的判定,入队、出队、长度的表达式,如何实现的循环？,