资源描述：
《数据结构（牛小飞）5 栈ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、栈模型栈(Stack)小结和作业栈的应用复习栈的链式实现栈的数组实现复习-线性表的逻辑结构D＝{a1,a2,…,ai,an}R＝{
2、ai-1,ai∈D,i=2,...,n}复习-顺序线性表a0a1a2L.theItemsL.theSizepublicclassMyArrayList>{privateAnyType[]theItems;//存储空间基址privateinttheSize;//表的大小privatestaticfinalintDEFAULT_CAPACIT
3、Y=10;//数组容量……成员方法}复习-单链表privatestaticclassNode{publicAnyTypedata;publicNodenext;……成员方法；}a0a1a2La0a1a2L复习-双向链表a2a3a1La2a3a1L复习-线性表的基本操作1、取出第i个数据元素的值2、插入或删除第i个数据元素3、第1个和最后1个数据元素往往是注意的焦点栈模型栈是线性表的特例。栈(stack)是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈顶(top)。(a1,a2,a3,……,an-1,an)表头(
4、栈底)表尾(栈顶)栈模型栈的基本操作：push(进栈)：pop(出栈)：插入操作删除最后插入的元素(a1,a2,a3,……,an-1,an)表头表尾栈模型stackpushpoptop栈模型：通过push向栈输入，通过pop和top从栈中输出41362top栈模型：只有栈顶元素可以访问将n个数a1,a2…,an-1,an按照下标的次序进栈，然后再出栈()(a1)(a1,a2)(a1,a2,a3)(a1,a2,a3,…)(a1,a2,a3,…an-1)(a1,a2,a3,…an-1,an)压栈过程出栈过程()(a1)(a1,a2)(a1,a2,a3)(a1,a2,a
5、3,…)(a1,a2,a3,…an-1)(a1,a2,a3,…an-1,an)anan-1a1a2a3……所以，栈又叫做先进后出(LastInFirstOut)表。栈模型练习1、有６个元素按照6,5,4,3,2,1的顺序进栈，问下列哪一个不是合法的出栈序列: A)5,4,3,6,2,1B)4,5,3,1,2,6 C)3,4,6,5,2,1D)2,3,4,1,5,62.一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列：A、1，3，2，4B、2，3，4，1C、4，3，1，2D、3，4，2，1栈的数组实现a0a1a2L.theItemsL.the
6、Sizea0a1a2topOfStack栈顶栈的逻辑形态空栈：topOfStack=-1topOfStacka0a1a2a3栈的数组实现topOfStack栈的逻辑形态对每一个栈的数据结构，用一个数组theArray以及栈顶位置topOfStack来描述。A进栈栈的数组实现栈的基本操作：进栈，出栈topOfStacktopOfStackBtopOfStackCtopOfStack出栈EDCBAtopOfStacktopOfStacktopOfStack栈的数组实现publicclassArrayStack{privateAnyType[]theA
7、rray;//存储空间基址privateinttopOfStack;//栈顶privatestaticfinalintDEFAULT_CAPACITY=10;//数组容量成员方法：}构造函数isEmptypushpopjava语言描述：ArrayStack原形：ArrayStack()作用：形成一个空栈publicArrayStack(){//空栈初始化ensureCapacity(DEFAULT_CAPACITY);topOfStack=-1;}topOfStackisEmptyboolisEmpty(){//reterntopOfStack==-1;}原形：b
8、ooleanisEmpty()作用：测试栈中是否有数据元素if(topOfStack==-1)returntrue;returnfalse;pop原形：publicAnyTypepop()作用：将栈顶的数据元素从栈中删除，并将其值赋给变量popVal。ABtopOfStack过程:popVal=B=theArray[topOfStack]topOfStackpoppublicAnyTypepop()throwsStackEmptyException{}if(isEmpty())thrownewStackEmptyException("Stackpop");AnyT
9、ypepo
