文档介绍：第3章栈和队列本章主题:栈和队列的应用教学目的:掌握栈和队列的应用方法,理解栈的重要作用教学重点:利用栈实现行编辑,利用栈实现表达式求值教学难点:利用栈实现表达式求值栈,也叫堆栈,是最常用也是最重要的数据结构之一。比如编译器中的语法识别、数学表达式的处理、程序运行中的函数及过程的调用等,都要用到栈的有关特性。它们是栈应用于实际问题的典型。【课前思考】 ? 简单地说,线性结构是一个数据元素的序列。 ?如果它们是按1,2,…,n的次序往上叠的,那么使用时候的次序应是什么样的? 必然是依从上往下的次序,即n,…,2,1。它们遵循的是"后进先出"的规律,这正是本章要讨论的"栈"的结构特点。 ,为了维持正常的社会秩序而出现的常见现象是什么? 是"排队"。在计算机程序中,模拟排队的数据结构是"队列"。2019/6/,插入或删除栈元素的运算只能在表的一端进行,称运算的一端为栈顶,另一端称为栈底。特点:后进先出栈又称为“后进先出”的线性表,简称LIFO表。……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)2019/6/(S)设置一个空栈S。压栈Push(S,x)将元素x插入栈S中,使x成为栈S的栈顶元素。出栈Pop(S,x)当栈S不空时,由x返回栈顶元素,并从栈中删除栈顶元素取栈顶元素GetTop(S,x)若栈S不空,则由x返回栈顶元素。判栈空Empty(S)若栈S为空栈,结果为1,否则结果为0。2019/6/174例1:对于一个栈,给出输入项A、B、C,如果输入项序列由ABC组成,试给出所有可能的输出序列。A进A出B进B出C进C出ABCA进A出B进C进C出B出ACBA进B进B出A出C进C出BACA进B进B出C进C出A出BCAA进B进C进C出B出A出CBA不可能产生输出序列CAB2019/6/175例2:一个栈的输入序列是12345,若在入栈的过程中允许出栈,则栈的输出序列43512可能实现吗?12345的输出呢?43512不可能实现,主要是其中的12顺序不能实现;12345的输出可以实现,只需压入一个立即弹出一个即可。435612中到了12顺序不能实现;135426可以实现。例3:如果一个栈的输入序列为123456,能否得到435612和135426的出栈序列?答:答:2019/6/176例4:计算机系2001年考研题(程序设计基础)设依次进入一个栈的元素序列为c,a,b,d,则可得到出栈的元素序列是:A)a,b,c,dB)c,d,a,bC)b,c,d,aD)a,c,d,bA、D可以(B、C不行)。答:2019/6/:。通常由一个一维数组和一个记录栈顶元素位置的变量组成。2019/6/178ElemType为栈中元素的数据类型,可以根据需要而指定为某种具体的类型。data域:为一个一维数组,用于存储栈中元素。top域:栈顶指针。取值范围为0~MaxSize-1。top=-1表示栈空,top=MaxSize-1表示栈满。#defineMaxSize<存储数据元素的最大个数>typedefstruct{ElemTypedata[MaxSize];inttop;}STACK;顺序栈的C++语言描述如下:2019/6/179。顺序栈的几种状态(最大长度MaxSize为4)(a)当栈中没有数据元素时,表示为栈空。栈顶元素所对应的下标值top=-1。(b)表示在(a)基础上执行Push(S,‘A’)后得到这种状态。(c)又有三个元素B、C、D先后入栈,此时栈顶元素的下标值top=3。栈已满。(d)表示在(c)状态下,执行一次Pop(S,x)运算得到。(e)表示在(d)状态下,执行三次Pop(S,x)运算得到。此时栈顶下标值top=-l,又变成栈空状态2019/6/1710