数据结构第三章栈和队列

第三章栈和队列【学习目标】1.掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。2.熟练掌握栈类型的两种实现方法。3.熟练掌握循环队列和链队列的基本操作实现算法。4.理解递归算法执行过程中栈的状态变化过程。【重点和难点】栈和队列是在程序设计中被广泛使用的两种线性数据结构，因此本章的学习重点在于掌握这两种结构的特点，以便能在应用问题中正确使用。【知识点】顺序栈、链栈、循环队列、链队列【学习指南】在这一章中，主要是学习如何在求解应用问题中适当地应用栈和队列，栈和队列在两种存储结构中的实现都不难，但应该对它们了如指掌，特别要注意它们的基本操作实现时的一些特殊情况，如栈满和栈空、队满和队空的条件以及它们的描述方法。本章要求必须完成的算法设计题为：3.15，3.17，3.19，3.22，3.28，3.30，3.31，3.32。其中前4个主要是练习栈的应用，后4个主要是有关队列的实现方法的练习。【课前思考】1.什么是线性结构？简单地说，线性结构是一个数据元素的序列。2.你见过餐馆中一叠一叠的盘子吗？如果它们是按1,2,…,n的次序往上叠的，那么使用时候的次序应是什么样的？必然是依从上往下的次序，即n,…,2,1。它们遵循的是后进先出的规律，这正是本章要讨论的栈的结构特点。3.在日常生活中，为了维持正常的社会秩序而出现的常见现象是什么？是排队。在计算机程序中，模拟排队的数据结构是队列。[引言]栈和队列是两种操作受限的线性表，是两种常用的数据类型通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)1≤i≤n即线性表允许在表内任一位置进行插入和删除；而栈只允许在表尾一端进行插入和删除；队列只允许在表尾一端进行插入，在表头一端进行删除。3.1栈3.1.1栈的类型定义栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。在表中，允许插入和删除的一端称作栈顶(top)，不允许插入和删除的另一端称作栈底(bottom)。其类型定义如下：ADTStack{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否则返回FALSE。StackLength(S)初始条件：栈S已存在。操作结果：返回栈S中元素个数，即栈的长度。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。StackTraverse(S,visit())初始条件：栈S已存在且非空，visit()为元素的访问函数。操作结果：从栈底到栈顶依次对S的每个元素调用函数visit()，一旦visit()失败，则操作失败。}ADTStack3.1.2栈的存储表示和操作的实现和线性表类似，栈也有两种存储表示，其顺序存储结构简称为顺序栈。一、顺序栈类型的定义//结构定义：typedefstruct{ElemType*base;//存储空间基址inttop;//栈顶指针intstacksize;//允许的最大存储空间以元素为单位}Stack;和顺序表类似，对顺序栈也需要事先为它分配一个可以容纳最多元素的存储空间，base为这个存储空间的基地址，也即一维数组的地址。从名称来讲，栈顶指针意为指示栈顶元素在栈中的位置，但它的值实际是栈中元素的个数，和顺序表中的length值的意义相同。为了应用方便，这个最大空间的容量应由使用这个顺序栈的程序员决定，它的默认值和顺序表的默认值相同。用图表示顺序栈如下：图中的顺序栈的最大容量为7，当前栈中元素个数为4，因此，我们也可认为栈顶指针总是指在栈顶元素的后面一个位置上。//基本操作接口(函数声明)：voidInitStack(Stack&S，intmaxsize);//构造一个最大存储容量为maxsize的空栈S。voidDestroyStack(Stack&S);//销毁栈S，S不再存在。voidClearStack(Stack&S);//将S置为空栈。boolStackEmpty(StackS);//若栈S为空栈，则返回TRUE，否则返回FALSE。intStackLength(StackS);//返回S的元素个数，即栈的长度。boolGetTop(StackS,ElemType&e);//若栈不空，则用e返回S的栈顶元素，并返回TRUE；否则返回FALSE。boolPush(Stack&S,ElemTypee);//若栈的存储空间不满，则插入元素e为新的栈顶元素，并返回TRUE；//否则返回FALSE。boolPop(Stack&S,ElemType&e);//若栈不空，则删除S的栈顶元素，用e返回其值，并返回TRUE；否则返回FALSE。voidStackTraverse(StackS,void(*visit(ElemType))//依次对S的每个元素调用函数visit()，一旦visit()失败，则操作失败。在此只给出其中4个函数的定义。对顺序栈来说，空栈的初始化和顺序表的初始化完全相同。这不奇怪，因为它们的结构是一样的。也就是说，并非对栈而言取不到除栈顶之外的元素，而是对栈类型来说，不允许这种操作。voidInitStack(Stack&S，intmaxsize){//构造一个最大存储容量为maxsize的空栈Sif(maxsize==0)maxsize=MAXLISTSIZE;S.base=newSElemType[maxsize];if(!S.base)exit(1);//存储分配失败S.stacksize=maxsize;S.top=0;//空栈中元素个数为0}在此定义中，栈顶指针的值恰为当前栈中元素个数，栈顶指针的初值为0和栈中元素个数为0是同一个含义。boolGetTop(StackS,ElemType&e){//若栈不空，则用e返回S的栈顶元素，并返回TRUE；否则返回FALSEif(S.top==0)returnFALSE;e=*(S.base+S.top-1);//返回非空栈中栈顶元素returnTRUE;}*(S.base+S.top-1)是S.base[S.top-1]的另一种写法，其实质相同。boolPush(Stack&S,ElemTypee){//若栈的存储空间不满，则插入元素e为新的栈顶元素，//并返回TRUE；否则返回FALSEif(S.top==S.stacksize)//栈已满，无法进行插入returnFALSE;*(S.base+S.top)=e;//插入新的元素++S.top;//栈顶指针后移returnTRUE;}boolPop(Stack&S,ElemType&e){//若栈不空，则删除S的栈顶元素，用e返回其值，//并返回TRUE；否则返回FALSEif(S.top==0)returnFALSE;e=*(S.base+S.top-1);//返回非空栈中栈顶元素--S.top;//栈顶指针前移returnTRUE;}显然，顺序栈的基本操作的时间复杂度，除遍历之外，均为常量级的，即O(1)。3.2栈的应用举例3.2.1数制转换十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：N=(Ndivd)×d+Nmodd(其中：div为整除运算，mod为求余运算)例如：(1348)10=(2504)8，其运算过程如动画演示所示：假设现要编制一个满足下列要求的程序：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。问题很明确，就是要输出计算过程中所得到的各个八进制数位。然而从动画演示的计算过程可见，这八进制的各个数位产生的顺序是从低位到高位的，而打印输出的顺序，一般来说应从高位到低位，这恰好和计算过程相反。因此，需要先保存在计算过程中得到的八进制数的各位，然后逆序输出，因为它是按后进先出的规律进行的，所以用栈最合适。算法3.1voidconversion(){//对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数InitStack(S);//构造空栈cinN;//输入一个十进制数while(N){Push(S,N%8);//余数入栈N=N/8;//非零商继续运算}//whilewhile(!StackEmpty){//和求余所得相逆的顺序输出八进制的各位数Pop(S,e);coute;}//while}//conversion你们可能会说，用数组直接实现不也很简单吗？你可以试一下利用数组重新写这个算法，那么你一定能体会到在这个算法中用栈的好处了。因栈的引入简化了程序设计的问题，突出了解决问题的根本所在。而用数组不仅掩盖了问题的本质，还要分散精力去考虑数组下标增减等细节问题。在以后几个例子中你将会看到，实际利用栈的问题中，入栈和出栈操作大都不是直线式的，而是交错进行的。3.2.2括弧匹配检验假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，如（［］（））或［（［］［］）］等为正确的匹配，［（]）或（［］（）或(())）均为错误的匹配。现在的问题是，要求检验一个给定表达式中的括弧是否正确匹配？检验括号是否匹配的方法可用期待的急迫程度这个概念来描述。即后出现的左括弧，它等待与其匹配的右括弧出现的急迫心情要比先出现的左括弧高。换句话说，对左括弧来说，后出现的比先出现的优先等待检验，对右括弧来说，每个出现的右括弧要去找在它之前最后出现的那个左括弧去匹配。显然，必须将先后出现的左括弧依次保存，为了反映这个优先程度，保存左括弧的结构用栈最合适。这样对出现的右括弧来说，只要栈顶元素相匹配即可。如果在栈顶的那个左括弧正好和它匹配，就可将它从栈顶删除。例如考虑下列括号序列：[([][])]12345678当计算机接受了第一个括号后，它期待着与其匹配的第八个括号的出现，然而等来的却是第二个括号，此时第一个括号[只能暂时靠边，而迫切等待与第二个括号相匹配的、第七个括号]的出现，类似地，因等来的是第三个括号[，其期待匹配的程度较第二个括号更急迫，则第二个括号也只能靠边，让位于第三个括号，在接受了第四个括号之后，第三个括号的期待得到满足，消解之后，第二个括号的期待匹配就成为当前最急迫的任务了，…，依次类推。那么，什么样的情况是不匹配的情况呢？上面列举的三种错误匹配从期待匹配的角度描述即为：1．来的右括弧非是所期待的；2．来的是不速之客；3．直到结束，也没有到来所期待的。这三种情况对应到栈的操作即为：1．和栈顶的左括弧不相匹配；2．栈中并没有左括弧等在哪里；3．栈中还有左括弧没有等到和它相匹配的右括弧。在以上分析的基础上就可以写出检验括弧匹配的算法了。但在写算法时要注意：1．匹配不是相等。因此你若在遇到左括弧时是将当前这个左括弧进栈的话，那么在遇到右括弧时必须分别不同情况进行判别。2．和栈顶元素进行比较的前提是栈不为空。因此你在判别当前出现的右括弧是否和相应左括弧匹配之前要先判别当前栈是否为空。3．没有等到即为栈不空的情况。因此在算法结束之前，要判别栈是否已为空了。4．此外别忘了使用栈之前一定要进行初始化。3.2.3迷宫求解问题你做过迷宫的游戏吗？你从入口进去之后是如何找到出口的？如果你是在一点也不了解迷宫结构的情