chapt栈和队列队列.ppt

堆栈和队列是数据结构的另外两种基本类型。从逻辑结构上看，堆栈和队列也是线性表，但它们是两种特殊的线性表。其特殊性在于，它们是运算受限的线性表，这里所说的运算是指对于数据的存取过程。 堆栈的存取只能在堆栈顶端进行；队列则通常限定从一端输入，从另一端端输出。因此，堆栈和队列也被称为限定性的数据结构。 堆栈的运算规则是：后进先出（Last In First Out）。 队列的运算规则是：先进先出（First In First Out）。 假设队列为q=(a1,a2,a3……an)，a1就是队头元素，an是队尾元素。队列中的元素是按照 a1,a2……an的顺序入队的，出队时也必须依照这个顺序依次退出。也就是说，an-1出队后才轮到an出队。 1、图形的广度优先搜索 2、优先队列：依据元素的某种特性和优先权存取元素。如模拟生活中的离散事件（排队问题） 3、操作系统中的工作调度。优先权相同者，先到先出。 如CPU调度。同时有几项作业运行时，均须通过通道（可以是多端控制）输出，按照请求的先后次序排队，逐个输出。 如打印缓冲管理“spooling”，先将输出数据写在磁盘上（缓冲区），由打印机按照先存入者先打印的顺序输出数据。 §1.2 队列的顺序存储结构及其基本运算实现 与顺序栈的处理方式相似，可以设置两个向量front、rear，做为指向队列前端（队首）和末端（队尾）的两个指针。初始值均为－1时，表示队列为空。如下图： 环状队列的逻辑示意图如下： 插入数据时，队尾指针rear会沿着逆时针方向前进，数据存入rear指向的位置。直到rear向前移到等于front时，表示队列已满，无法输入数据。 输出数据时，队首指针front也沿着逆时针方向前进。 从逻辑图式可以看出，这种处理方式的特殊点是front指向一个空位置，该位置不存储数据，所以环状队列的可使用空间不再是Maxsize，而是“Maxsize－1”。 输出元素就是front的下一个元素（如上图所示a1）。 同样的，当front前移至等于rear时，表示队列已空，无法输出数据。 上述逻辑环实际上还是如右上图所示的展开形式，是线性存储结构。当rear指针到达Maxsize－1时，欲再存入元素，rear又再次回到原队列首端，相当于index=0的元素位置（如存入b1），以达到环状输入目的。front指针也要如此循环。 §1.3 队列的链式存储结构及其基本运算实现 当数据元素的变动较大，或者无法预计顺序存储所需空间时，队列的链式存储结构也比顺序存储结构更加有利。 使用链表描述的队列称为链队列。 一个链队列显然也需要两个分别指向队头和队尾的指针front、rear。其逻辑结构示意图如下： * * 第3章 栈和队列 §1 栈 §2 队列 本章小结 § 1.1 队列的概述 § 1.2 队列的顺序存储结构及其基本运算实现 § 1.3 队列的链式存储结构及其基本运算实现 § 1.4 队列的应用 § 2 队列 1.1.1 队列的定义 队列（queue）是一种先进先出的线性表（First In First Out，缩写为FIFO）。这种限定性的数据结构，只允许在一端进行输入，而在另一端输出。 在队列中，允许输入的一端叫做队尾（也叫后端，rear），允许输出的一端叫做队头（也叫前端，front）。 向队列中插入新元素称为入队, 从队列中删除元素称为出队。 队列的逻辑示意图如下页所示： §1.1 队列的概述 队头 队尾 front rear 出队列 入队列 a1 a2 a3……an 1.1.2 队列的应用范围 队列的入队和出队操作示意图 顺序队列类型定义 假设队列的元素个数最大不超过整数MaxSize，所有的元素都具有同一数据类型ElemType，则顺序队列类型SqQueue定义如下: typedef struct { ElemType data[MaxSize]； int front,rear； /*队首和队尾指针*/ } SqQueue 顺序队列的空间管理问题 从上图可以看出，这种两端向量的线性空间配置并不能有效地利用空间。 如，图(a)为队列的初始状态,有front==rear成立,该条件可以作为队列空的条件；但是rear==MaxSiz