文档介绍：第3章栈和队列§1栈§2队列本章小结堆栈和队列是数据结构的另外两种基本类型。从逻辑结构上看,堆栈和队列也是线性表,但它们是两种特殊的线性表。其特殊性在于,它们是运算受限的线性表,这里所说的运算是指对于数据的存取过程。堆栈的存取只能在堆栈顶端进行;队列则通常限定从一端输入,从另一端端输出。因此,堆栈和队列也被称为限定性的数据结构。堆栈的运算规则是:后进先出(LastInFirstOut)。队列的运算规则是:先进先出(FirstInFirstOut)。§§§§§(queue)是一种先进先出的线性表(FirstInFirstOut,缩写为FIFO)。这种限定性的数据结构,只允许在一端进行输入,而在另一端输出。在队列中,允许输入的一端叫做队尾(也叫后端,rear),允许输出的一端叫做队头(也叫前端,front)。向队列中插入新元素称为入队,从队列中删除元素称为出队。队列的逻辑示意图如下页所示:§=(a1,a2,a3……an),a1就是队头元素,an是队尾元素。队列中的元素是按照a1,a2……an的顺序入队的,出队时也必须依照这个顺序依次退出。也就是说,an-1出队后才轮到an出队。队头队尾frontrear出队列入队列a1a2a3……an1、图形的广度优先搜索2、优先队列:依据元素的某种特性和优先权存取元素。如模拟生活中的离散事件(排队问题)3、操作系统中的工作调度。优先权相同者,先到先出。如CPU调度。同时有几项作业运行时,均须通过通道(可以是多端控制)输出,按照请求的先后次序排队,逐个输出。如打印缓冲管理“spooling”,先将输出数据写在磁盘上(缓冲区),由打印机按照先存入者先打印的顺序输出数据。§,可以设置两个向量front、rear,做为指向队列前端(队首)和末端(队尾)的两个指针。初始值均为-1时,表示队列为空。如下图:队列的入队和出队操作示意图顺序队列类型定义假设队列的元素个数最大不超过整数MaxSize,所有的元素都具有同一数据类型ElemType,则顺序队列类型SqQueue定义如下:typedefstruct{ ElemTypedata[MaxSize]; intfront,rear;/*队首和队尾指针*/}SqQueue顺序队列的空间管理问题从上图可以看出,这种两端向量的线性空间配置并不能有效地利用空间。如,图(a)为队列的初始状态,有front==rear成立,该条件可以作为队列空的条件;但是rear==MaxSize-1却不能作为队满的条件。如图(d)中,队列为空,但仍满足rear==MaxSize-1。此时再入队则出现“上溢出”,但这种溢出并不是真正的溢出,队列中仍有可存放元素的空位置,所以这是一种假溢出。在实际应用过程中,通常使用环状队列解决空间利用的问题。其实就是改变队列首尾指针的控制方式,使线性空间从逻辑上形成一个闭合的环,物理上仍是线性静态的存储空间分配。环状队列的逻辑示意图如下:frontreara1a3a2a5a4…………环状队列逻辑示意图Maxsize-1frontrear210anan-1b1……环状队列的存储逻辑示意图