【10】Chapter6 队列-循环队列.ppt

数据结构与算法2009年秋季授课教师:张剑波方芳授课班级:111081-4班115081-2班Chapter6队列(Queue)(顺序队列)(链队列)、几个相关的概念1、定义队列是一种特殊的线性表,是一种只允许在表的一端进行插入操作,而在另一端进行删除操作的线性表。a1a2a3…an入队列出队列队头(front)队尾(rear)3、重要特征每次进队列的元素都放在原队列队尾之后而成为新的队尾元素;每次出队列的数据元素都是原队头元素;先入队列的元素先出队列,后入队列的元素后出队列。队列是一个先进先出的线性表(FirstInFirstOut,FIFO)。如:(1)日常生活中的排队;(2)操作系统中的作业队列。C课堂练****3、设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5和e6依次通过栈S,一个元素出栈后即进队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,e1,则栈S的容量至少应该是。A、6B、5C、3D、{实例 有序线性表,一端称为front,一端称为rear操作 Create(); //创建一个空的队列 IsEmpty(); //如果队列为空,返回true,否则返回false IsFull(); //如果队列满,返回true,否则返回false First(); //返回队列中的第一个元素 Last(); //返回队列中的最后一个元素 Add(x); //向队列添加元素x Delete(x); //删除队首元素,并将它传递给x}队列的两种描述形式队列的物理存储可以用:顺序存储结构链式存储结构a1,a2,a3,…,an出队列入队列队头队尾datalinkfrontrear队列的顺序存储结构,简称顺序队列;顺序队列可用一个一维数组queue[MaxSize]来存储,其中MaxSize是队列能存放的最大元素个数;为了指示队头和队尾,需要设立一个队头指示器和一个队尾指示器,或称队头指针、队尾指针,为了算法设计上的方便,约定:front(头指针):指向实际队头元素的前一个位置;rear(尾指针):指向实际队尾元素所在的位置。(顺序存储结构)(1)初始化(2)入队列(插入)建立一个空队列,即队头指针front=-1,队尾指针rear=-1。当队满时(队满条件:rear==MaxSize-1),产生溢出;当队不满时,尾指针加1(rear=rear+1),然后把待插元素x送入尾指针所指数组分量。1、顺序队列的基本操作(3)出队列(删除)当队不空时(队空条件:front==rear),队头指针加1(front=front+1),返回原队头元素,即头指针所指数组分量的值。