数据结构-第三章-栈和队列.ppt

《数据结构-第三章-栈和队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章栈和队列3.1栈3.1.1抽象数据类型栈的定义3.1.2栈的表示和实现3.2栈的应用举例3.2.1数制转换3.2.2括号匹配的检验3.2.4行编辑程序3.2.5迷宫求解3.2.5表达式求值3.1.1栈3.1.1栈的定义及基本运算栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。假设栈S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，…an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈

2、的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。栈是限定仅能在表尾一端进行插入、删除操作的线性表（a1,a2,...,ai-1,ai,ai+1,…,an）插入删除什么是栈一、栈的定义进行插入和删除的一端是浮动端，通常被称为栈顶，并用一个“栈顶指针”指示；而另一端是固定端，通常被称为栈底。通常将栈用下图的形式描述：1）限定在线性表的一端进行插入。2）限定在线性表的一端进行删除。3）后进先出（LastInFirstOut），简称为LIFO线性表。第一个进栈的元素在栈底，最后一个进栈的元素在栈顶，第一个出栈的元素为栈顶元素，最后一个出

3、栈的元素为栈底元素。不含元素的栈称为空栈。出栈Pop进栈Push栈顶栈底topbottom空栈topbottoman...a2a1bottomtopbottomtopAABCDEAB栈操作图示A进栈BCDE进栈EDC出栈CDEtoptoptop栈的特点后进先出LIFO入栈与出栈topbottomtopbottomtoptoptop栈的表示和实现顺序栈：栈的顺序存储结构，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，指针top指向栈顶元素在顺序栈中的下一个位置，base为栈底指针，指向栈底的位置。base空栈a进栈b进栈aabtopbase

4、topbasetoptoptopabcdee进栈abcdef进栈溢出abde出栈cbasebasebasetop思考：假设有A,B,C三个元素进S栈的顺序是A,B,C，写出所有可能的出栈序列。CBAACBABCCABBACBCA如果是4个元素，那么它不可能的出栈序列有哪些？可能的出栈序列：12431324134221342143231424313241321434214321不可能出现的出栈序列：2413312434124123423142134312栈的数学性质若已知栈的输入序列为1,2,3…n,则输出序列有1/(n+1)*种.如：若输入序列为1,

5、2,3,4,则输出序列有14种。以1为头：12341243132413421432以2为头：21342143231423412431以3为头：321432413421以4为头：4321四．写出下列程序段的输出结果（栈的元素类型SElemType为char）（8分）Voidmain(){StackS;charx,y;InitStack(S);x=’c’;y=’k’;Push(S,x);Push(S,’a’);Push(S,y);Pop(S,x);Push(S,’t’);Push(S,x);Pop(S,x);Push(S,’s’);while(!

6、StackEmpty(S)){Pop(S,y);printf(y);};printf(x);}简述以下算法的功能Algo1(StackS){inti,n=0,A[255];While(!StackEmpty(S)){n++;pop(S,A[n]);}For(i=1;i<=n;i++)push(S,A[i]);}Algo2(StackS,inte){StackT;intd;Initstack(T);While(!stackEmpty(S)){pop(s,d);if(d!=e)push(T,d);}While(!stackEmpty(T)){pop(T,

7、d);push(S,d);}}3.1.2顺序栈由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top。例、一叠书或一叠盘子。栈的抽象数据类型的定义如下：anan-1a2a1……栈顶栈底顺序栈的类型表示:#defineSTACK_INIT_SIZE100；#defineSTACKINCREMENT10；typedefcharSElem

8、type;typedefstruct{//顺序栈定义SElemtype*base;//栈底指针SElemty