合取学院 第5章队列及其应用 HEFEI UNIVERSITY 第5章队列及其应用 r5.1队列的基本概念 5.2顺序队列及其基本算法 5.3链队列及其基本算法 5.4队列的应用举例 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(20071120)
第5章 队列及其应用 1 ☞5.1 队列的基本概念 5.2 顺序队列及其基本算法 5.3 链队列及其基本算法 5.4 队列的应用举例 第5章 队列及其应用
⊙合雕学院 第5章队列及其应用 HEFEI UNIVERSITY 5.1队列的基本概念 m5.1.1队列的定义 5.1.2队列的基本运算 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(20071山20)
第5章 队列及其应用 2 ☞5.1.1 队列的定义 5.1.2 队列的基本运算 5.1 队列的基本概念
⑧合取学院 第5章队列及其应用 HEFEI UNIVERSITY 定义队列是满足下列条件的数据元素集合： (1)有限个具有相同数据类型的数据元素的集合，D= {a:i=1,2,…,n},a为数据元素。 (2)数据元素之间的关系为R={Ka1,a+1>a:, a+1∈D,i=1,2，…,n (3)a为队头元素，a为队尾元素：数据元素按a1,2 ,..,a的次序入队，也以相同的次序出队 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(2007-1120)
第5章 队列及其应用 3 定义 队列是满足下列条件的数据元素集合： (1) 有限个具有相同数据类型的数据元素的集合，D = { ai | i=1，2，…，n }，ai为数据元素。 (2) 数据元素之间的关系为R = {| ai， ai+1∈D，i=1，2，…，n}； (3) a1为队头元素，an为队尾元素；数据元素按a1，a2 ，…，an的次序入队，也以相同的次序出队
⑧ 合取学院 第5章队列及其应用 HEFEI UNIVERSITY 由定义可以看出，队列是由一组同类型数据元素 (a1,a2,.,a)组成的线性序列 其中，a(1<<)可以是原子类型（如整型、实型 字符型等)、或是结构类型的数据元素。在一个队列 中，元素a是a的唯一直接前驱，a+1是a的唯一直接 后继：而队头元素a无前驱，队尾元素a无后继 因此，队列属于线性逻辑结构。 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(2007-1120)
第5章 队列及其应用 4 由定义可以看出，队列是由一组同类型数据元素 (a1，a2，…，an )组成的线性序列。 其中，ai (1≤i≤n)可以是原子类型(如整型、实型、 字符型等)、或是结构类型的数据元素。在一个队列 中，元素ai-1是ai的唯一直接前驱，ai+1是ai的唯一直接 后继；而队头元素a1无前驱，队尾元素an无后继。 因此，队列属于线性逻辑结构
⑧合取学院 第5章队列及其应用 HEFEI UNIVERSITY 即：队列是限定仅在一端进行插入，而在另一端进行 删除操作的线性表 允许删除的一端称为队头(front),允许插入的一端 称为队尾(rear). 当队列中没有元素时称为空队列。在空队列中依次 加入元素a1,a2,.an之后，a1是队头元素，an是队尾 元素。显然退出队列的次序也只能是a1,a2,.an,也 就是说队列的修改是依先进先出的原则进行的。 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(20071山20)
第5章 队列及其应用 5 即：队列是限定仅在一端进行插入，而在另一端进行 删除操作的线性表。 允许删除的一端称为队头(front)，允许插入的一端 称为队尾(rear)。 当队列中没有元素时称为空队列。在空队列中依次 加入元素a1,a2,…an之后，a1是队头元素，an是队尾 元素。显然退出队列的次序也只能是a1,a2,…an ，也 就是说队列的修改是依先进先出的原则进行的
⑧合取学院 第5章队列及其应用 HEFEI UNIVERSITY 队列的特点 一根据队列的定义可知，最先入队的元素也是最先 出队。 r特点：先进先出(FIFO) 也就是说，队列是一种先进先出(First In First Out的线性表，简称为FIFO表 出队列 入队列 a1 a2 a3............an 队头 队尾 front rear 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(200711一20)
第5章 队列及其应用 6 队列的特点 ☞ 根据队列的定义可知，最先入队的元素也是最先 出队。 ☞ 特点：先进先出（FIFO） 也就是说，队列是一种先进先出(First In First Out)的线性表，简称为FIFO表。 a1 a2 a3 …………an 出队列 入队列 队头 front 队尾 rear
合取学院 第5章队列及其应用 HEFEI UNIVERSITY 5.1队列的基本概念 5.1.1队列的定义 m5.1.2队列的基本运算 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(200711一20)
第5章 队列及其应用 7 5.1.1 队列的定义 ☞5.1.2 队列的基本运算 5.1 队列的基本概念
⊙合雕学院 第5章队列及其应用 HEFEI UNIVERSITY r定义在该逻辑结构上的运算有以下几种基本运算： (1)置空队：nitQueue(Q),InitQueuei运算的结果是 将队列Q置成空队列。 2)判队空：QueueEmpty(Q),如果队列为空，则 QueueEmptyi返回1，否则QueueEmptyi返回O。 (3)判队满：QueueFull(Q),如果队满，则QueueFull 返回1，否则QueueFull返回0。 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(20071山20)
第5章 队列及其应用 8 ☞ 定义在该逻辑结构上的运算有以下几种基本运算： (1)置空队：InitQueue (Q)，InitQueue运算的结果是 将队列Q置成空队列。 (2)判队空：QueueEmpty(Q)，如果队列为空，则 QueueEmpty返回1，否则QueueEmpty返回0。 (3)判队满：QueueFull(Q)，如果队满，则QueueFull 返回1，否则QueueFull返回0
⑧合取学院 第5章队列及其应用 HEFEI UNIVERSITY (4)入队：Add(Q,x),Add在队列Q的队尾插入元 素x。 (⑤)出队：Delete(Q),Delete从队列Q中删除队头元 素。 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(200711一20)
第5章 队列及其应用 9 (4)入队：Add (Q，x)，Add在队列Q的队尾插入元 素x。 (5)出队：Delete (Q)，Delete从队列Q中删除队头元 素
合取警院 第5章 队列及其应用 HEFEI UNIVERSITY 第5章队列及其应用 5.1队列的基本概念 m5.2顺序队列及其基本算法 5.3链队列及其基本算法 5.4队列的应用举例 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(20071120)
第5章 队列及其应用 10 5.1 队列的基本概念 ☞5.2 顺序队列及其基本算法 5.3 链队列及其基本算法 5.4 队列的应用举例 第5章 队列及其应用