数据结构第八的讲.ppt

3.4 队列 1. 定义 2. 链队列----队列的链式存储结构 3. 循环队列----队列的顺序存储结构 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 1．队列的实例 例1：到医院看病，首先需要到挂号处挂号，然后，按号 码顺序救诊。 例2：乘坐公共汽车，应该在车站排队，车来后，按顺序 上车。 一 、队列的定义 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 2．队列的定义 前面所讲的栈是一种后进先出的数据结构，而在实际问题中还经常使用一种“先进先出” (FIFO---First In First Out)的数据结构：即插入在表一端进行，而删除在表的另一端进行，我们将这种数据结构称为队或队列，把允许插入的一端叫队尾(rear) ，把允许删除的一端叫队头(front)。下图所示是一个有5 个元素的队列。入队的顺序依次为a1、 a2 、a3 、a4 、 a5 ，出队时的顺序将依然是a1、 a2 、a3 、a4 、 a5 。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. a1 a2 a3 …… an 入队列 队头 队尾 出队列 队 列 的 示 意 图 队列的特点 先进先出 说明： 第一个入队的元素在队头，最后一个入队的元素在队尾， 第一个出队的元素为队头元素， 最后一个出队的元素为队尾元素 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 2. 链队列——队列的链式存储结构 实质是带头结点的线性链表； 两个指针： 队头指针Q.front指向头结点 队尾指针Q.rear指向尾结点 初始态：队空条件 头指针和尾指针均指向头结点 Q.front = Q.rear Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 1）链队列的类型定义 p61 typedef struct QNode { //元素结点 QElemType data; struct QNode *next; }QNode, *QueuePtr; typedef struct{ //特殊结点 QueuePtr front; //队头指针 QueuePtr rear; //队尾指针 }LinkQueue; LinkQueue Q; Q.front——指向头结点 Q.rear ——指向链尾结点 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 2）链队列示意图 p61图3.10 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 队列运算指针变化状况 空队列 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 3）基本操作与实现 初始化 p62 Status InitQueue (LinkQueue Q) 销毁队列 p62 Status DestroyQueue (LinkQueue Q) 入队 p62 Status EnQueue(LinkQueue Q,