堆栈和队列-资料

第3章限定性线性表——堆栈和队列3.1堆栈3.2堆栈应用3.4*优先级队列栈和队列是两种重要的抽象数据类型，是一类操作受限制的特殊线性表，其特殊性在于限制插入和删除等运算的位置。3.3队列第2页3.1堆栈3.1.1堆栈的基本概念堆栈的定义：限定只能在固定一端进行插入和删除操作的线性表。通常将表中允许进行插入、删除操作的一端称为栈顶(Top)，表的另一端被称为栈底(Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。栈又称为后进先出的线性表，即LIFO。第3页根据栈定义，每次进栈的元素都被放在原栈顶元素之上而成为新的栈顶，而每次出栈的总是当前栈中“最新”的元素，即最后进栈的元素。因此，栈又称为后进先出的线性表。简称为LIFO表。如下图所示：进栈、出栈图例进栈出栈ana2a1进栈出栈栈顶栈底第4页例3-1利用一个堆栈，如果输入系列由A、B、C组成，试给出全部可能的输出系列和不可能的输出系列。输出系列有：ABC、ACB、BAC、BCA、CBA不可能的输出系列为：CAB第5页3.1.2栈的抽象数据类型定义数据元素集合：描述为{a0,a1,…,an-1}，ai的数据类型为DataType。关系：栈中数据元素之间是线性关系。基本操作：(1)Initiate(S)初始化堆栈S(2)Push(S,x)入栈(3)Pop(S,d)出栈(4)GetTop(S)取栈顶数据元素(5)NotEmpty(S)堆栈S非空否第6页3.1.3栈的表示和实现——顺序堆栈类栈在计算机中主要有两种基本的存储结构：顺序存储结构和链式存储结构。顺序存储的栈为顺序栈；链式存储的栈为链栈。第7页1.顺序堆栈的存储结构顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必须附设一个位置指针top（栈顶指针）来动态地指示栈顶元素在顺序栈中的位置。通常以top=0表示空栈。其结构如图所示：a0a1a2a3a4stack栈底栈顶MaxStackSize-1012345=top其中，a0,a1,a2,a3,a4表示顺序堆栈中已存储的数据元素，stack表示存放数据元素的数组，MaxStackSize-1表示最大存储单元个数，top表示当前栈顶存储下标。第8页classSeqStack{private:DataTypedata[MaxStackSize];//顺序堆栈数组inttop;//栈顶位置指示器public:SeqStack(void){top=0;}//构造函数~SeqStack(void){}//析构函数voidPush(constDataTypeitem);//入栈DataTypePop(void);//出栈DataTypeGetTop(void)const;//取栈顶数据元素intNotEmpty(void)const//堆栈非空否{return(top!=0);}};2.顺序堆栈类的定义和实现第9页voidSeqStack::Push(constDataTypeitem)//入栈//把元素item入栈;堆栈满时出错退出{if(top==MaxStackSize){cout堆栈已满!endl;exit(0);}data[top]=item;//先存储itemtop++;//然后top加1}第10页DataTypeSeqStack::Pop()//出栈//出栈并返回栈顶元素;堆栈空时出错退出{if(top==0){cout堆栈已空!endl;exit(0);}top--;//top先减1returndata[top];//然后取元素返回}第11页DataTypeSeqStack::GetTop(void)const//取栈顶数据元素//取当前栈顶数据元素并返回{if(top==0){cout堆栈空!endl;exit(0);}returndata[top-1];//返回当前栈顶元素}第12页测试主程序如下：#includeiostream.h#includestdlib.hconstintMaxStackSize=100;//定义问题要求的元素数目的最大值typedefintDataType;//定义具体问题元素的数据类型#includeseqstack.h3.顺序堆栈类的测试voidmain(void){SeqStackmyStack;//构造函数无参数时，定义的对象后不带括号DataTypetest[]={1,3,5,7,9};intn=5;for(inti=0;in;i++)myStack.Push(test[i]);while(myStack.NotEmpty())coutmyStack.Pop();}程序运行输出结果为：97531第13页3.1.4链式堆栈类1.链式堆栈链式存储结构的堆栈。2.链式栈的存储结构它是以头指针为栈顶，在头指针处插入或删除，其结构如图所示：头结点an-1an-2a0∧…h栈底栈顶链栈中每个结点由两个域构成：data域和next域，其结点类和类定义分别如下：templateclassTclassLinStack;//前视定义，否则友元无法定义第14页//结点类templateclassT//模板类型为TclassStackNode{friendclassLinStackT;//定义类LinStackT为友元private:Tdata;//数据元素StackNodeT*next;//指针public://构造函数1，用语构造头结点StackNode(StackNodeT*ptrNext=NULL){next=ptrNext;}//构造函数2，用于构造其他结点StackNode(constT&item,StackNodeT*ptrNext=NULL){data=item;next=ptrNext;}~StackNode(){};};第15页//链式堆栈类的定义templateclassTclassLinStack{private:StackNodeT*head;//头指针intsize;public://数据元素个数public:LinStack(void);//构造函数~LinStack(void);//析构函数voidPush(constT&item);//入栈TPop(void);//出栈TGetTop(void)const;//取栈顶元素intNotEmpty(void)const;//堆栈非空否};第16页templateclassTLinStackT::LinStack()//构造函数{head=newStackNodeT;//头指针指向头结点size=0;//size的初值为0}templateclassTLinStackT::~LinStack(void)//析构函数//释放所有动态申请的结点空间{StackNodeT*p,*q;p=head;//p指向头结点while(p!=NULL)//循环释放结点空间{q=p;p=p-next;deleteq;}}第17页templateclassTintLinStackT::NotEmpty(void)const//堆栈非空否{if(size!=0)return1;elsereturn0;}templateclassTvoidLinStackT::Push(constT&item)//入栈{//新结点newNode的data域值为item,next域值为head-nextStackNodeT*newNode=newStackNodeT(item,head-next);head-next=newNode;//新结点插入栈顶size++;//元素个数加1}第18页templateclassTTLinStackT::Pop(void)//出栈{if(size==0){cout堆栈已空无元素可删!endl;exit(0);}StackNodeT*p=head-next;//p指向栈顶元素结点Tdata=p-data;head-next=head-next-next;//原栈顶元素结点脱链deletep;//释放原栈顶结点空间size--;//结点个数减1returndata;//返回原栈顶结点的data域值}第19页templateclassTTLinStackT::GetTop(void)const//取栈顶元素{returnhead-next-data;}说明：1)在链栈中的头结点对操作的实现影响不大，栈顶（表头）操作频繁，可不设头结点链栈。2)一般不会出现栈满情况；除非没有空间导致malloc分配失败。3)链栈的入栈、出栈操作就是栈顶的插入与删除操作，修改指针即可完成。4)采用链栈存储方式的优点是，可使多个栈共享空间；当栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式。第20页3.2堆栈应用1、括号匹配问题例：假设一个算法表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个判别表达式中括号是否正确配对的函数。设计思路：用栈暂存左括号第21页voidExpIsCorrect(charexp[],intn)//判断有n个字符的字符串exp左右括号是否配对正确{SeqStackmyStack;//定义顺序堆栈类对象myStackinti;for(i=0;in;i++){if((exp[i]=='(')||(exp[i]=='[')||(exp[i]=='{'))myStack.Push(exp[i]);//入栈elseif(exp[i]==')'&&myStack.NotEmpty()&&myStack.GetTop()=='(')myStack.Pop();//出栈第22页elseif(exp[i]==')'&&myStack.NotEmpty()&&myStack.GetTop()!='('){cout左、右括号配对次序不正确!endl;return;}elseif(exp[i]==']'&&myStack.NotEmpty()&&myStack.GetTop()=='[')myStack.Pop();//出栈elseif(exp[i]==']'&&myStack.NotEmpty()&&myStack.GetTop()!='['){cout左、右括号配对次序不正确!endl;return;}第23页elseif(exp[i]=='}'&&myStack.NotEmpty()&&myStack.GetTop()=='{')myStack.Pop();//出栈elseif(exp[i]=='}'&&myStack.NotEmpty()&&myStack.GetTop()!='{'){cout左、右括号配对次序不正确!endl;return;}第24页elseif(((exp[i]==')')||(exp[i]==']')||(exp[i]=='}'))&&!myStack.NotEmpty()){cout右括号多于左括号!endl;return;}}if(myStack.NotEmpty())cout左括号多于右括号!endl;elsecout左、右括号匹配正确!endl;}第25页2、表达式计算问题表达式计算是编译系统中的基本问题，其实现方法是堆栈的一个典型应用。在编译系统中，要把便于人理解的表达式翻译成能正确求值的机器指令序列，通常需要先把表达式变换成机器便于理解的形式，这就要变换表达式的表示序列。假设计算机高级语言中的一个算术表达式为A+(B-C/D)*E这种表达式称为中缀表达式，写成满足四则运算规则的相应的后缀表达式即为ABCD/-E*+第26页表达式的三种标识方法：设Exp=S1+OP+S2则称OP+S1