第3章栈和队列 本章思政 从组成元素的逻辑关系看,栈和队列都属于线性结构。栈和队列与线性表的不同之处在于它们的相关运算具有一些特殊性。更准确地说,一般线性表上的插入、删除运算不受限制,而栈和队列上的插入、删除运算均受某种特殊限制,因此栈和队列也称为操作受限的线性表。 本章介绍栈和队列的基本概念、存储结构、基本运算算法设计和应用实例。 3.1 栈 栈是一种常用而且重要的数据结构之一,如用于保存函数调用时相关参数信息等,通常在将递归算法转换成非递归算法时需要使用到栈。本节主要讨论栈及其应用。 3.1.1栈的定义 栈(stack)是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶(top),表的另一端称为栈底(bottom),如图3.1所示。 图3.1栈示意图 栈顶的当前位置是动态的,栈顶的当前位置由一个被称为栈顶指针的位置指示器来标识。当栈中没有数据元素时称为空栈。栈的插入操作通常称为进栈或入栈(push),栈的删除操作通常称为出栈或退栈(pop)。 栈的主要特点是“后进先出”(last in first out,LIFO),即后进栈的元素先出栈。每次进栈的数据元素都放在原来栈顶元素之前成为新的栈顶元素,每次出栈的数据元素都是当前栈顶元素。栈也称为后进先出表。 例如,若干个人走进一个死胡同,假设该死胡同的宽度恰好只够一个人进出,那么走出死胡同的顺序和走进的顺序正好相反。这个死胡同就是一个栈。 栈抽象数据类型的定义如下: ADT Stack {数据对象: D={ ai | 1≤i≤n,n≥0,ai为ElemType类型}//ElemType是自定义类型标识符 数据关系: R={ai,ai+1 | ai,ai+1∈ D,i=1,…,n-1} 基本运算: InitStack(&s): 初始化栈,构造一个空栈s。 DestroyStack(&s): 销毁栈,释放为栈s分配的存储空间。 StackEmpty(s): 判断栈是否为空,若栈s为空,则返回真; 否则返回假。 Push(&s,e): 进栈,将元素e插入栈s中作为栈顶元素。 Pop(&s,&e): 出栈,从栈s中删除栈顶元素,并将其值赋给e。 GetTop(s,&e): 取栈顶元素,返回当前的栈顶元素,并将其值赋给e。 } 【例3.1】若元素的进栈序列为1234,能否得到3142的出栈序列? 解为了让3作为第一个出栈元素,1、2先进栈,此时要么2出栈,要么4进栈后出栈,出栈的第2个元素不可能是1,所以得不到3142的出栈序列。 【例3.2】用S表示进栈操作、X表示出栈操作,若元素的进栈顺序为1234,为了得到1342的出栈序列,给出相应的S和X操作串。 解为了得到1342的出栈序列,其操作过程是1进栈,1出栈,2进栈,3进栈,3出栈,4进栈,4出栈,2出栈。因此相应的S和X操作串为SXSSXSXX。 说明: n个不同的元素通过一个栈产生的出栈序列的个数为1n+1Cn2n。例如n=4时,出栈序列的个数等于14。 图3.2栈操作的一个时刻 【例3.3】一个栈的进栈序列为1,2,…,n,通过一个栈得到出栈序列p1,p2,…,pn(p1,p2,…,pn是1,2,…,n的一种排列)。若p1=3,则p2可能取值的个数是多少? 解为了让3作为第一个出栈元素,将1、2、3依次进栈,3出栈,此时如图3.2所示。之后可以让2出栈,p2=2,也可以让4进栈再出栈,p2=4,也可以让4、5进栈再出栈,p2=5,…,所以p2可以是2,4,5,…,n,不可能是1和3,即p2可能取值的个数是n-2。 3.1.2栈的顺序存储结构及其基本运算的实现 栈中数据元素的逻辑关系呈线性关系,所以栈可以像线性表一样采用顺序存储结构进行存储,即分配一块连续的存储空间来存放栈中的元素,并用一个变量(例如top)指向当前的栈顶元素以反映栈中元素的变化。采用顺序存储结构的栈称为顺序栈(sequential stack)。 假设栈的元素个数最大不超过正整数MaxSize,所有的元素都具有同一数据类型,即ElemType,可用下列方式来声明顺序栈的类型SqStack: typedef struct {ElemType data[MaxSize];//存放栈中的数据元素 int top; //栈顶指针,即存放栈顶元素在data数组中的下标 } SqStack; //顺序栈类型 栈到顺序栈的映射过程如图3.3所示。本节采用栈指针s(不同于栈顶指针top)的方式创建和使用顺序栈,如图3.4所示。 图3.3栈到顺序栈的映射 图3.4顺序栈指针s 图3.5是一个顺序栈操作示意图。图3.5(a)是初始情况,它是一个空栈; 图3.5(b)表示元素a进栈以后的状态; 图3.5(c)表示元素b、c、d进栈以后的状态; 图3.5(d)表示元素d出栈以后的状态。 综上所述,对于s所指的顺序栈(即顺序栈s),初始时设置s->top=-1,可以归纳出对后面的算法设计来说非常重要的4个要素。 图3.5栈操作示意图 栈空的条件: s-top==-1。 栈满的条件: s-top==MaxSize-1(data数组的最大下标)。 元素e进栈的操作: 先将栈顶指针top增1,然后将元素e放在栈顶指针处。 出栈的操作: 先将栈顶指针top处的元素取出放在e中,然后将栈顶指针减1。 在顺序栈上对应栈的基本运算算法设计如下。 1) 初始化栈: InitStack(&s) 该运算创建一个空栈,由s指向它。实际上就是分配一个顺序栈空间,并将栈顶指针设置为-1。算法如下: void InitStack(SqStack *&s) {s=(SqStack *)malloc(sizeof(SqStack));//分配一个顺序栈空间,首地址存放在s中 stop=-1; //栈顶指针置为-1 } 2) 销毁栈: DestroyStack(&s) 该运算释放顺序栈s占用的存储空间。算法如下: void DestroyStack(SqStack *&s) { free(s); } 3) 判断栈是否为空: StackEmpty(s) 该运算实际上用于判断条件s->top==-1是否成立。算法如下: bool StackEmpty(SqStack *s) { return(stop==-1); } 4) 进栈: Push(&s,e) 该运算的执行过程是,在栈不满的条件下先将栈顶指针增1,然后在该位置上插入元素e,并返回真; 否则返回假。算法如下: bool Push(SqStack *&s,ElemType e) {if (stop==MaxSize-1)//栈满的情况,即栈上溢出 return false; stop++; //栈顶指针增1 sdata[stop]=e; //元素e放在栈顶指针处 return true; } 5) 出栈: Pop(&s,&e) 该运算的执行过程是,在栈不为空的条件下先将栈顶元素赋给e,然后将栈顶指针减1,并返回真; 否则返回假。算法如下: bool Pop(SqStack *&s,ElemType &e) {if (stop==-1)//栈为空的情况,即栈下溢出 return false; e=sdata[stop]; //取栈顶元素 stop--; //栈顶指针减1 return true; } 6) 取栈顶元素: GetTop(s,&e) 该运算在栈不为空的条件下将栈顶元素赋给e并返回真; 否则返回假。算法如下: bool GetTop(SqStack *s,ElemType &e) {if (stop==-1)//栈为空的情况,即栈下溢出 return false; e=sdata[stop]; //取栈顶元素 return true; } 和出栈运算相比,本算法只是没有移动栈顶指针。上述6个基本运算算法的时间复杂度均为O(1),说明这是一种非常高效的设计。 【例3.4】设计一个算法,利用顺序栈判断一个字符串是否为对称串。所谓对称串指从左向右读和从右向左读的序列相同。 解n个元素连续进栈,产生的连续出栈序列和输入序列正好相反,本算法就是利用这个特点设计的。对于字符串str,从头到尾将其所有元素连续进栈,如果所有元素连续出栈产生的序列和str从头到尾的字符依次相同,表示str是一个对称串,返回真; 否则表示str不是对称串,返回假。算法如下: bool symmetry(ElemType str[])//判断str是否为对称串 {int i; ElemType e; SqStack *st; //定义顺序栈指针 InitStack(st); //初始化栈 for (i=0;str[i]!='\0';i++) //将str的所有元素进栈 Push(st,str[i]); for (i=0;str[i]!='\0';i++) //处理str的所有字符 {Pop(st,e); //退栈元素e if (str[i]!=e) //若e与当前串字符不同表示不是对称串 {DestroyStack(st);//销毁栈 return false;//返回假 } } DestroyStack(st); //销毁栈 return true; //返回真 } 顺序栈采用一个数组存放栈中的元素。如果需要用到两个类型相同的栈,这时若为它们各自开辟一个数组空间,极有可能出现这样的情况: 第一个栈已满,再进栈就溢出了,而另一个栈还有很多空闲的存储空间。解决这个问题的方法是将两个栈合起来,如图3.6所示,用一个数组来实现这两个栈,这称为共享栈(share stack)。 图3.6共享栈 在设计共享栈时,由于一个数组(大小为MaxSize)有两个端点,两个栈有两个栈底,让一个栈的栈底为数组的始端,即下标为0处,另一个栈的栈底为数组的末端,即下标为MaxSize-1处,这样在两个栈中进栈元素时栈顶向中间伸展。 共享栈的4个要素如下。 栈空条件: 栈1空为top1==-1; 栈2空为top2==MaxSize。 栈满条件: top1==top2-1。 元素x进栈的操作: 进栈1操作为top1++;data[top1]=x; 进栈2操作为top2--;data[top2]=x。 出栈的操作: 出栈1操作为x=data[top1];top1--; 出栈2操作为x=data[top2];top2++。 在上述设置中,data数组表示共享栈的存储空间,top1和top2分别为两个栈的栈顶指针,这样该共享栈通过data、top1和top2来标识,也可以将它们设计为一个结构体类型: typedef struct {ElemType data[MaxSize];//存放共享栈中的元素 int top1,top2; //两个栈的栈顶指针 } DStack; //共享栈的类型 在实现共享栈的基本运算算法时需要增加一个形参i,指出是对哪个栈进行操作,例如i=1表示对栈1进行操作,i=2表示对栈2进行操作。 3.1.3栈的链式存储结构及其基本运算的实现 栈中数据元素的逻辑关系呈线性关系,所以栈可以像线性表一样采用链式存储结构。采用链式存储结构的栈称为链栈(linked stack)。链表有多种,这里采用带头结点的单链表来实现链栈。 链栈的优点是不存在栈满上溢出的情况。规定栈的所有操作都是在单链表的表头进行的(因为给定链栈后,已知头结点的地址,在其后面插入一个新结点和删除首结点都十分方便,对应算法的时间复杂度均为O(1))。 图3.7所示为头结点指针为s的链栈,首结点是栈顶结点,尾结点是栈底结点。栈中的元素自栈底到栈顶依次是a1,a2,…,an。 图3.7栈到链栈的映射 链栈中结点类型LinkStNode的声明如下: typedef struct linknode {ElemType data;//数据域 struct linknode *next; //指针域 } LinkStNode; //链栈结点类型 在以s为头结点指针的链栈(简称链栈s)中,可以归纳出对后面的算法设计来说非常重要的4个要素。 栈空的条件: s-next==NULL。 栈满的条件: 由于只有内存溢出时才出现栈满,通常不考虑这样的情况,所以在链栈中可以看成不存在栈满。 元素e进栈的操作: 新建一个结点存放元素e(由p指向它),将结点p插入头结点之后。 出栈的操作: 取出首结点的data值并将其删除。 图3.8创建一个空栈 在链栈上对应栈的基本运算算法设计如下。 1) 初始化栈: InitStack(&s) 该运算创建一个空链栈s,如图3.8所示。实际上是创建链栈的头结点,并将其next域置为NULL。算法如下: void InitStack(LinkStNode *&s) {s=(LinkStNode *)malloc(sizeof(LinkStNode)); snext=NULL; } 本算法的时间复杂度为O(1)。 2) 销毁栈: DestroyStack(&s) 该运算释放链栈s占用的全部结点空间,和单链表的销毁算法完全相同。算法如下: void DestroyStack(LinkStNode *&s) {LinkStNode *pre=s,*p=snext;//pre指向头结点,p指向首结点 while (p!=NULL) //循环到p为空 {free(pre); //释放pre结点 pre=p; //pre、p同步后移 p=prenext; } free(pre); //此时pre指向尾结点,释放其空间 } 本算法的时间复杂度为O(n),其中n为链栈中数据结点的个数。 3) 判断栈是否为空: StackEmpty(s) 该运算判断s->next=NULL的条件是否成立。算法如下: bool StackEmpty(LinkStNode *s) { return(snext==NULL); } 本算法的时间复杂度为O(1)。 4) 进栈: Push(&s,e) 该运算新建一个结点,用于存放元素e(由p指向它),然后将其插入头结点之后作为新的首结点。算法如下: bool Push(LinkStNode *&s,ElemType e) {LinkStNode *p; p=(LinkStNode *)malloc(sizeof(LinkStNode));//新建结点p pdata=e; //存放元素e pnext=snext; //将p结点插入作为首结点 snext=p; return true; } 本算法的时间复杂度为O(1)。 5) 出栈: Pop(&s,&e) 该运算在栈不为空的条件下提取首结点的数据域赋给引用型参数e,然后将其删除。算法如下: bool Pop(LinkStNode *&s,ElemType &e) {LinkStNode *p; if (snext==NULL)//栈空的情况 return false; //返回假 p=snext; //p指向首结点 e=pdata; //提取首结点值 snext=pnext; //删除首结点 free(p);//释放被删结点的存储空间 return true; //返回真 } 本算法的时间复杂度为O(1)。 6) 取栈顶元素: GetTop(s,&e) 该运算在栈不为空的条件下提取首结点的数据值赋给引用型参数e。算法如下: bool GetTop(LinkStNode *s,ElemType &e) {if (snext==NULL)//栈空的情况 return false; //返回假 e=snextdata; //提取首结点值 return true; //返回真 } 和出栈运算相比,本算法只是没有删除栈顶结点,其时间复杂度为O(1)。 【例3.5】设计一个算法判断输入的表达式中括号是否配对(假设只含有左、右圆括号)。 解该算法在表达式括号配对时返回真,否则返回假。设置一个链栈st,遍历表达式exp,遇到左括号时进栈; 遇到右括号时,若栈顶为左括号,则出栈,否则返回假。当表达式遍历完毕而且栈为空时返回真; 否则返回假。算法如下: bool Match(char exp[],int n) {int i=0; char e; bool match=true; LinkStNode *st; InitStack(st);//初始化链栈 while (in && match) //遍历exp中的所有字符 {if (exp[i]=='(') //当前字符为左括号,将其进栈 Push(st,exp[i]); else if (exp[i]==')') //当前字符为右括号 {if (GetTop(st,e)==true) //成功取栈顶元素e {if (e!='(') //栈顶元素不为'('时 match=false; //表示不匹配 else //栈顶元素为'('时 Pop(st,e); //将栈顶元素出栈 } else match=false; //无法取栈顶元素时表示不匹配 } i++; //继续处理其他字符 } if (!StackEmpty(st)) //栈不空时表示不匹配 match=false; DestroyStack(st); //销毁栈 return match; } 3.1.4栈的应用 在实际应用中,栈通常作为一种存放临时数据的容器。如果后存入的元素先处理,则采用栈。本节通过简单表达式求值和迷宫问题的求解过程来说明栈的应用。 1. 简单表达式求值 1) 问题描述 这里限定的简单表达式求值问题是用户输入一个包含+、-、*、/、正整数和圆括号的合法算术表达式,计算该表达式的运算结果。 2) 数据组织 简单表达式采用字符数组exp表示,其中只含有+、-、*、/、正整数和圆括号。为了方便,假设该表达式都是合法的算术表达式,例如exp="1+2*(4+12)",在设计相关算法中用到栈,这里采用顺序栈存储结构。 3) 设计运算算法 在算术表达式中,运算符位于两个操作数中间的表达式称为中缀表达式(infix expression),例如1+2*3就是一个中缀表达式。中缀表达式是一种最常用的表达式形式,日常生活中的表达式一般都是中缀表达式。 对中缀表达式的运算一般遵循“先乘除,后加减,从左到右计算,先括号内,后括号外”的规则,因此中缀表达式不仅要依赖运算符的优先级,还要处理括号。 算术表达式的另一种形式是后缀表达式(postfix expression)或逆波兰表达式,就是在算术表达式中运算符在操作数的后面,例如1+2*3的后缀表达式为1 2 3 * +。在后缀表达式中已经考虑了运算符的优先级,没有括号,只有操作数和运算符,而且越放在前面的运算符越优先执行。 同样,在算术表达式中,如果运算符在操作数的前面,称为前缀表达式(prefix expression),例如1+2*3的前缀表达式为+ 1 * 2 3。 后缀表达式是一种十分有用的表达式,它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式。所以对中缀表达式的求值过程是先将中缀算术表达式转换成后缀表达式,然后对该后缀表达式求值。 (1) 将算术表达式转换成后缀表达式。 在将一个中缀表达式转换成后缀表达式时,操作数之间的相对次序是不变的,但运算符的相对次序可能不同,同时还要除去括号。 所以在转换时需要从左到右遍历算术表达式,将遇到的操作数直接存放到后缀表达式中,将遇到的每一个运算符或者左括号都暂时保存到运算符栈,而且先执行的运算符先出栈。 图3.9两个'+'进行优先级比较 假设用exp字符数组存储满足前面条件的简单中缀表达式,其对应的后缀表达式存放在字符数组postexp中。下面讨论几种情况。 例如,若exp="1+2+3",转换过程是首先将操作数1存入postexp; 遇到第1个'+',尚未确定它是否最先执行,将其进栈; 再将操作数2存入postexp; 又遇到第2个'+',需要两个'+'进行优先级比较,如图3.9所示,如果直接将第2个'+'进栈,它以后一定先出栈,表示第2个'+'比第1个'+'先执行,显然是错误的。正确的做法是先将栈中的第1个'+'出栈并存入postexp,然后将第2个'+'进栈(表示第1个'+'先执行); 最后将操作数3存入postexp; 此时exp遍历完毕,出栈第2个'+'并存入postexp。得到的最后结果是postexp="1 2+3 +"。 归纳1: 在遍历exp遇到一个运算符op时,如果栈为空,直接将其进栈; 如果栈不空,只有当op的优先级高于栈顶运算符的优先级时才直接将op进栈(以后op先出栈表示先执行它); 否则依次出栈运算符并存入postexp(出栈的运算符都比op先执行),直到栈顶运算符的优先级小于op的优先级为止,然后将op进栈。 图3.10遇到')'的情况 再看看带有括号的例子,若exp="2*(1+3)-4",转换过程是将操作数2存入postexp; 遇到'*',将其进栈; 遇到'(',将其进栈; 将操作数1存入postexp; 遇到'+',将其进栈; 将操作数3存入postexp; 遇到')',如图3.10所示,出栈'+'并存入postexp,出栈'('; 遇到'-',出栈'*'并存入postexp,将'-'进栈; 将操作数4存入postexp; 此时exp扫描完毕,出栈'-'并存入postexp。得到的最后结果是postexp="2 1 3 + * 4 -"。 归纳2: 在遍历exp遇到一个运算符op时,如果op为'(',表示一个子表达式的开始,直接将其进栈; 如果op为')',表示一个子表达式的结束,需要计算该子表达式的值,则出栈运算符并存入postexp,直到栈顶为'(',再将'('出栈; 如果op是其他运算符,而栈顶为'(',直接将其进栈。 设置一个运算符栈Optr,初始时为空。为了方便后面将数值串转换为对应的数值,在后缀表达式中的每个数字串的末尾添加一个'#'。将算术表达式exp转换成后缀表达式postexp的过程如下: while (从exp读取字符ch,ch!='\0') {ch为数字: 将后续的所有数字均依次存放到postexp中,并以字符'#'标识数字串结束; ch为左括号'(': 将此括号进到Optr栈中; ch为右括号')': 将Optr中出栈时遇到的第1个左括号'('以前的运算符依次出栈并 存放到postexp中,然后将左括号'('出栈; ch为其他运算符: if (栈空或者栈顶运算符为'(') 直接将ch进栈; else if (ch的优先级高于栈顶运算符的优先级) 直接将ch进栈; else 依次出栈并存入postexp中,直到ch的优先级高于栈顶运算符,然后将ch进栈; } 若exp遍历完毕,则将Optr中的所有运算符依次出栈并存放到postexp中。 对于简单的算术表达式,'+'和'-'运算符的优先级相同,'*'和'/'运算符的优先级相同,只有'*'和'/'运算符的优先级高于'+'和'-'运算符的优先级。所以上述过程进一步改为如下: while (从exp读取字符ch,ch!='\0') {ch为数字: 将后续的所有数字均依次存放到postexp中,并以字符'#'标识数字串结束; ch为左括号'(': 将此括号进到Optr栈中; ch为右括号')': 将Optr中出栈时遇到的第1个左括号'('以前的运算符依次出栈并 存放到postexp中,然后将左括号'('出栈; ch为'+'或'-': 出栈运算符并存放到postexp中,直到栈空或者栈顶为'(',然后将ch 进栈; ch为'*'或'/': 出栈运算符并存放到postexp中,直到栈空或者栈顶为'('、'+'或'-', 然后将ch进栈; } 若exp遍历完毕,则将Optr中的所有运算符依次出栈并存放到postexp中。 例如对于表达式“(56-20)/(4+2)”,其转换为后缀表达式的过程如表3.1所示,最后得到的后缀表达式为“56#20#-4#2#+/”。 表3.1表达式“(56-20)/(4+2)”转换成后缀表达式的过程 操作postexpOptr栈 (栈底→栈顶) 遇到ch为'(',将此括号进栈( 遇到ch为数字,将56#存入postexp中56#( 遇到ch为'-',直接将ch进栈56#(- 遇到ch为数字,将20#存入postexp中56#20#(- 遇到ch为')',将栈中'('之前的运算符'-'出栈并存入postexp中,然后将'('出栈56#20#- 遇到ch为'/',将ch进栈56#20#-/ 遇到ch为'(',将此括号进栈56#20#-/( 遇到ch为数字,将4#存入postexp中56#20#-4#/( 遇到ch为'+',由于栈顶运算符为'(',则直接将ch进栈56#20#-4#/(+ 遇到ch为数字,将2#存入postexp中56#20#-4#2#/(+ 遇到ch为')',将栈中'('之前的运算符'+'出栈并存入postexp中,然后将'('出栈56#20#-4#2#+/ str遍历完毕,则将Optr栈中的所有运算符依次出栈并存入postexp中,得到最终的后缀表达式56#20#-4#2#+/ 设置运算符栈类型SqStack中的ElemType为char类型。根据上述原理得到的trans()算法如下: void trans(char *exp,char postexp[])//将算术表达式exp转换成后缀表达式postexp {char e; SqStack *Optr; //定义运算符栈指针 InitStack(Optr); //初始化运算符栈 int i=0; //i作为postexp的下标 while (*exp!='\0') //exp表达式未遍历完时循环 {switch(*exp) { case '(': //判定为左括号 Push(Optr,'(');//左括号进栈 exp++; //继续遍历其他字符 break; case ')': //判定为右括号 Pop(Optr,e); //出栈元素e while (e!='(') //不为'('时循环 {postexp[i++]=e; //将e存放到postexp中 Pop(Optr,e); //继续出栈元素e } exp++; //继续遍历其他字符 break; case '+': //判定为加号或减号 case '-': while (!StackEmpty(Optr)) //栈不空时循环 {GetTop(Optr,e); //取栈顶元素e if (e!='(') //e不是'(' {postexp[i++]=e; //将e存放到postexp中 Pop(Optr,e); //出栈元素e } else //e是'('时退出循环 break; } Push(Optr,*exp); //将'+'或'-'进栈 exp++; //继续遍历其他字符 break; case '*': //判定为'*'或'/'号 case '/': while (!StackEmpty(Optr)) //栈不空时循环 {GetTop(Optr,e); //取栈顶元素e if (e=='*' ‖ e=='/') //将栈顶'*'或'/'运算符出栈并存放到postexp中 {postexp[i++]=e; //将e存放到postexp中 Pop(Optr,e); //出栈元素e } else //e为非'*'或'/'运算符时退出循环 break; } Push(Optr,*exp); //将'*'或'/'进栈 exp++; //继续遍历其他字符 break; default: //处理数字字符 while (*exp='0' && *exp='9') {postexp[i++]=*exp; exp++; } postexp[i++]='#';//用#标识一个数字串结束 } } while (!StackEmpty(Optr)) //此时exp遍历完毕,栈不空时循环 {Pop(Optr,e); //出栈元素e postexp[i++]=e; //将e存放到postexp中 } postexp[i]='\0'; //给postexp表达式添加结束标识 DestroyStack(Optr); //销毁栈 } (2) 后缀表达式求值。 后缀表达式的求值过程是从左到右遍历后缀表达式postexp,若读取的是一个操作数,将它进操作数栈,若读取的是一个运算符op,从操作数栈中连续出栈两个操作数,假设为a(第1个出栈的元素)和b(第2个出栈的元素),计算b op a的值,并将计算结果进操作数栈。当整个后缀表达式遍历结束时,操作数栈中的栈顶元素就是表达式的计算结果。 在后缀表达式求值算法设计中操作数栈为Opnd,用于临时存放要进行某种算术运算的操作数。下面给出后缀表达式求值的过程,假设postexp存放的后缀表达式是正确的,在while循环结束后,Opnd栈中恰好有一个操作数,它就是该后缀表达式的求值结果。 while (从postexp读取字符ch,ch!='\0') {ch为'+': 从Opnd栈中出栈两个数值a和b,计算c=b+a;将c进栈; ch为'-': 从Opnd栈中出栈两个数值a和b,计算c=b-a;将c进栈; ch为'*': 从Opnd栈中出栈两个数值a和b,计算c=b*a;将c进栈; ch为'/': 从Opnd栈中出栈两个数值a和b,若a不为零,计算c=b/a;将c进栈; ch为数字字符: 将连续的数字串转换成数值d,将d进栈; } 返回Opnd栈的栈顶操作数(即后缀表达式的值); 后缀表达式“56#20#-4#2#+/”的求值过程如表3.2所示,最后的求值结果为6,与原表达式“(56-20)/(4+2)”的计算结果一致。 表3.2后缀表达式“56#20#-4#2#+/”的求值过程 操作Opnd栈(栈底→栈顶) 遇到56#,将56进栈56 遇到20#,将20进栈56,20 遇到'-',出栈两次,将56-20=36进栈36 遇到4#,将4进栈36,4 遇到2#,将2进栈36,4,2 遇到'+',出栈两次,将4+2=6进栈36,6 遇到'/',出栈两次,将36/6=6进栈6 postexp遍历完毕,算法结束,栈顶数值6即为所求 设置操作数栈类型SqStack1中的ElemType为double类型,在栈基本运算名称的后面加上“1”以区别前面字符栈的基本运算。根据上述计算原理得到求后缀表达式值的算法如下: double compvalue(char *postexp)//计算后缀表达式的值 {double d,a,b,c,e; SqStack1 *Opnd; //定义操作数栈 InitStack1(Opnd); //初始化操作数栈 while (*postexp!='\0') //postexp字符串未遍历完时循环 {switch (*postexp) { case '+': //判定为'+'号 Pop1(Opnd,a); //出栈元素a Pop1(Opnd,b); //出栈元素b c=b+a; //计算c Push1(Opnd,c); //将计算结果c进栈 break; case '-': //判定为'-'号 Pop1(Opnd,a); //出栈元素a Pop1(Opnd,b); //出栈元素b c=b-a; //计算c Push1(Opnd,c); //将计算结果c进栈 break; case '*': //判定为'*'号 Pop1(Opnd,a); //出栈元素a Pop1(Opnd,b); //出栈元素b c=b*a; //计算c Push1(Opnd,c); //将计算结果c进栈 break; case '/': //判定为'/'号 Pop1(Opnd,a); //出栈元素a Pop1(Opnd,b); //出栈元素b if (a!=0) {c=b/a; //计算c Push1(Opnd,c); //将计算结果c进栈 break; } else {printf("\n\t除零错误!\n"); exit(0); //异常退出 } break; default: //处理数字字符 d=0; //将连续的数字字符转换成对应的数值存放到d中 while (*postexp='0' && *postexp='9') {d=10*d+*postexp-'0'; postexp++; } Push1(Opnd,d); //将数值d进栈 break; } postexp++; //继续处理其他字符 } GetTop1(Opnd,e); //取栈顶元素e DestroyStack1(Opnd); //销毁栈 return e; //返回e } 4) 设计求解程序 设计以下主函数调用上述算法: int main() {char exp[]="(56-20)/(4+2)";//可将exp改为键盘输入 char postexp[MaxSize]; trans(exp,postexp);//将exp转换为postexp printf("中缀表达式:%s\n",exp);//输出exp printf("后缀表达式:%s\n",postexp);//输出postexp printf("表达式的值:%g\n",compvalue(postexp));//求postexp的值并输出 return 1; } 5) 运行结果 运行本程序,得到对应的结果如下: 中缀表达式:(56-20)/(4+2) 后缀表达式:56#20#-4#2#+/ 表达式的值:6 2. 求解迷宫问题 1) 问题描述 给定一个M×N的迷宫图,求一条从指定入口到出口的迷宫路径,在行走中一步只能从当前方块移动到上、下、左、右相邻方块中的一个方块。假设一个迷宫图如图3.11所示(这里M=8,N=8),其中的每个方块用空白表示通道,用阴影表示障碍物。 一般情况下,所求迷宫路径是简单路径,即在求得的迷宫路径上不会重复出现同一个方块。一个迷宫图的迷宫路径可能有多条,这些迷宫路径有长有短, 图3.11一个迷宫的示意图 这里仅考虑用栈求一条从指定入口到出口的迷宫路径。 2) 数据组织 为了表示迷宫,设置一个数组mg,其中每个元素表示一个方块的状态,为0时表示对应方块是通道,为1时表示对应方块是障碍物(不可走)。为了算法方便,一般在迷宫的外围加一条围墙。图3.11所示的迷宫对应的迷宫数组mg(由于迷宫的四周加了一道围墙,故mg数组的行数和列数均加上2)如下: int mg[M+2][N+2]= {{1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1} }; 另外,在算法中用到的栈采用顺序栈存储结构,即将迷宫栈声明如下: typedef struct {int i;//当前方块的行号 int j; //当前方块的列号 int di; //di是走到下一相邻可走方块的方位号 } Box; //方块类型 typedef struct {Box data[MaxSize]; int top; //栈顶指针 } StType; //顺序栈类型 3) 设计运算算法 对于迷宫中的每个方块,有上、下、左、右4个方块相邻,如图3.12所示,第i行第j列的当前方块的位置记为(i,j),规定上方方块为方位0,并按顺时针方向递增编号。在试探过程中,假设按从方位0到方位3的方向查找下一个可走的相邻方块。 求迷宫问题就是在一个指定的迷宫中求出从入口到出口的一条路径。在求解时采用“穷举法”,即从入口出发,按方位0到方位3的次序试探相邻的方块,一旦找到一个可走的相邻方块就继续走下去,并记下所走的方位; 若某个方块没有相邻的可走方块,则沿原路退回到前一个方块,换下一个方位再继续试探,直到所有可能的通路都试探完为止。 为了保证在任何位置上都能沿原路退回(称为回溯),需要保存从入口到当前位置的路径上走过的方块,由于回溯的过程是从当前位置退到前一个方块,体现出后进先出的特点,所以采用栈保存走过的方块。 若一个非出口方块(i,j)是可走的,将它进栈,每个刚进栈的方块,其方位di置为-1(表示尚未试探它的周围),然后开始从方位0到方位3试探这个栈顶方块的四周,如果找到某个方位d的相邻方块(i1,j1)是可走的,则将栈顶方块(i,j)的方位di置为d,同时将方块(i1,j1)进栈,再继续从方块(i1,j1)做相同的操作。若方块(i,j)的四周没有一个方位是可走的,将它退栈,如图3.13所示,前一个方块(x,y)变成栈顶方块,再从方块(x,y)的下一个方位继续试探。 图3.12迷宫方位图 图3.13方块(i,j)的四周没有一个方位可走的情况 在算法中应保证试探的相邻可走方块不是已走路径上的方块。如方块(i,j)已进栈,在试探方块(i+1,j)的相邻可走方块时又会试探到方块(i,j)。也就是说,从方块(i,j)出发会试探方块(i+1,j),而从方块(i+1,j)出发又会试探方块(i,j),这样可能会引起死循环,为此在一个方块进栈后将对应的mg数组元素值改为-1(变为不可走的方块),当退栈时(表示该栈顶方块没有相邻可走方块)将其恢复为0。 求解迷宫中从入口(xi,yi)到出口(xe,ye)的一条迷宫路径的过程如下: 将入口(xi,yi)进栈(其初始方位设置为-1); mg[xi][yi]=-1; while (栈不空) {取栈顶方块(i,j,di); if ((i,j)是出口(xe,ye)) {输出栈中的全部方块构成一条迷宫路径; return true; } 查找(i,j,di)的下一个相邻可走方块; if (找到一个相邻可走方块) {该方块位置为(i1,j1),对应方位d; 将栈顶方块的di设置为d; (i1,j1,-1)进栈; mg[i1][j1]=-1; } if (没有找到(i,j,di)的任何相邻可走方块) {将(i,j,di)出栈; mg[i][j]=0; } } return false;//没有找到迷宫路径 根据上述过程得到求迷宫问题的算法如下: bool mgpath(int xi,int yi,int xe,int ye)//求解路径为(xi,yi)(xe,ye) {Box path[MaxSize], e; int i,j,di,i1,j1,k; bool find; StType *st; //定义栈st InitStack(st); //初始化栈顶指针 e.i=xi; e.j=yi; e.di=-1; //设置e为入口 Push(st,e); //方块e进栈 mg[xi][yi]=-1; //将入口的迷宫值置为-1,避免重复走到该方块 while (!StackEmpty(st)) //栈不空时循环 {GetTop(st,e); //取栈顶方块e i=e.i; j=e.j; di=e.di; if (i==xe && j==ye) //找到了出口,输出该路径 {printf("一条迷宫路径如下:\n"); k=0;//k表示路径中的方块数 while (!StackEmpty(st)) {Pop(st,e); //出栈方块e path[k++]=e; //将e添加到path数组中 } while (k0) {printf("\t(%d,%d)",path[k-1].i,path[k-1].j); if ((k+1)%5==0) //每输出5个方块后换一行 printf("\n"); k--; } printf("\n"); DestroyStack(st); //销毁栈 return true; //输出一条迷宫路径后返回true } find=false; while (di4 && !find) //找方块(i,j)的下一个相邻可走方块(i1,j1) {di++; switch(di) { case 0:i1=i-1; j1=j; break; case 1:i1=i; j1=j+1; break; case 2:i1=i+1; j1=j; break; case 3:i1=i; j1=j-1; break; } if (mg[i1][j1]==0) find=true; //找到一个相邻可走方块,设置find为真 } if (find) //找到了一个相邻可走方块(i1,j1) {stdata[sttop].di=di; //修改原栈顶元素的di值 e.i=i1; e.j=j1; e.di=-1; Push(st,e); //相邻可走方块e进栈 mg[i1][j1]=-1; //将(i1,j1)迷宫值置为-1,避免重复走到该方块 } else //没有路径可走,则退栈 {Pop(st,e); //将栈顶方块退栈 mg[e.i][e.j]=0; //让退栈方块的位置变为其他路径可走方块 } } DestroyStack(st); //销毁栈 return false; //表示没有可走路径,返回false } 4) 设计求解程序 建立以下主函数调用上述算法: int main() {if (!mgpath(1,1,M,N)) printf("该迷宫问题没有解!"); return 1; } 5) 运行结果 对于如图3.11所示的迷宫,从入口(1,1)到出口(8,8)的求解结果如下: 一条迷宫路径如下: (1,1)(1,2)(2,2)(3,2)(3,1) (4,1)(5,1)(5,2)(5,3)(6,3) (6,4)(6,5)(5,5)(4,5)(4,6) (4,7)(3,7)(3,8)(4,8)(5,8) (6,8)(7,8)(8,8) 图3.14用栈求解的迷宫路径 上述迷宫路径的显示结果如图3.14所示,图中路径上方块(i,j)中的箭头表示从该方块行走到下一个相邻方块的方位,例如方块(1,1)中的箭头是“→”,该箭头表示方位1,即方块(1,1)走方位1到相邻方块(1,2)。显然这个解不是最优解,即不是最短路径,在使用队列求解时可以找出最短路径,这将在后面介绍。 实际上,在使用栈求解迷宫问题时,当找到出口后输出一个迷宫路径,然后可以继续回溯搜索下一条迷宫路径。采用这种回溯方法可以找出所有的迷宫路径。 3.2 队列 队列也有广泛的应用,特别是在操作系统的资源分配和排队论中大量地使用了队列。本节主要讨论队列及其应用。 3.2.1队列的定义 队列(queue)简称队,它也是一种操作受限的线性表,其限制为仅允许在表的一端进行插入操作,而在表的另一端进行删除操作。把进行插入的一端称为队尾(rear),把进行删除的一端称为队头或队首(front), 图3.15一个队列 如图3.15所示。向队列中插入新元素称为进队或入队(enqueue),新元素进队后就成为新的队尾元素; 从队列中删除元素称为出队或离队(dequeue),元素出队后,其直接后继元素就成为队首元素。 由于队列的插入和删除操作分别是在各自的一端进行的,每个元素必然按照进入的次序出队,所以又把队列称为先进先出表(first in first out,FIFO)。 例如,若干个人走过一个独木桥,下桥的顺序和上桥的顺序相同,在这里该独木桥就是一个队列。 队列抽象数据类型的定义如下: ADT Queue {数据对象: D={ ai|1≤i≤n,n≥0,ai为ElemType类型} //ElemType是自定义类型标识符 数据关系: R={ai,ai+1 | ai,ai+1∈D,i=1,…,n-1} 基本运算: InitQueue(&q): 初始化队列,构造一个空队列q。 DestroyQueue(&q): 销毁队列,释放为队列q分配的存储空间。 QueueEmpty(q): 判断队列是否为空,若队列q为空,则返回真; 否则返回假。 enQueue(&q,e): 进队列,将元素e进队作为队尾元素。 deQueue(&q,&e): 出队列,从队列q中出队一个元素,并将其值赋给e。 } 【例3.6】若元素的进队顺序为1234,能否得到3142的出队顺序? 解若进队顺序为1234,不同于栈,出队的顺序只有一种,即1234(先进先出),所以不能得到3142的出队顺序。 3.2.2队列的顺序存储结构及其基本运算的实现 队列中数据元素的逻辑关系呈线性关系,所以队列可以像线性表一样采用顺序存储结构进行存储,即分配一块连续的存储空间来存放队列中的元素,并用两个整型变量来反映队列中元素的变化,它们分别存储队首元素和队尾元素的下标位置,分别称为队首指针(队头指针)和队尾指针。采用顺序存储结构的队列称为顺序队(sequential queue)。 假设队列中元素的个数最多不超过整数MaxSize,所有的元素都具有ElemType数据类型,则顺序队类型SqQueue声明如下: typedef struct {ElemType data[MaxSize];//存放队中元素 int front,rear; //队头和队尾指针 } SqQueue; //顺序队类型 队列到顺序队的映射过程如图3.16所示,并且约定在顺序队中队头指针front指向当前队列中队头元素的前一个位置,队尾指针rear指向当前队列中队尾元素的位置。本节采用队列指针q的方式建立和使用顺序队。 图3.16队列到顺序队的映射 1. 在顺序队中实现队列的基本运算 图3.17所示为一个顺序队操作过程的示意图,其中MaxSize=5。初始时front=rear=-1。图3.17(a)表示一个空队; 图3.17(b)表示进队5个元素后的状态; 图3.17(c)表示出队两个元素后的状态; 图3.17(d)表示再出队3个元素后的状态。 从图中可以看到,队空的条件为front=rear(图3.17(a)和图3.17(d)都是这种情况); 元素进队时队尾指针rear总是增1,所以队满条件是rear指向最大下标,即rear==MaxSize-1(图3.17(b)和图3.17(c)都是这种情况)。 图3.17队列操作过程的示意图 综上所述,对于q所指的顺序队(即顺序队q),初始时设置q->rear=q->front=-1,可以归纳出对后面的算法设计来说非常重要的4个要素。 队空的条件: q-front==q-rear。 队满的条件: q-rear==MaxSize-1(data数组的最大下标)。 元素e进队的操作: 先将rear增1,然后将元素e放在data数组的rear位置。 出队的操作: 先将front增1,然后取出data数组中front位置的元素。 在顺序队上对应队列的基本运算算法设计如下。 1) 初始化队列: InitQueue(&q) 构造一个空队列q,将front和rear指针均设置成初始状态,即-1值。算法如下: void InitQueue(SqQueue *&q) {q=(SqQueue *)malloc(sizeof(SqQueue)); qfront=qrear=-1; } 2) 销毁队列: DestroyQueue(&q) 释放队列q占用的存储空间。算法如下: void DestroyQueue(SqQueue *&q) { free(q); } 3) 判断队列是否为空: QueueEmpty(q) 若队列q为空,返回真; 否则返回假。算法如下: bool QueueEmpty(SqQueue *q) { return(qfront==qrear); } 4) 进队列: enQueue(&q,e) 在队列q不满的条件下先将队尾指针rear增1,然后将元素e插到该位置。算法如下: bool enQueue(SqQueue *&q,ElemType e) {if (qrear==MaxSize-1)//队满上溢出 return false; //返回假 qrear++; //队尾增1 qdata[qrear]=e; //在rear位置插入元素e return true; //返回真 } 5) 出队列: deQueue(&q,&e) 在队列q不空的条件下先将队头指针front增1,并将该位置的元素值赋给e。算法如下: bool deQueue(SqQueue *&q,ElemType &e) {if (qfront==qrear)//队空下溢出 return false; qfront++; e=qdata[qfront]; return true; } 上述5个基本运算算法的时间复杂度均为O(1)。 2. 在环形队中实现队列的基本运算 在前面的顺序队操作中,元素进队时队尾指针rear增1,元素出队时队头指针front增1,当队满的条件(即rear==MaxSize-1)成立时,表示此时队满(上溢出)了,不能再进队元素。实际上,当rear==MaxSize-1成立时,队列中可能还有空位置,这种因为队满条件设置不合理导致队满条件成立而队列中仍然有空位置的情况称为假溢出(false overflow),图3.17(c)所示就是假溢出的情况。 可以看出,在出现假溢出时队尾指针rear指向data数组的最大下标,而另外一端还有若干个空位置。解决的方法是把data数组的前端和后端连接起来,形成一个环形数组,即把存储队列元素的数组从逻辑上看成一个环,称为环形队列或者循环队列(circular queue)。 环形队列首尾相连后,当队尾指针rear=MaxSize-1后,再前进一个位置就到达0,于是就可以使用另一端的空位置存放队列元素了。实际上存储器中的地址总是连续编号的,为此采用数学上的求余运算(%)来实现: 队头指针front循环增1: front=(front+1)%MaxSize 队尾指针rear循环增1: rear=(rear+1)%MaxSize 环形队列的队头指针front和队尾指针rear初始化时都置为0,即front=rear=0。在进队元素和出队元素时,队尾指针和队头指针分别循环增1。 那么,环形队列q的队满和队空条件如何设置呢?显然队空条件是q->rear==q->front。当进队元素的速度快于出队元素的速度时,队尾指针会回过来很快赶上队首指针,此时可以看出环形队列的队满条件也是q->rear==q->front,也就是说无法仅通过这两个指针的当前位置区分开队空和队满。 那么怎样区分队空和队满呢?改为以“队尾指针循环增1时等于队头指针”作为队满条件,也就是说尝试进队一次,若达到队头,就认为队满了,不能再进队。这样环形队列少用一个元素空间,即该队列中在任何时刻最多只能有MaxSize-1个元素。 因此,在环形队列q中设置队空条件是q->rear==q->front; 队满条件是(q->rear+1) % MaxSize==q->front。而进队操作和出队操作改为分别将队尾rear和队头指针front循环进1。 图3.18说明了环形队列操作的几种状态,这里假设MaxSize等于5。 图3.18环形队列操作示意图 在这样设计的环形队列中,实现队列的基本运算算法如下。 1) 初始化队列: InitQueue(&q) 构造一个空队列q,将front和rear指针均设置成初始状态,即0值。算法如下: void InitQueue(SqQueue *&q) {q=(SqQueue *)malloc (sizeof(SqQueue)); qfront=qrear=0; } 2) 销毁队列: DestroyQueue(&q) 释放队列q占用的存储空间。算法如下: void DestroyQueue(SqQueue *&q) { free(q); } 3) 判断队列是否为空: QueueEmpty(q) 若队列为空,返回真; 否则返回假。算法如下: bool QueueEmpty(SqQueue *q) { return(qfront==qrear); } 4) 进队列: enQueue(&q,e) 在队列不满的条件下先将队尾指针rear循环增1,然后将元素插到该位置。算法如下: bool enQueue(SqQueue *&q,ElemType e) {if ((qrear+1)%MaxSize==qfront)//队满上溢出 return false; qrear=(qrear+1)%MaxSize; qdata[qrear]=e; return true; } 5) 出队列: deQueue(&q,&e) 在队列q不空的条件下将队首指针front循环增1,取出该位置的元素并赋给e。算法如下: bool deQueue(SqQueue *&q,ElemType &e) {if (qfront==qrear)//队空下溢出 return false; qfront=(qfront+1)%MaxSize; e=qdata[qfront]; return true; } 上述5个基本运算算法的时间复杂度均为O(1)。 在实际应用中有时需要求队列中元素的个数,如果采用遍历data数组的方式来实现会导致性能低下,通常有两种方法。 一种方法是在环形队列中增加一个表示队中元素个数的count域,在进队、出队元素时维护count的正确性,也就是说初始时count=0,在进队一个元素时执行count++,在出队一个元素时执行count--。 另外一种方法是利用环形队列状态求元素的个数,由于队头指针front指向队头元素的前一个位置,队尾指针rear指向队尾元素的位置,它们都是已知的,可以求出队中元素的个数=(rear-front+MaxSize)%MaxSize。在前面的环形队列中增加如下求元素个数的算法: int Count(SqQueue *q)//求队列中元素的个数 { return(qrear-qfront+MaxSize)%MaxSize; } 说明: 环形队列解决了假溢出现象,更充分地利用了队列空间。那么是不是在任何情况下都采用环形队列呢?答案是否定的。在环形队列中,随着多次进队和出队,已出队元素的空间可能被新进队的元素覆盖,而非环形队列中已出队的元素仍在其中,不会被覆盖。如果需要利用出队的元素来求解时采用非环形队列为好,例如用队列求解迷宫问题就属于这种情况。 【例3.7】对于环形队列来说,如果知道队头指针和队列中元素的个数,则可以计算出队尾指针。也就是说,可以用队列中的元素个数代替队尾指针。设计出这种环形队列的初始化、进队、出队和判队空算法。 解依题意设计的环形队列类型如下。 typedef struct {ElemType data[MaxSize]; int front;//队头指针 int count; //队列中元素的个数 } QuType; //本例的环形队列类型 当已知队列的队头指针front和队列中元素的个数count后,队尾指针rear的计算公式是rear=(front+count)%MaxSize。因此,这种队列的队空条件为count==0; 队满条件为count==MaxSize; 元素e的进队操作是先根据队头指针和元素的个数求出队尾指针rear,将rear循环增1,然后将元素e放置在rear处; 出队操作是先将队头指针循环增1,然后取出该位置的元素。 对应的算法如下: void InitQueue(QuType *&qu)//初始化算法 {qu=(QuType *)malloc(sizeof(QuType)); qufront=0; //将队头指针设置为0 qucount=0; //将队列中元素的个数设置为0 } bool EnQueue(QuType *&qu,ElemType x) //进队算法 {int rear; //临时存放队尾指针 if (qucount==MaxSize) //队满上溢出 return false; else {rear=(qufront+qucount)%MaxSize; //求队尾位置 rear=(rear+1)%MaxSize; //队尾指针循环增1 qudata[rear]=x; qucount++; //元素的个数增1 return true; } } bool DeQueue(QuType *&qu,ElemType &x) //出队算法 {if (qucount==0) //队空下溢出 return false; else {qufront=(qufront+1)%MaxSize; //队头循环增1 x=qudata[qufront]; qucount--; //元素的个数减1 return true; } } bool QueueEmpty(QuType *qu) //判队空算法 { return(qucount==0); } 注意: 在采用本例设计的环形队列中最多可以放置MaxSize个元素。 3.2.3队列的链式存储结构及其基本运算的实现 队列中数据元素的逻辑关系呈线性关系,所以队列可以像线性表一样采用链式存储结构。采用链式存储结构的队列称为链队(linked queue)。链表有多种,这里是采用单链表来实现链队的。 在这样的链队中只允许在单链表的表头进行删除操作(出队)和在单链表的表尾进行插入操作(进队),因此需要使用队头指针front和队尾指针rear两个指针,用front指向队首结点,用rear指向队尾结点。和链栈一样,链队中也不存在队满上溢出的情况。 链队的存储结构如图3.19所示。链队中数据结点的类型DataNode声明如下: typedef struct qnode {ElemType data;//存放元素 struct qnode *next; //下一个结点指针 } DataNode; //链队数据结点的类型 图3.19链队的存储结构 链队头结点(或链队结点)的类型LinkQuNode声明如下: typedef struct {DataNode *front;//指向队首结点 DataNode *rear; //指向队尾结点 } LinkQuNode; //链队结点的类型 图3.20说明了一个链队q的动态变化过程。图3.20(a)是链队的初始状态,图3.20(b)是在链队中3个元素进队后的状态,图3.20(c)是链队中一个元素出队后的状态。 图3.20一个链队的动态变化过程 在以q为链队结点指针的链队(简称链队q)中,可以归纳出对后面的算法设计来说非常重要的4个要素。 队空的条件: q-rear==NULL(也可以为q-front==NULL)。 队满的条件: 不考虑。 元素e进队的操作: 新建一个结点存放元素e(由p指向它),将结点p插入作为尾结点。 出队的操作: 取出队首结点的data值并将其删除。 在链队上对应队列的基本运算算法设计如下。 1) 初始化队列: InitQueue(&q) 构造一个空队,即创建一个链队结点,其front和rear域均置为NULL。算法如下: void InitQueue(LinkQuNode *&q) {q=(LinkQuNode *)malloc(sizeof(LinkQuNode)); qfront=qrear=NULL; } 本算法的时间复杂度为O(1)。 2) 销毁队列: DestroyQueue(&q) 释放链队占用的全部存储空间,包括链队结点和所有数据结点的存储空间。算法如下: void DestroyQueue(LinkQuNode *&q) {DataNode *pre=qfront,*p;//pre指向队首结点 if (pre!=NULL) {p=prenext; //p指向pre结点的后继结点 while (p!=NULL) //p不空时循环 {free(pre); //释放pre结点 pre=p;p=pnext; //pre、p同步后移 } free(pre); //释放最后一个数据结点 } free(q); //释放链队结点 } 本算法的时间复杂度为O(n),其中n为链队中数据结点的个数。 3) 判断队列是否为空: QueueEmpty(q) 若链队为空,返回真; 否则返回假。算法如下: bool QueueEmpty(LinkQuNode *q) { return(qrear==NULL); } 本算法的时间复杂度为O(1)。 4) 进队列: enQueue(&q,e) 创建一个新结点用于存放元素e(由p指向它)。若原队列为空,则将链队结点的两个域均指向结点p,否则将结点p链接到单链表的末尾,并让链队结点的rear域指向它。算法如下: bool enQueue(LinkQuNode *&q,ElemType e) {DataNode *p; p=(DataNode *)malloc(sizeof(DataNode));//创建新结点 pdata=e; pnext=NULL; if (qrear==NULL) //若链队空,则新结点既是首结点又是尾结点 qfront=qrear=p; else //若链队不空 {qrearnext=p; //将结点p链到队尾,并将rear指向它 qrear=p; } return true; } 本算法的时间复杂度为O(1)。 5) 出队列: deQueue(&q,&e) 若原队列为空,则下溢出返回假; 若原队列不空,则将首结点的data域值赋给e,并删除之,若原队列只有一个结点,则需将链队结点的两个域均置为NULL,表示队列已为空。算法如下: bool deQueue(LinkQuNode *&q,ElemType &e) {DataNode *t; if (qrear==NULL)//原来队列为空 return false; t=qfront; //t指向首结点 if (qfront==qrear) //原来队列中只有一个数据结点时 qfront=qrear=NULL; else //原来队列中有两个或两个以上结点时 qfront=qfrontnext; e=tdata; free(t); return true; } 本算法的时间复杂度为O(1)。 【例3.8】采用一个不带头结点、只有一个尾结点指针rear的循环单链表存储队列,设计队列的初始化、进队和出队算法。 解本例的链队如图3.21所示,用只有尾结点指针rear的循环单链表作为队列存储结构,其中每个结点的类型为LinkNode(LinkNode为单链表结点类型,在第2章中已声明),rear指针用于唯一地标识链队,对应链队的4个要素如下。 图3.21用只有尾结点指针的循环单链表作为队列存储结构 队空的条件: rear==NULL。 队满的条件: 不考虑。 元素e进队的操作: 新建一个结点存放元素e(由p指向它),将结点p插入作为尾结点,让rear指向这个新的尾结点。 出队的操作: 取出队头结点(rear所指结点的后继结点)的data值并将其删除。 需要注意的是,在该链队进队和出队操作后链队或者为空,或者为一个不带头结点的由尾结点指针rear唯一标识的循环单链表,不能改变其结构特性。 对应的队列基本运算算法如下: void initQueue(LinkNode *&rear)//初始化算法 { rear=NULL; } bool enQueue(LinkNode *&rear,ElemType e) //进队算法 {LinkNode *p; p=(LinkNode *)malloc(sizeof(LinkNode)); //创建新结点 pdata=e; if (rear==NULL) //原链队为空 {pnext=p; //改为循环链表 rear=p; //rear指向新结点 } else //原链队不空 {pnext=rearnext; //将p结点插入rear结点之后 rearnext=p; //改为循环链表 rear=p; //rear指向新结点 } return true; } bool deQueue(LinkNode *&rear,ElemType &e) //出队算法 {LinkNode *t; if (rear==NULL) //队空 return false; else if (rearnext==rear) //原队中只有一个结点 {e=reardata; free(rear); rear=NULL; //让rear为空链表 } else //原队中有两个或两个以上的结点 {t=rearnext; //t指向队头结点 e=tdata; rearnext=tnext; //删除t结点 free(t); //释放结点空间 } return true; } bool queueEmpty(LinkNode *rear) //判队空算法 { return(rear==NULL); } 3.2.4队列的应用举例 在实际应用中,队列通常作为一种存放临时数据的容器。如果先存入的元素先处理,则采用队列。本节通过报数问题和迷宫问题的求解过程介绍队列的应用。 1. 求解报数问题 1) 问题描述 设有n个人站成一排,从左向右的编号分别为1~n,现在从左往右报数“1,2,1,2,…”,数到“1”的人出列,数到“2”的立即站到队伍的最右端。报数过程反复进行,直到n个人都出列为止。要求给出他们的出列顺序。 例如,当n=8时初始序列为: 12345678 则出列顺序为: 13572648 2) 数据组织 用一个队列解决出列问题,由于这里不需要使用已经出队后的元素,所以采用环形队列。 3) 设计运算算法 采用的算法思想是先将n个人的编号进队,然后反复执行以下操作,直到队列为空。 (1) 出队一个元素,输出其编号(报数为1的人出列)。 (2) 若队列不空,再出队一个元素,并将刚出列的元素进队(报数为2的人站到队伍的最右端,即队尾)。 对应的算法如下: void number(int n) {int i; ElemType e; SqQueue *q;//环形队列指针q InitQueue(q); //初始化队列q for (i=1;i=n;i++) //构建初始序列 enQueue(q,i); printf("报数出列顺序:"); while (!QueueEmpty(q)) //队列不空时循环 {deQueue(q,e); //出队一个元素e printf("%d ",e); //输出元素的编号 if (!QueueEmpty(q)) //队列不空 {deQueue(q,e); //出队一个元素e enQueue(q,e); //将刚出队的元素进队 } } printf("\n"); DestroyQueue(q); //销毁队列q } 4) 设计求解程序 设计一个主函数调用上述算法: int main() {int i,n=8; printf("初始序列:"); for (i=1;i=n;i++) printf("%d ",i); printf("\n"); number(n); return 1; } 5) 运行结果 上述程序的运行结果如下: 初始序列: 1 2 3 4 5 6 7 8 报数出列顺序: 1 3 5 7 2 6 4 8 2. 求解迷宫问题 1) 问题描述 参见3.1.4节的问题描述。 2) 数据组织 用队列解决求迷宫路径问题。使用一个顺序队qu保存走过的方块,该队列的类型声明如下: typedef struct {int i,j;//方块的位置 int pre; //本路径中上一个方块在队列中的下标 } Box; //方块类型 typedef struct {Box data[MaxSize]; int front,rear; //队头指针和队尾指针 } QuType; //顺序队类型 这里使用的顺序队列qu不是环形队列,因为在找到出口时需要利用队列中的所有方块查找一条迷宫路径。如果采用环形队列,出队的方块可能被新进队的方块覆盖,从而无法求出迷宫路径。这里要求非环形队列qu有足够大的空间。 3) 设计运算算法 搜索从入口(xi,yi)到出口(xe,ye)路径的过程是,首先将入口(xi,yi)进队,在队列qu不为空时循环,出队一个方块e(由于不是环形队列,该出队方块不会被覆盖,其下标为front)。然后查找方块e的所有相邻可走方块,假设为e1和e2两个方块,将它们进队,它们在队列中的位置分别为rear1和rear2,并且将它们的pre均设置为front(因为在迷宫路径上e1和e2两个方块的前一个方块都是方块e),如图3.22所示。 图3.22设置相邻方块的pre 当找到出口时,通过出口方块的pre值前推找到出口,所有经过的中间方块构成一条迷宫路径。对应的过程如下: 将入口(xi,yi)的pre置为-1并进队; mg[xi][yi]=-1; while (队列qu不空) {出队一个方块e,其在队列中的位置是front; if (方块e是出口) {输出一条迷宫路径; return true; } for (对于方块e的所有相邻可走方块e1) {设置e1的pre为front; 将方块e1进队; 将方块e1的迷宫数组值设置为-1; } } return false;//没有迷宫路径,返回假 实际上,上述过程是从入口(xi,yi)开始,利用队列的特点,一层一层向外扩展查找可走的方块,直到找到出口为止,这个方法就是将在第8章中介绍的广度优先搜索方法。 在找到出口后,输出路径的过程是根据当前方块(即出口,其在队列qu中的下标为front)的pre值回推找到迷宫路径。对于如图3.11所示的迷宫,在找到出口后,队列qu中data的全部数据如表3.3所示。当前的front=40,qu->data[40].pre为35,表示路径上的前一个方块为qu->data[35]; 而qu->data[35].pre为30,表示路径上的上一个方块为qu->data[30]; qu->data[30].pre为27,表示路径上的前一个方块为qu->data[27],…,以此类推,找到入口为qu->data[0]。在对应的dispapath算法中,为了正向输出路径,先从qu->front开始回推出一条反向路径并存放在path数组中,再反向输出path中所有方块位置构成一条正向迷宫路径。 表3.3队列qu中data的全部数据 下标ijpre下标ijpre 011-1211618 1120226520 2210235522 3221247522 4312254523 5323265623 6414278524 7335284625 8516295726 9347308627 10528318427 11618324728 12249335829 135310346729 147111358730 151412368331 162512373732 176313384832 181515396833 192616408835 206417 根据上述搜索过程得到以下用队列求解迷宫的算法: bool mgpath1(int xi,int yi,int xe,int ye)//搜索路径为(xi,yi)(xe,ye) {Box e; int i,j,di,i1,j1; QuType *qu; //定义顺序队指针qu InitQueue(qu); //初始化队列qu e.i=xi; e.j=yi; e.pre=-1; enQueue(qu,e); //(xi,yi)进队 mg[xi][yi]=-1; //将其赋值-1,以避免回过来重复搜索 while (!QueueEmpty(qu)) //队不空时循环 {deQueue(qu,e); //出队方块e,非环形队列中元素e仍在队列中 i=e.i; j=e.j; if (i==xe && j==ye) //找到了出口,输出路径 {dispapath(qu,qufront); //调用dispapath函数输出路径 DestroyQueue(qu); //销毁队列 return true; //找到一条路径时返回真 } for (di=0;di4;di++) //循环遍历每个方位,把每个相邻可走的方块进队 {switch(di) { case 0:i1=i-1; j1=j; break; case 1:i1=i; j1=j+1; break; case 2:i1=i+1; j1=j; break; case 3:i1=i; j1=j-1; break; } if (mg[i1][j1]==0) {e.i=i1; e.j=j1; e.pre=qufront; //指向路径中上一个方块的下标 enQueue(qu,e); //(i1,j1)方块进队 mg[i1][j1]=-1; //将其赋值-1,以避免回过来重复搜索 } } } DestroyQueue(qu); //销毁队列 return false; //未找到任何路径时返回假 } void dispapath(QuType *qu,int front) //从队列qu中找到一条迷宫路径并输出 {Box path[MaxSize]; int p=front,k=0,i; while(p!=-1) //搜索反向路径path[0..k-1] {path[k++]=qu->data[p]; p=qu->data[p].pre; } printf("一条迷宫路径如下:\n"); for(i=k-1;i>=0;i--) //反向输出path构成正向路径 {printf("\t(%d,%d)",path[i].i,path[i].j); if ((k-i)%5==0) printf("\n"); //每输出5个方块后换一行 } printf("\n"); } 4) 设计求解程序 建立以下主函数调用上述算法: int main() {if (!mgpath1(1,1,M,N)) printf("该迷宫问题没有解!"); return 1; } 5) 运行结果 对于如图3.10所示的迷宫,求解结果如下: 一条迷宫路径如下: (1,1)(2,1)(3,1)(4,1)(5,1) (5,2)(5,3)(6,3)(6,4)(6,5) (7,5)(8,5)(8,6)(8,7)(8,8) 上述迷宫路径的显示结果如图3.23所示,图中路径上方块(i,j)中的箭头指向路径的前一个相邻方块,例如方块(2,1)的箭头是“↑”,表示路径上的前一个方块是方块(1,1),即出口。显然这个解是最优解,也就是最短路径。 图3.23用队列求解的迷宫路径 3.2.5双端队列 所谓双端队列(deque,doubleended queue)是指两端都可以进行进队和出队操作的队列,如图3.24所示。将队列的两端分别称为前端和后端,两端都可以进队和出队。其元素的逻辑关系仍是线性关系。 图3.24一个双端队列 在双端队列中进队时,从前端进的元素排列在队列中从后端进的元素的前面,从后端进的元素排列在队列中从前端进的元素的后面。在双端队列中出队时,无论是从前端出还是从后端出,先出的元素都排列在后出的元素的前面。 例如,4个不同字符a、b、c、d作为输入序列,通过一个双端队列可以产生24个输出序列,即可以得到所有的全排列。那么是不是任何n个不同字符作为输入序列,通过一个双端队列都可以产生所有的全排列呢?答案是否定的,例如5个不同字符a、b、c、d、e作为输入序列,通过一个双端队列可以产生116种排列而不是5!个排列,其中不能够得到eacbd和ebcda等输出序列。 实际上,从前面的双端队列可以看出,从后端进前端出或者从前端进后端出体现先进先出的特点,从前端进前端出或从后端进后端出体现出后进先出的特点。 在实际使用中,还可以有输出受限的双端队列(即允许两端进队,但只允许一端出队的双端队列)和输入受限的双端队列(即允许两端出队,但只允许一端进队的双端队列),前者如图3.25所示,后者如图3.26所示。如果限定双端队列中从某端进队的元素只能从该端出队,则该双端队列就蜕变为两个栈底相邻的栈了。 图3.25一个输出受限的双端队列 图3.26一个输入受限的双端队列 【例3.9】某队列允许在两端进行入队操作,但仅允许在一端进行出队操作,若a、b、c、d、e元素进队,则以下不可能得到的顺序有哪些? (1) bacde(2) dbace(3) dbcae(4) ecbad 解本题的队列实际上是一个输出受限的双端队列,这样的双端队列如图3.25所示。 (1) a后端进,b前端进,c后端进,d后端进,e后端进,全出队。 (2) a后端进,b前端进,c后端进,d前端进,e后端进,全出队。 (3) a后端进,b前端进,因d未出,此时只能进队,c怎么进都不可能在b、a之间。 (4) a后端进,b前端进,c前端进,d后端进,e前端进,全出队。 所以不可能得到的顺序为(3)。 【例3.10】如果允许在环形队列的两端进行插入和删除操作(这样的队列即为双端队列),若仍采用前面定义的SqQueue队列类型,设计“从队尾删除”和“从队头插入”的算法。 解从前面介绍的环形队列结构可以看到,队头指针front指向队列中队首元素的前一个位置,而队尾指针rear指向队列中的队尾元素。所以“从队尾删除”运算应先提取队尾元素,再循环后退一个位置,而“从队头插入”运算应先在队头插入元素,再循环后退一个位置。 实现“从队尾删除”运算的算法如下: bool deQueue1(SqQueue *&q,ElemType &e)//从队尾删除算法 {if (qfront==qrear) //队空返回假 return false; e=qdata[qrear]; //提取队尾元素 qrear=(qrear-1+MaxSize)%MaxSize; //修改除尾指针 return true; } 实现“从队头插入”运算的算法如下: bool enQueue1(SqQueue *&q,ElemType e)//从队头插入算法 {if ((qrear+1)%MaxSize==qfront) //队满返回假 return false; qdata[qfront]=e; //元素e进队 qfront=(qfront-1+MaxSize)%MaxSize; //修改队头指针 return true; } 本 章 小 结 本章的基本学习要点如下: (1) 理解栈和队列的特性以及它们之间的差异。 (2) 掌握栈的两种存储结构(即顺序栈和链栈)的设计特点,注意顺序栈和链栈中栈满和栈空的条件判断。 (3) 掌握在顺序栈和链栈中实现栈的基本运算的算法设计方法。 (4) 掌握队列的两种存储结构(即顺序队和链队)的设计特点,以及环形队列和非环形队列的差异,注意各种存储结构中队满和队空的条件判断。 (5) 掌握在顺序队和链队中实现队列的基本运算的算法设计方法。 (6) 理解栈和队列的作用,知道在何时使用哪一种数据结构,用栈和队列求解迷宫问题的差异。 (7) 灵活地运用栈和队列两种数据结构解决一些综合应用问题。 练习题3 1. 有5个元素,其进栈次序为ABCDE,在各种可能的出栈次序中以元素C、D最先出栈(即C第一个且D第二个出栈)的次序有哪几个? 2. 在一个算法中需要建立多个栈(假设3个栈或以上)时可以选用以下3种方案之一,试问这些方案各有什么优缺点? (1) 分别用多个顺序存储空间建立多个独立的顺序栈。 (2) 多个栈共享一个顺序存储空间。 (3) 分别建立多个独立的链栈。 3. 在以下几种存储结构中哪种最适合用作链栈? (1) 带头结点的单链表。 (2) 不带头结点的循环单链表。 (3) 带头结点的双链表。 4. 简述以下算法的功能(假设ElemType为int类型)。 void fun(ElemType a[],int n) {int i; ElemType e; SqStack *st1,*st2; InitStack(st1); InitStack(st2); for (i=0;in;i++) if (a[i]%2==1) Push(st1,a[i]); else Push(st2,a[i]); i=0; while (!StackEmpty(st1)) {Pop(st1,e); a[i++]=e; } while (!StackEmpty(st2)) {Pop(st2,e); a[i++]=e; } DestroyStack(st1); DestroyStack(st2); } 5. 简述以下算法的功能(顺序栈的元素类型为ElemType)。 void fun(SqStack *&st,ElemType x) {SqStack *tmps; ElemType e; InitStack(tmps); while(!StackEmpty(st)) {Pop(st,e); if(e!=x) Push(tmps,e); } while (!StackEmpty(tmps)) {Pop(tmps,e); Push(st,e); } DestroyStack(tmps); } 6. 简述以下算法的功能(队列qu的元素类型为ElemType)。 bool fun(SqQueue *&qu,int i) {ElemType e; int j; int n=(qurear-qufront+MaxSize)%MaxSize; if (i1 ‖ in) return false; for (j=1;j=n;j++) {deQueue(qu,e); if (j!=i) enQueue(qu,e); } return true; } 7. 什么是环形队列?采用什么方法实现环形队列? 8. 环形队列一定优于非环形队列吗?在什么情况下使用非环形队列? 9. 假设以I和O分别表示进栈和出栈操作,栈的初态和终态均为空,进栈和出栈的操作序列可表示为仅由I和O组成的序列。 (1) 在下面的序列中哪些是合法的? A. IOIIOIOOB. IOOIOIIOC. IIIOIOIOD. IIIOOIOO (2) 通过对(1)的分析,设计一个算法判断所给的操作序列是否合法,若合法返回真,否则返回假(假设被判断的操作序列已存入一维数组中)。 10. 假设表达式中允许包含圆括号、方括号和大括号3种括号,编写一个算法判断表达式中的括号是否正确配对。 11. 设从键盘输入一个序列的字符a1,a2,…,an。设计一个算法实现这样的功能: 若ai为数字字符,ai进队; 若ai为小写字母,将队首元素出队; 若ai为其他字符,表示输入结束。要求使用环形队列。 12. 设计一个算法,将一个环形队列(容量为n,元素的下标从0到n-1)中的元素倒置。例如,图3.27(a)中为倒置前的队列(n=10),图3.27(b)中为倒置后的队列。 图3.27一个环形队列倒置前后的状态 13. 编写一个程序,输入n(由用户输入)个10以内的数,每输入i(0≤i≤9)就把它插到第i号队列中,最后把10个队中的非空队列按队列号从小到大的顺序串接成一条链,并输出该链中的所有元素。 上机实验题3 验证性实验 实验题1: 实现顺序栈的各种基本运算的算法 目的: 领会顺序栈的存储结构和掌握顺序栈中各种基本运算算法的设计。 内容: 编写一个程序sqstack.cpp,实现顺序栈(假设栈中的元素类型ElemType为char)的各种基本运算,并在此基础上设计一个程序exp31.cpp完成以下功能。 (1) 初始化栈s。 (2) 判断栈s是否非空。 (3) 依次进栈元素a、b、c、d、e。 (4) 判断栈s是否非空。 (5) 输出出栈序列。 (6) 判断栈s是否非空。 (7) 释放栈。 实验题2: 实现链栈的各种基本运算的算法 目的: 领会链栈的存储结构和掌握链栈中各种基本运算算法的设计。 内容: 编写一个程序listack.cpp,实现链栈(假设栈中的元素类型ElemType为char)的各种基本运算,并在此基础上设计一个程序exp32.cpp完成以下功能。 (1) 初始化栈s。 (2) 判断栈s是否非空。 (3) 依次进栈元素a、b、c、d、e。 (4) 判断栈s是否非空。 (5) 输出出栈序列。 (6) 判断栈s是否非空。 (7) 释放栈。 实验题3: 实现环形队列的各种基本运算的算法 目的: 领会环形队列的存储结构和掌握环形队列中各种基本运算算法的设计。 内容: 编写一个程序sqqueue.cpp,实现环形队列(假设栈中的元素类型ElemType为char)的各种基本运算,并在此基础上设计一个程序exp33.cpp完成以下功能。 (1) 初始化队列q。 (2) 判断队列q是否非空。 (3) 依次进队元素a、b、c。 (4) 出队一个元素,输出该元素。 (5) 依次进队元素d、e、f。 (6) 输出出队序列。 (7) 释放队列。 实验题4: 实现链队的各种基本运算的算法 目的: 领会链队的存储结构和掌握链队中各种基本运算算法的设计。 内容: 编写一个程序liqueue.cpp,实现链队(假设栈中的元素类型ElemType为char)的各种基本运算,并在此基础上设计一个程序exp34.cpp完成以下功能。 (1) 初始化链队q。 (2) 判断链队q是否非空。 (3) 依次进链队元素a、b、c。 (4) 出队一个元素,输出该元素。 (5) 依次进链队元素d、e、f。 (6) 输出出队序列。 (7) 释放链队。 设计性实验 实验题5: 用栈求解迷宫问题的所有路径及最短路径 目的: 掌握栈在求解迷宫问题中的应用。 内容: 编写一个程序exp35.cpp,改进3.1.4节的求解迷宫问题程序,要求输出如图3.28所示的迷宫的所有路径,并求第一条最短路径及其长度。 图3.28迷宫示意图 实验题6: 编写病人看病模拟程序 目的: 掌握队列应用的算法设计。 内容: 编写一个程序exp36.cpp,反映病人到医院排队看医生的情况。在病人排队过程中主要重复下面两件事。 (1) 病人到达诊室,将病历本交给护士,排到等待队列中候诊。 (2) 护士从等待队列中取出下一位病人的病历,该病人进入诊室就诊。 要求模拟病人等待就诊这一过程。程序采用菜单方式,其选项及功能说明如下。 1: 排队——输入排队病人的病历号,加入病人排队队列中。 2: 就诊——病人排队队列中最前面的病人就诊,并将其从队列中删除。 3: 查看排队——从队首到队尾列出所有排队病人的病历号。 4: 不再排队,余下依次就诊——从队首到队尾列出所有排队病人的病历号,并退出运行。 5: 下班——退出运行。 实验题7: 求解栈元素排序问题 图3.29八皇后问题 目的: 掌握栈应用的算法设计。 内容: 编写一个程序exp37.cpp,按升序对一个字符栈进行排序,即最小元素位于栈顶,注意最多只能使用一个额外的栈存放临时数据,并输出栈排序的过程。 综合性实验 实验题8: 用栈求解n皇后问题 目的: 深入掌握栈应用的算法设计。 内容: 编写一个程序exp38.cpp求解n皇后问题,即在n×n的方格棋盘上放置n个皇后,要求每个皇后不同行、不同列、不同左右对角线。图3.29所示为八皇后问题的一个解。在本实验中,皇后个数n由用户输入,其值不能超过20,输出所有的解; 采用类似于用栈求解迷宫问题的方法。 实验题9: 编写停车场管理程序 目的: 深入掌握栈和队列应用的算法设计。 内容: 编写满足以下要求的停车场管理程序exp39.cpp。设停车场内只有一个可停放n辆汽车的狭长通道,且只有一个大门可供汽车进出。 汽车在停车场内按车辆到达时间的先后顺序依次由南向北排列(大门在最北端,最先到达的第一辆车停放在停车场的最南端),若停车场内已停满n辆车,则后来的汽车只能在门外的便道(即候车场)上等候,一旦有车开走,则排在便道上的第一辆车即可开入; 当停车场内的某辆车要离开时,在它之后进入的车辆必须先退出停车场为它让路,待该辆车开出大门外,其他车辆再按原次序进入停车场,每辆停放在停车场的车在它离开停车场时必须按停留的时间长短交纳费用。整个停车场的示意图如图3.30所示。 图3.30停车场示意图 LeetCode在线编程题3 1. LeetCode1381——设计一个支持增量操作的栈★★ 2. LeetCode155——最小栈★ 3. LeetCode20——有效的括号★ 4. LeetCode1249——移除无效的括号★★ 5. LeetCode946——验证栈序列★★ 6. LeetCode1441——用栈操作构建数组★ 7. LeetCode150——逆波兰表达式求值★★ 8. LeetCode227——基本计算器Ⅱ★★ 9. LeetCode224——基本计算器★★★ 10. LeetCode622——设计循环队列★★ 11. LeetCode641——设计循环双端队列★★ 12. LeetCode225——用队列实现栈★ 13. LeetCode232——用栈实现队列★