《数据结构与算法分析》课件第3章

第3章栈和队列3.1栈3.2队列

3.1栈

栈(Stack)是限定仅在表尾进行插入和删除运算的线性表。我们把表尾称为栈顶(Top)；表头称为栈底(Bottom)。当栈中没有数据元素时称为空栈。图3-1栈的示意图3.1.1栈的顺序存储表示——顺序栈

1.栈的顺序存储结构

栈是一种特殊的线性表，因此可以用线性表的方法来存储栈。最简单的方法是用一维数组来存储。由于栈底是固定不变的，而栈顶是随进栈出栈操作动态变化的，因此为了实现对栈的操作，必须记住栈顶的当前位置。另外，对于栈来说，是有容量限制的。鉴于以上考虑，把栈的顺序存储结构定义为图3-2栈的状态变化

(1)置空栈。对栈进行初始化，即将栈顶指针Top初始化为-1。

(2)判断栈是否为空。在进行出栈操作时，必须先判断栈不为空；否则会出错。

(3)进栈。将数据元素e插入栈顶。

(4)出栈。首先判断栈是否为空，若为空则表示下溢；否则删除栈顶数据元素。

(5)取栈顶元素。只把栈顶元素的值取出，而不调整栈顶指针Top的值。

2.多个栈共享存储空间

上面讨论了单个栈在顺序存储结构下的实现和运算，它能有效地控制先进后出顺序的数据处理。但是，当一个程序中同时使用多个顺序栈时，应如何处理呢？

为了防止上溢错误，需要为每个栈分配一个较大的空间，但在某一个栈发生上溢的同时，可能其余栈未用的空间还很多，如果将这多个栈安排在同一个向量中，即让多个栈共享存储空间，既节约了存储空间，又降低了上溢发生的概率。图3-3两个栈共享存储空间图3-4多个栈共享存储空间3.1.2栈的链式存储表示——链栈

对于顺序栈来说，其最大缺点是：当栈的容量不固定时，必须设置栈，使其可容纳最多的数据元素，这样就会浪费很多存储容间，也可能产生上溢现象。采用链式存储结构就不会产生类似的问题。

栈的链式存储结构称为链栈。它是运算受限的单链表，其插入和删除操作仅在表头进行。图3-5是链栈的示意图。图3-5链栈的示意图栈顶是top指针，它唯一地确定一个链栈。当top等于NULL时，该链栈为空栈。链栈的定义如下：3.1.3栈的应用

栈的应用非常广泛，只要问题满足LIFO原则，均可使用栈做数据结构。栈的典型应用有：

(1)过程递归调用。

(2)“回溯”问题的求解。

(3)表达式求值。

下面通过举例来说明。

1．递归调用

递归调用是指一个过程(函数)通过调用语句直接或间接调用自身的过程。递归是程序设计中一个强有力的工具，有很多数学函数就是递归定义的，如大家熟悉的阶乘函数；在有的数据结构中，如二叉树、广义表等。由于结构本身固有的递归特性，使其操作也可用递归函数来描述。下面以计算Fibonacci序列为例来说明栈在递归调用中的作用。

Fibonacci序列定义为图3-6递归执行过程图3-7递归调用过程中栈的变化

2．地图染色问题

1)问题描述及分析

地图染色问题，可以根据四色定理来解决。四色定理是指可以用不多于四种颜色对地图着色，使相邻的行政区域不重色。下面应用这个定理的结论，用回溯算法对一幅给定的地图染色。

2)数据结构

在计算机上实现上述算法时，用一个关系矩阵R[n][n]来描述各行政区域间的相邻关系，如下所示：

除关系矩阵R之外，还需要设置一个栈S，用来记录行政区域的所染颜色的序号：

S[i] = k根据以上说明，类型说明如下：

intR[n][n];

intS[n];

图3-8所示行政区域的关系矩阵R如图3-9所示。图3-8行政区域地图及染色结果

图3-9关系矩阵R[7][7]

3)算法设计

上述算法的C语言实现如下：图3-10运行过程中栈S的变化过程

3．表达式求值

1)问题描述及分析

任何一个表达式都是由操作数(operand)、操作符(operator)和界限符(delimiter)组成的。在实际应用中，操作数可以是任何合法的变量名和常数；操作符可以分为算术运算符、关系运算符和逻辑运算符等；界限符有左右括号和表达式结束符等。在这里仅讨论简单算术表达式的求值问题。这种表达式只含加、减、乘、除四种运算符，其运算规则与四则运算相同。

2)数据结构

为了实现算符优先法，我们设置两个栈，一个称做OPTR，用来存放运算符；另一个称做OPND，用以存放操作数或运算结果。这两个栈既可均采用顺序存储，也可采用链式存储。

3)算法设计

算法的基本思想：

(1)置操作数栈OPND为空栈，表达式起始符#为运算符栈OPTR的栈底元素。

(2)依次读入表达式中的每个字符，若是操作数则进OPND栈；若是运算符，则在和栈OPTR的栈顶元素比较优先权后做相应的操作，直至整个表达式求值完毕为止。

3.2队列

队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(Front)；允许插入的另一端称为队尾(Rear)。

队列同现实生活中排队相仿，新来的成员总是加入队尾(即不允许“加塞”)，每次离开的成员总是队列头上的(不允许中途离队)，即当前“最老的”成员离队。换言之，先进入队列的成员总是先离开队列。因此队列亦称做先进先出(FirstInFirstOut)的线性表，简称为FIFO表。图3-11队列示意图队列抽象数据类型的定义如下：3.2.1队列的存储结构

1．顺序队列

顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也必须用一个数组来存放当前队列中的元素。由于队列的队头和队尾的位置均是变化的，因而需要设置两个指针，分别指示当前队头元素和队尾元素在数组中的位置。对顺序队列的类型sequeue和一个实际的顺序队列指针sq的说明如下：为方便起见，我们规定头指针front总是指向当前队头元素的前一个位置，尾指针rear指向当前队尾元素的位置。一开始，队列的头、尾指针指向向量空间下界的前一个位置，在此设置为-1。若不考虑溢出，则入队运算可描述为

sq->rear++; //尾指针加1

sq->data[sq->rear]=x; //x入队

出队运算可描述为

sq->front++;

//头指针加1

*temp=sq->data[sq->front]; //读出队头元素图3-12顺序队列运算时的头、尾指针变化情况显然，当前队列中的元素个数(即队列的长度)是(sq->rear)-(sq->front)。若sq->front=sq->rear，则队列长度为0，即当前队列是空队列，图3-12(a)和(c)均表示空队列。空队列时再做出队操作便会产生“下溢”。队满的条件是当前队列长度等于向量空间的大小，即

(sq->rear)-(sq->front)==MAXSIZE克服假上溢通常采用的方法是：设想向量sq->data

[MAXSIZE]是一个首尾相接的圆环，即sq->data[0]接在sq->data[MAXSIZE-1]之后，我们将这种意义下的队列称为循环队列，如图3-13所示。图3-13循环队列示意图若当前尾指针等于数组的上界，则再做入队操作时，令尾指针等于数组的下界，这样就能利用到已被删除的元素空间，克服了假上溢。因此入队操作时，在循环意义下的尾指针加1操作可描述为

 if(sq->rear+1>=MAXSIZE)sq->rear=0;

elsesq->rear++;

如果利用“模”运算，上述循环意义下的尾指针加1操作可以更简洁地描述为

sq->rear=(sq->rear+1)%MAXSIZE同样，出队操作时，在循环意义下的头指针加1操作，也可利用“模”运算来实现，即

sq->front=(sq->frout+1)%MAXSIZE

因为出队和入队分别要将头指针和尾指针在循环意义下加1，所以某个元素出队后，若头指针已从后面追上尾指针，即

sq->front==sq->rear则当前队列为空；若某个元素入队后，尾指针已从后面追上头指针，即

sq->rear==sq->front

则当前队列为满。因此，仅凭关系式sq->front==sq->rear是无法区别循环队列是空还是满的。对此，有两种解决的办法：一种是引入一个标志变量以区别是空队列还是满队；另一种更为简单的办法是入队前测试尾指针在循环意义下加1后是否等于头指针，若相等则认为是队满，即判别队满的条件是：

(sq->rear+1)%MAXSIZE==sq->front

从而保证了sq->rear==sq->front是队空的判别条件。在循环队列上实现的五种基本运算如下：

(1)置空队列。

(2)判队空。

(3)取队头元素。

(4)入队。

(5)出队。

2．链队列

队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾插入操作，为此再增加一个尾指针，指向链表上的最后一个结点。于是，一个链队列由一个头指针和一个尾指针唯一地确定。和顺序队列类似，我们也是将这两个指针封装在一起，将链队列的类型linkqueue定义为一个结构体类型，如下所示：

typedefstruct{

linklist*front,*rear;

}linkqueue;

linkqueue

q;图3-14链队列示意图在链队列上实现的五种基本运算如下：

(1)置空队。

(2)判队空。

(3)取队头结点数据。

(4)入队。

(5)出队。3.2.2队列的应用

1．划分子集问题

1)问题描述与分析

已知集合A = {a1，a2，…，an}，并已知集合上的关系R = {(ai，aj)|ai，aj属于A，i不等于j}，其中(ai，aj)表示ai与aj之间的冲突关系。现要求将集合A划分成互不相交的子集A1，A2…Am(m≤n)，使任何子集上的元素均无冲突关系，同时要求划分的子集个数较少。

2)数据结构

采用循环筛选法。从集合A中的第一个元素开始，凡与第一个元素无冲突且与该组中的其他元素也无冲突的元素划归一组，作为一个子集A1；再将A中剩余元素按同样的方法找出互不冲突的元素划归第二组，即子集A2；依次类推，直到A中所有元素都划归不同的组(子集)为止。

在计算机实现时，首先要将集合中元素的冲突关系设置一个冲突关系矩阵，用一个二维数组R[n][n]表示，若第i个元素与第j个元素有冲突则R[i][j] = 1；否则R[i][j] = 0。对应上述问题的关系矩阵R见图3-15。图3-15关系矩阵R[q][q]另外，还要设置以下数据结构：循环队列cq[n]，用来存放集合A的元素；数组result[n]用来存放每个元素的分组号；newr[n]为工作数组。其类型定义如下：

intR[n][n];

intcq[n],result[n],newr[n];

3)算法思想

初始状态：集合A中的元素放入cq中，result和newr置0，设组号group = 1。如图8-16(a)所示。图3-16划分子集的筛选过程

4)算法实现

2．离散事件仿真

1)问题描述及分析

假设服务系统有四个窗口对外接待客户，在营业时间内不断有客户进入并要求服务。由于每个窗口只能接待一个客户，因此进入该服务系统的客户须在某一个窗口前排队。如果窗口的服务员忙则进入的客户排队等待；闲则可立即服务。服务结束则从队列中撤离，并计算一天内进入服务系统的客户的平均逗留时间。影响系统队列变化的原因有两种：

(1)新客户进入服务系统，该客户加入到队列最短的窗口队列中。

(2)四个队列中有客户服务完毕而撤离。

2)算法思想

假设事件表中最早发生的是新客户到达，则随之应得到两个时间：一是本客户处理业务所需时间；二是下一个客户到达服务系统的时间间隔。此时模拟程序应做的工作如下：

(1)比较四个队列中的客户数，