队列44914323--课件(PPT演示稿).ppt

1数据结构课程的内容 2五队列 P37 ?队列的定义: 队列(queue) 也是一种特殊的线性表。所有插入操作限定在一端进行,所有删除操作限定在另一端进行。允许进行插入操作的一端称为队尾队尾,允许删除操作的另一端则称为队首队首。它的主要特点是: 先进队的数据元素将先出队先进队的数据元素将先出队。 1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式 3 ,仍为一对一关系。顺序队或链队,以循环顺序队更常见。只能在队首和队尾运算,且访问结点时依照先进先出(FIFO )的原则。关键是掌握入队和出队操作,具体实现依顺序队或链队的不同而不同。基本操作有:入队入队或出队出队,建空队列建空队列,判队空判队空或队满队满等操作。 3. 存储结构 4. 运算规则 5. 实现方式 2. 逻辑结构只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表(头删尾插) 4 队列( Queue )是仅在表尾进行插入操作,在表头进行删除操作的线性表。表尾即 a n 端,称为队尾;表头即 a 1 端,称为队头。它是一种先进先出( FIFO )的线性表。例如:队列 Q= (a 1 , a 2 , a 3 , ……….,a n-1 , a n ) 插入元素称为入队;删除元素称为出队。队头队尾?队列的存储结构为链队或顺序队(常用循环顺序队) 5 如果给定一个队列 Q: (Data 1, Data 2, Data 3,…, Data n ),如果队列中元素是按 a 1,a 2,a 3,…,a n的次序进队,如图 3-17 所示: 则从这个队列中取出所有元素的出队次序为:a 1,a 2,a 3,…,a n。换言之, 队列中元素的进队过程与出队过程是按“先进先出先进先出”的规则进行的,这是队列结构的重要特征。所以, 队列又称为先进先出先进先出 FIFO(first_in_first_out) FIFO(first_in_first_out) 的线性表的线性表。 1a 2a 1?na na6 ?1顺序队列所谓顺序队列就是使用顺序存储分配方式表示的队列。和顺序栈一样,顺序队列也可以利用 ANSI C 语言中的一维数组来实现。另外,在队列操作过程中,队头元素和队尾元素将不断地变动。为确定队头元素和队尾元素的位置,我们设置两个位置指示变两个位置指示变量: 量: front front 和和 rear rear 。。其中: front front 用于存放队头的位置, 用于存放队头的位置, rear rear 用于存放队尾的位置用于存放队尾的位置。为描述算法方便起见,设: 表示队列的数组长度为表示队列的数组长度为 maxsize maxsize ,在这里约定如下三点: ①建立队列时,队列初始(空)状态设置为 front=0 和 rear=0 。当 front=rear 时表示队列为空。②在队列未满的情况下,在队列中插入一个新的队尾元素后, rear 加1, rear 总是代表队尾元素的下一个位置,即下一个新元素进队的插人位置。③在队列未空的情况下,在每次删除一个队头元素后, front 加1 “上溢”错误:当 rear=maxsize-1( 队满)时进行入队操作; “下溢”错误:当 rear=front( 队空)时进行出队操作; 7 typedef struct { elemtype queue[maxsize]; int front; int rear; } seqqueue ; q front a 1 a 2 a 3 queue a 4 0.......99(队尾) rear 顺序队示意图 8 顺序队示意图 Q(队首) front a 1 a 2 a 3 queue a 4 0.......99(队尾) rear ②队列会满吗? 很可能会,因为数组前端空间无法释放。因此数组应当有长度限制。①空队列的特征? 约定: front=rear 入队(尾部插入): queue[rear ]=e; rear++; 出队(头部删除): x=queue[front ]; front++; 讨论: 假溢出假溢出有缺陷③怎样实现入队和出队操作? 9 问:什么叫“假溢出”?如何解决? 答: 在顺序队中,当尾指针已经到了数组的上界 rear=M ,不能再有入队操作, 但其实数组中还有空位置 front >0,这就叫“假溢出”。队列队列采用循环队列 Circular Queue 避免“假溢出”问题的两个办法: 1)一个元素出队后,将整个队列向队头端移动一个位置,使队头元素始终占据第一个数组元素 queue[0] .换言之, 使front 总是为 0. 2)将顺序