栈与队列(java版)

数据结构(Java语言描述)第三章栈与队列数据结构（Java语言描述）第三章栈与队列章节目录作业布置结束放映教学内容3.2队列3.1栈3.4栈与队列的综合应用举例3.3栈与队列的比较数据结构（Java语言描述）第三章栈与队列章节目录作业布置结束放映教学重点与难点重点：栈、队列的特点；栈、队列基本操作的实现算法难点：栈、队列的应用数据结构（Java语言描述）第三章栈与队列章节目录作业布置结束放映通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。线性表栈队列Insert(i,x)Insert(n,x)Insert(n,x)0≤i≤nDelete(i)Delete(n-1)Delete(0)0≤i≤n-1栈和队列是两种操作受限的线性表，是两种常用的数据类型。数据结构（Java语言描述）3.1栈作业布置结束放映章节目录3.1.1栈的概念(1)栈是仅限制在表尾进行插入和删除操作的特殊线性表，限制操作的表尾端称为“栈顶”,另一端称为“栈底”a0a1a2…an-1栈底栈顶进出(2)栈是“后进先出”的线性表（LIFO）或“先进后出”的线性表（FILO）数据结构（Java语言描述）3.1栈作业布置结束放映章节目录3.1.1栈的概念如下图所示的是铁路调度站形象地表示栈的“后进先出”特点。数据结构（Java语言描述）3.1栈作业布置结束放映章节目录3.1.1栈的概念思考题：设有编号为1，2，3，4的四辆列车，顺序进一个栈式结构的站台，具体写出这四辆列车开出车站的所有可能的顺序。数据结构（Java语言描述）3.1栈作业布置结束放映章节目录3.1.1栈的概念解答：四辆车出站的所有可能顺序为：6）2、1、3、4；7）2、1、4、3；8）2、3、4、1；9）2、3、1、4；10）2、4、3、1；14）4、3、2、1。1）1、2、3、4；2）1、2、4、3；3）1、3、2、4；4）1、3、4、2；5）1、4、3、2；11）3、2、1、4；12）3、2、4、1；13）3、4、2、1；数据结构（Java语言描述）3.1栈作业布置结束放映章节目录3.1.2栈的抽象数据类型描述clear()1）栈的置空操作：isEmpty()2）栈的判空操作：length()3）求栈的长度：4）取栈顶元素操作：5）入栈操作：peek()push(x)6）出栈操作：pop()1.基本操作数据结构（Java语言描述）3.1栈作业布置结束放映章节目录3.1.2栈的抽象数据类型描述2.栈的抽象数据类型的Java接口描述publicinterfaceIStack{}publicvoidclear();publicbooleanisEmpty();publicintlength();publicObjectpeek();publicvoidpush(Objectx)throwsException;publicObjectpop();实现此接口的方法有两种:顺序栈链栈数据结构（Java语言描述）3.1栈作业布置结束放映章节目录3.1.3顺序栈及其基本操作的实现1.顺序栈非空栈空栈a0a1an-1……top=nstackElemmaxSize-101……n-1……top=0stackElemmaxSize-1012……数据结构（Java语言描述）3.1栈作业布置结束放映章节目录3.1.3顺序栈及其基本操作的实现1.顺序栈思考栈空条件?栈满条件?栈的长度?栈顶元素?如下问题如何描述?top==0top==stackElem.lengthtopstackElem[top-1]a0a1an-1……top=nstackElem01……n-1数据结构（Java语言描述）3.1栈作业布置结束放映章节目录3.1.3顺序栈及其基本操作的实现2.顺序栈类的描述(书P71-与P33顺序表类对照学习)publicclassSqStackimplementsIStack{privateObject[]stackElem;privateinttop;}//构造一个容量为maxSize的空栈publicSqStack(intmaxSize){}//栈置空publicvoidclear(){}……stackElem=newObject[maxSize];top=0;top=0;数据结构（Java语言描述）3.1栈作业布置结束放映章节目录2.顺序栈类的描述(见教材P71)publicclassSqStackimplementsIStack{}//栈判空publicbooleanisEmpty(){}//求栈数据元素个数函数publicintlength(){}…………//取栈顶元素的函数publicObjectpeek(){}returntop==0;returntop;if(!isEmpty())//栈非空returnstackElem[top-1];//栈顶元素elsereturnnull;数据结构（Java语言描述）3.1栈作业布置结束放映章节目录2.顺序栈类的描述(见教材P71)publicclassSqStackimplementsIStack{}//入栈操作的函数publicvoidpush(Objectx){……}……//出栈操作的函数publicvoidpop(){……}//输出函数(从栈顶到栈底)publicvoiddisplay(){}for(inti=top-1;i=0;i--)System.out.print(stackElem[i].toString()+);数据结构（Java语言描述）3.1栈作业布置结束放映章节目录3.顺序栈基本操作的实现1)顺序栈的入栈操作push(x)的实现（算法3.1)(1)操作要求：插入元素x使其成为顺序栈中新的栈顶元素。xa0a1an-1……toptop数据结构（Java语言描述）3.1栈作业布置结束放映章节目录a.[判断顺序栈是否为满，若满则抛出异常]b.[若栈不满，则将新元素x压入栈顶，并修正栈顶指针](2)算法步骤：if(top==stackElem.length)thrownewException(栈已满)1)顺序栈的入栈操作push(x)的实现（算法3.1)statckElem[top++]=xstatckElem[top]=x;top=top+1;数据结构（Java语言描述）3.1栈作业布置结束放映章节目录(3)算法publicvoidpush(Objectx)throwsException{}//算法3.1结束if(top==stackElem.length)thrownewException(栈已满);elsestackElem[top++]=x;1)顺序栈的入栈操作push(x)的实现（算法3.1)时间复杂度为：O(1)数据结构（Java语言描述）3.1栈作业布置结束放映章节目录3.顺序栈基本操作的实现2)顺序栈的出栈操作pop()的实现（算法3.2)(1)操作要求：将栈顶元素从栈中移去，并返回被移去的栈顶元素值。a0a1an-1……an-2top数据结构（Java语言描述）3.1栈作业布置结束放映章节目录(2)算法步骤：2)顺序栈的出栈操作pop()的实现（算法3.2)a）若栈空，则返回空值b)若栈不空，则移去栈顶元素并返回其值if(top==0)returnnull;a1a2an……an-1top或if(isEmpty())returnnull;returnstackElem[top];returnstackElem[--top];top=top-1;数据结构（Java语言描述）3.1栈作业布置结束放映章节目录(3)算法publicObjectpop()throwsException{}//算法3.2结束if(isEmpty())returnnull;elsereturnstackElem[--top];2)顺序栈的出栈操作pop()的实现（算法3.2)时间复杂度为：O(1)数据结构（Java语言描述）3.1栈作业布置结束放映章节目录3.1.4链栈及其基本操作的实现1.链栈栈的链式存储结构称为链栈，是运算受限的单链表，其插入和删除操作仅限制在链表的表头位置上进行，故链栈没有必要象单链表一样附加头结点，栈顶指针即为链表的头指针。top∧a0an-1注意:链栈中指针的方向an-2栈底数据结构（Java语言描述）3.1栈作业布置结束放映章节目录3.1.4链栈及其基本操作的实现1.链栈思考栈空条件?栈的长度?栈顶元素?如下问题如何描述?top==null需从栈顶开始沿着next指针依次对结点逐个进行点数才能确定。top.getData()top∧a0an-1an-2数据结构（Java语言描述）3.1栈作业布置结束放映章节目录3.1.4链栈及其基本操作的实现2.链栈类的描述(书中P73-74)Importcho2.Node;publicclassLinkStackimplementsIStack{privateNodetop;}//栈置空函数publicvoidclear(){}……//判空函数publicbooleanisEmpty(){}top=null;returntop==null;数据结构（Java语言描述）3.1栈作业布置结束放映章节目录2.链栈类的描述(书中P73-74)publicclassLinkStackimplementsIStack{}//求栈数据元素个数函数publicintlength(){……}…………//取栈顶元素的函数publicObjectpeek(){}if(!isEmpty())//栈非空returntop.getData();//栈顶元素elsereturnnull;数据结构（Java语言描述）3.1栈作业布置结束放映章节目录2.链栈类的描述(书中P73-74)publicclassLinkStackimplementsIStack{}//入栈操作的函数publicvoidpush(Objectx){……}……//出栈操作的函数publicvoidpop(){……}//输出函数(从栈顶到栈底)publicvoiddisplay(){}Nodep=top;System.out.print(p.getData().tostring()+)p=p.getNext();while(p!=null){}数据结构（Java语言描述）3.1栈作业布置结束放映章节目录03.链栈基本操作的实现1)求链栈的长度操作length()的实现(1)操作要求：计算出链栈中所包含的数据元素的个数并返回其值。(2)方法与求单链表长度的方法相同。ppplength123211830754256∧topp4p5p6p数据结构（Java语言描述）3.1栈作业布置结束放映章节目录(3)算法publicintlength(){}//算法3.3结束Nodep=top;intlength=0;时间复杂度为：O(n)1)求链栈的长度操作length()的实现(算法3.3)while(p!=null){p=p.getNext();++length;}数据结构（Java语言描述）3.1栈作业布置结束放映章节目录3.链栈基本操作的实现2)链栈的入栈操作push(x)的实现（算法3.4)(1)操作要求：将数据域值为x的新结点插入到链栈的栈顶，使其成为新的栈顶元素。x1830754256∧toptopNodep=newNode(x);p.setNext(top);top=p;p数据结构（Java语言描述）3.1栈作业布置结束放映章节目录(2)算法publicvoidpush(objectx){}//算法3.4结束Nodep=newNode(x);2)链栈的入栈操作push(x)的实现（算法3.4)时间复杂度为：O(1)p.setNext(top);top=p;数据结构（Java语言描述）3.1栈作业布置结束放映章节目录3.链栈基本操作的实现3)链栈的出栈操作pop()的实现（算法3.5)(1)操作要求：将首结点（或栈顶结点）从链栈中移去，