DS_2010_34数据结构课件.pdf

第三章 栈和队列(4) 《数据结构》主讲:林华 3.4 队列的类型定义 队列(Queue)也是一种操作受限的线性表。它只允 队列(Queue) 许在表的一端进行插入，而在另一端进行删除。允许 删除的一端称为队头(front)，允许插入的一端称为队 队头(front) 队 尾 (rear)。在队尾插入的操作称为入队,在队头删除的 尾 (rear) 操作称为出队。 当队列中没有元素时称为空队列。在空队列中依 空队列 次加入元素a ,a ,…a 之后，a 是队头元素，a 是队尾 1 2 n 1 队头元素 n 队尾 元素。显然退出队列的次序也只能是a ,a ,…a ，也 元素 1 2 n 就是说队列的修改是依先进先出的原则进行的。因此 队列亦称作先进先出(First In First Out)的线性 表，简称FIFO表。 《数据结构》主讲:林华 队列的抽象数据类型定义 ADT Queue { 数据对象： D ＝{a | a ∈ElemSet, i=1,2,...,n, n ≥0} i i 数据关系： R1 ＝{ a ,a | a , a ∈D, i=2,...,n} i-1 i i-1 i 约定其中a1 端为队列头，an 端为队列尾 基本操作： } ADT Queue 《数据结构》主讲:林华 队列的基本操作： InitQueue(Q) DestroyQueue(Q) QueueEmpty(Q) QueueLength(Q) GetHead(Q, e) ClearQueue(Q) EnQueue(Q, e) DeQueue(Q, e) QueueTraverse(Q, visit()) 《数据结构》主讲:林华 InitQueue(Q) 操作结果：构造一个空队列Q。 DestroyQueue(Q) 初始条件：队列Q 已存在。 操作结果：队列Q被销毁， 不再存在。 《数据结构》主讲:林华 QueueEmpty(Q) 初始条件：队列Q 已存在。 操作结果：若Q为空队列，则 返回TRUE ，否则返回 FALSE 。 《数据结构》主讲:林华 QueueLength(Q) 初始条件：队列Q 已存在。 操作结果：返回Q的元素个 数，即队列的长度。 《数据结构》主讲:林华 GetHead(Q, e) 初始条件：Q为非空队列。 操作结果：用e返回Q的队头 元素。 a a … … a