数据结构栈和队列.ppt

第三章栈和队列3.1栈3.2栈的应用举例3.3队列•栈和队列是两种重要的线性结构。•从数据结构角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是操作受限的线性表。•从数据类型角度看，它们是和线性表大不相同的两类重要的抽象数据类型。•由于它们广泛应用在各种软件系统中，因此在面向对象的程序设计中，它们是多型数据类型。多型数据类型：指其值的成分不确定的数据类型。从抽象数据类型角度看，具有相同的数学抽象特性，故称之为多型数据类型，需要借助面向对象程序设计语言，如C++等实现。3.1栈3.1.1抽象数据类型栈的定义•栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。•当表中没有元素时称为空栈。•假设栈S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，…an的次序进栈，退栈的第一个元素应为栈顶元素。•换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。•假设栈S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，…an的次序进栈，退栈的第一个元素应为栈顶元素，次序却是an，an-1，…，a1。•栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO），也可称为先进后出（FILO）。a1topbottoman....进栈出栈栈的示意图栈的基本操作演示3.1.2栈的表示和实现•由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。•栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。•因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top（栈顶指针），指示栈顶元素在顺序栈中的位置。顺序栈：栈的顺序存储结构，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，指针top指向栈顶元素在顺序栈中的下一个位置，base为栈底指针，指向栈底的位置。base空栈topa进栈abasetopb进栈abbasetoptopabcdee进栈basetopabcdef进栈溢出baseabde出栈cbasetop•空栈的通常表示方法是：top=0；•鉴于C语言中数组的下标约定从0开始，则当以C做描述语言时，如此设置会带来很大的不便；•另一方面，由于栈在使用过程中所需最大空间的大小很难估计，因此，一般来说，在初始化设空栈时不应限定栈的最大容量。•一个较合理的做法是：–先为栈分配一个基本容量；–然后在应用过程中，当栈的空间不够使用时在逐段扩大；–为此，需要设定两个常量：STACK_INIT_SIZE（存储空间初始分配量）和STACKINCREMENT（存储空间分配增量）。比较合理的顺序栈的定义Typedefstruct{StackData*base;//栈底指针StackData*top;//栈顶指针intstacksize;//当前栈可使用的最大容量}SeqStack;•栈的初始化操作：按设定的初始分配量进行第一次存储分配；•base为栈底指针，在顺序栈中始终指向栈底的位置；如果base的值为NULL，则表明栈结构不存在。•top为栈顶指针，其初值指向栈底：即top=base可作为栈空的标记，同时每当插入新的栈顶元素时，指针top增1；删除栈顶元素时，指针top减1；•非空栈中的栈顶指针始终在栈顶元素的下一位置上。•每当插入新的栈顶元素时，指针top增1；删除栈顶元素时，指针top减1。如图，顺序栈中数据元素和栈顶指针之间的对应关系。•非空栈中的栈顶指针始终在栈顶元素的下一个位置上。顺序栈的演示•顺序栈实现：一维数组s[M]top=0123450栈空栈顶指针top，指向实际栈顶后的空位置，初值为0top123450进栈Atop出栈栈满BCDEF设数组维数为Mtop=0，栈空，此时出栈，则下溢（underflow)top=M，栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空#defineSTACK_INIT_SIZE100；#defineSTACKINCREMENT10；typedefcharStackData;typedefstruct{//顺序栈定义StackData*base;//栈底指针StackData*top;//栈顶指针intstacksize；//当前已分配的全部存储空间}SeqStack；•初始化voidInitStack(SeqStack*S){//置空栈S-base=(StackData*)malloc(STACK_INIT_SIZE*sizeof(StackData));if(!S-base)exit(OVERFLOW);//存储空间分配失败S-top=S-base;S-stacksize=STACK_INIT_SIZE;returnok;}base空栈top顺序栈的基本运算•判栈空intStackEmpty(SeqStack*S){if(S-top==S-base)return1//判栈空,空则返回1elsereturn0;}//否则返回0base空栈top•判栈满intStackFull(SeqStack*S){if(S-top-S-base=S-StackSize)return1//判栈满,满则返回1elsereturn0;}//否则返回0topabcde栈满base•设S是SeqStack类型的指针变量。•若栈底位置在向量的底端，即s–data[0]是栈底元素，那么栈顶指针s–top是正向增加的，即进栈时需将s–top加1，退栈时需将s–top减1。•当栈满时再做进栈运算必定产生空间溢出，简称“上溢”；当栈空时再做退栈运算也将产生溢出，简称“下溢”。•上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。•入栈intPush(SeqStack*S,StackDatax){//插入元素x为新的栈顶元素if(StackFull(S)){//栈满，追加存储空间S-base=(StackData*)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(StackData));if(!S-base)exit(overflow);//存储分配失败S-top=S-base+S-stacksize;S-stacksize+=STACKINCREMENT;}//追加存储空间*(S-top)=x;（S-top）++;Returnok//入栈成功}Abasebasetoptop•出栈intPop(SeqStack*S,StackData&x){//若栈空返回0,否则栈顶元素退出到x并返回1if(StackEmpty(S))return0;--(S-top);x=*(S-top);return1;}EDCBABAbasebasetoptop•取栈顶元素intGetTop(SeqStack*S,StackData&x){//若栈空返回0,否则栈顶元素读到x并返回1if(StackEmpty(S))return0;x=*(S-top-1);return1;}BAbasetop链式栈：栈的链式表示•链式栈无栈满问题，空间可扩充；•插入与删除仅在栈顶处执行；•链式栈的栈顶在链头；•适合于多栈操作；top由于栈的操作是线性表操作的特例，则链栈的操作易于实现，它是运算受限的单链表。•链栈的类型定义如下：typedefstructnode{Elemtypedata;//数据域structnode*next;//指针域}ListNode;typedefListNode*LinkStack;LinkStacktop;//定义一个栈的栈顶指针变量top为栈顶指针，它唯一地确定一个栈。空栈时top==NULL。由于链栈是动态分配结点的空间，所以操作时无需考虑上溢出问题。链栈的插入、删除等运算的操作方法与单链表操作相似，也是通过修改指针进行的，只是链栈是限定在栈顶操作而已。•链式栈(LinkStack)的定义typedefintStackData;typedefstructnode{StackDatadata;//结点structnode*link;//链指针}StackNode;typedefstruct{StackNode*top;//栈顶指针}LinkStack;top链式栈操作实现•初始化voidInitStack(LinkStack*S){S-top=NULL;}•入栈intPush(LinkStack*S,StackDatax){StackNode*p=(StackNode*)malloc(sizeof(StackNode));p-data=x;p-link=S-top;S-top=p;return1;}toptop•判栈空intStackEmpty(LinkStack*S){returnS-top==NULL;}•出栈intPop(LinkStack*S,StackData&x){if(StackEmpty(S))return0;StackNode*p=S-top;S-top=p-link;x=p-data;free(p);return1;}toptop•取栈顶intGetTop(LinkStack*S,StackData&x){if(StackEmpty(S))return0;x=S-top-data;return1;}•置栈空intMakeEmpty(LinkStack*S){While(S-top!=NULL){StackNode*p=S-top;S-top=S-top-link;free(p);}}链栈的基本操作演示3.2栈的应用举例•由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈应用的例子：1.数制转换；2.括号匹配的检验；3.行编辑程序；4.表达式求值；5.递归实现。•数制转换：十进制数转换为八进制数。采用对十进制数除8取余的方法，可得到八进制数的倒序。N=(Ndivd)×d+Nmodd•例如：（1348)10=(2504)8，其运算过程如下：NNdiv8Nmod8134816841682102125202计算顺序输出顺序1.数制转换•假设现要编制一个满足下列要求的程序：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。•由于上述计算过程是从低位到高位顺序产生八进制数的各个数位，而打印输出，一般来说应从高位到低位进行，恰好和计算过程相反。因此，若将计算过程中得到的八进制数的各位顺序进栈，则按出栈序列打印输出的即为与输入对应的八进制数。NNdiv8Nmod8134816841682102125202计算顺序输出顺序voidconversion(){//对于输入的任意一个非负十进制整数，打印出与其等值的八进制数initstack(s);//初始化栈。scanf(“%”,n);//从键盘读入需要从转换的数N。while(n){push(s,n%8);//将余数入栈。n=n/8;//数n进行除8操作，考虑八进制数的下一个位数。}while(!Stackempty(s)){pop(s,e);printf(“%d”,e);//栈中的数依次出栈。}}//conversion算法3.1数制转换的演示2.行编辑程序•在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。•设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区;并假设“#”为退格符，“@”为退行符。假设从终端接受两行字符：whli##ilr#