数据结构与算法项目化教程ppt模块2 栈-歌曲播放器.pptx

《数据结构与算法项目化教程ppt模块2 栈-歌曲播放器.pptx》由会员分享，可在线阅读，更多相关《数据结构与算法项目化教程ppt模块2 栈-歌曲播放器.pptx（62页珍藏版）》请在汇文网上搜索。

1、项 目 描 述相 关 知 识项 目 实 施项 目 总 结C O N T A N T S目录 项目描述某公司的播放器软件程序的研发工作。播放器的其中一个功能是：从播放列表中顺序播放歌曲。设计一个程序，模拟播放器的播放顺序功能。项目描述introduction具体系统功能需求如下：（1）可在待播放歌曲列表添加歌曲。（2）当前点击播放的歌曲因为是最想听的，应先播放，即后加入歌曲列表的歌曲先播放。（3）待播放列表设定最大长度作为任务1，不设定最大长度作为任务2。（4）输入错误提示：最大长度设定值只能为数字，如输入字符，系统自动将其设置为默认值20。项目描述introduction本项目利用栈结构存储待

2、播歌曲。“添加歌曲”功能对应入栈操作，新加的歌曲放在栈顶（待播歌曲栏的最上方），“播放歌曲”功能对应出栈操作，即从栈顶取出最后放入的歌曲，添加到已播歌曲列表。项目描述图2-1 播放器示意图图2-2 播放器程序界面 相关知识栈的定义 栈的基本运算 顺序栈 链栈Useful knowleage相关知识栈的定义栈的基本运算顺序栈链栈栈是一种特殊的线性表，它仅允许在表的一端进行运算。在表中，允许插入和删除的一端称为“栈顶”，另一端称为“栈底”，将元素插入栈顶的操作成为“进栈”，称删除栈顶元素的操作为“出栈”，如图2-3所示。因为出栈操作时后进栈的元素先出，所以栈也被称为是一种“后进先出”表，简称为LI

3、FO（Last In First Out）。1栈的定义图2-3 堆栈根据实际应用，通常认为，栈应该包含了以下一些基本运算：（1）栈初始化置栈为空栈。（2）判断栈是否为空若栈为空，则返回true，否则返回false。（3）求栈的长度返回栈的元素个数。（4）进栈将一个元素下推进栈。（5）出栈将栈顶元素托出栈。（6）读栈顶返回栈顶元素。2栈的基本运算抽象数据类型(abstract data type,ADT)是带有一组操作的一些对象的集合，在ADT的定义中只定义了一些基本的操作，没有提到关于这组操作是如何实现的任何解释。在Java中，我们用栈的接口IStack表示栈这些功能操作的集合。在后面的例子中

4、，我们将实现这个接口，通过展示不同的实现代码，详细解释顺序栈和链栈的不同之处。但不管怎样，只要这些类实现了栈的接口，你就可以将其成为栈。2栈的基本运算栈的接口代码如下:public interface IStack public void push(Object obj)throws Exception;/进栈public Object pop()throws Exception;/出栈 public Object getTop()throws Exception;/取栈顶public boolean isEmpty();/判断栈是否为空public int getSize();/求栈长2栈的

5、基本运算与线性表类似，栈的存储结构也分为顺序存储结构和链式存储结构。顺序存储结构的栈简称为顺序栈，链式存储结构的栈称为链栈。1)顺序存储定义2)顺序栈的基本运算3)顺序栈的动手实践3顺序栈1)顺序存储定义与顺序线性表类似，顺序栈也需要通过一个一维数组存储元素，同时设置栈顶元素的位置下标，如图2-4所示。顺序栈=一维数组+栈顶指示图2-4 顺序栈的存储结构顺序栈用一个类SeqStack 实现，其数据类型描述如下:public class SeqStack implements IStack final int defaultSize=10;int maxSize;int top;/栈顶指示Obj

6、ect stack;/一维数组顺序栈用一维数组stack存放数据，序号为i的元素a_i对应数组的下标是i-1，即用stacki-1表示，栈顶用stacktop表示。栈空及栈满条件：栈空条件：top=-1。栈满条件：top=MaxSize-1。2)栈的基本运算 Useful knowleage判断栈是否为空2求栈的长度3进栈操作4出栈操作5获取栈顶元素6栈初始化1打印栈中所有元素72)栈的基本运算 出栈操作栈是否为空栈的长度进栈操作栈初始化栈顶元素打印栈中所有元素栈的初始化实现比较简单，通过添加一个initiate方法，在该方法中将栈顶top的值设置为-1即可，同时创建一个用于存储栈中元素的一维

7、数组stack，参数sz表示栈的大小。然后在构造函数中调用此方法。public class SeqStack implements IStack final int defaultSize=10;int maxSize;int top;/栈顶指示Object stack;/一维数组 public SeqStack()initiate(defaultSize);public SeqStack(int sz)initiate(sz);private void initiate(int sz)maxSize=sz;top=-1;stack=new Objectsz;2)栈的基本运算 出栈操作栈是否为

8、空栈的长度进栈操作栈初始化栈顶元素打印栈中所有元素此处实现接口中的isEmpty方法。在判断栈是否为空时，只需将栈顶指示top值与-1相比即可，若top值为-1，则表示顺序栈中不包含任何元素，代码如下。public boolean isEmpty()return top=-1;2)栈的基本运算 出栈操作栈是否为空栈的长度进栈操作栈初始化栈顶元素打印栈中所有元素此处实现接口中的getSize方法。栈的长度即为栈中数组的元素个数，因为top值总是指向最后一个元素，考虑到当top值为0时，已经有一个元素存在，则元素的个数为top+1，代码如下。public int getSize()return t

9、op+1;2)栈的基本运算 出栈操作栈是否为空栈的长度进栈操作栈初始化栈顶元素打印栈中所有元素此处实现接口中的push方法。假设顺序栈中包含元素(a1,a2,a3),将元素e入栈时，实际就是要在栈顶位置插入该元素。相关过程如图2-5所示，具体步骤为：（1）栈顶指示top朝栈的增长方向前进一步（即top值增1）。（2）将元素放入栈中由当前栈顶top指向的位置上。在栈的这种静态实现中，进行进栈运算时，必须先进行栈满检查，以避免错误。图2-5 将元素入栈2)栈的基本运算 出栈操作栈是否为空栈的长度进栈操作栈初始化栈顶元素打印栈中所有元素 public void push(Object obj)thr

10、ows Exception if(top=maxSize-1)throw new Exception(栈满无法进栈！);else top+;stacktop=obj;2)栈的基本运算 出栈操作栈是否为空栈的长度进栈操作栈初始化栈顶元素打印栈中所有元素 此处实现接口中的pop方法。同样假设顺序栈中包含元素(a1,a2,a3),现将a3元素出栈，只需将栈顶指示top后退一步（即top值减1）即可，如图所示。同时若需在出栈的同时返回该出栈元素，还需通过一个临时变量获取a3并返回。应该注意的是，出栈前应进行栈空检查。public Object pop()throws Exception if(top=

11、-1)return null;else Object e=stacktop;top-;return(e);2)栈的基本运算 出栈操作栈是否为空栈的长度进栈操作栈初始化栈顶元素打印栈中所有元素 此处实现接口中的getTop方法。根据栈顶指示top，可以直接获取最后入栈的元素。应该注意的是，在进行读取之前，也要进行栈空检查，代码如下:public Object getTop()throws Exception if(top=-1)return null;return stacktop;2)栈的基本运算 出栈操作栈是否为空栈的长度进栈操作栈初始化栈顶元素打印栈中所有元素 此方法非接口中定义的功能，但

12、可以在SeqStack类中进行扩展，代码如下:public void print()for(int i=0;i=top;i+)System.out.print(stacki+);System.out.println();public static void main(String args)throws Exception/创建一个栈SeqStack ss=new SeqStack();/判断是否为空System.out.println(是否为空：+ss.isEmpty();/进栈操作,1-10依次进栈for(int i=0;i10;i+)ss.push(i+1);/打印栈中元素ss.prin

13、t();/显示栈顶元素System.out.println(当前栈顶元素为+ss.getTop();/出栈5次，并显示每一次的出栈元素for(int i=0;i5;i+)System.out.println(出栈元素为+ss.pop();/显示栈长System.out.println(当前栈长为+ss.getSize();测试端代码图2-7 堆栈程序运行结果3)顺序栈的动手实践12345实现思路实训内容关键代码运行结果实训目的掌握顺序栈的进栈、出栈等操作，学会较为复杂问题的求解。3)顺序栈的动手实践12345实现思路实训内容关键代码运行结果实训目的给定一个只包括(，)，的字符串 s，判断字符串

14、是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。示例1示例2示例3示例4示例5输入：s=()输出：true输入：s=()输出：true输入：s=(输出：false输入：s=()输出：false输入：s=输出：true3)顺序栈的动手实践12345实现思路实训内容关键代码运行结果实训目的如果计算出左括号的数量，和右括号的数量，如果每种括号左右数量相同，会不会就是有效的括号了呢？事实上不是的，假如输入是，每种括号的左右数量分别相等，但不是有效的括号。这是因为结果还与括号的位置有关。仔细分析我们发现，对于有效的括号，它的部分子表达式仍然是有效的括号，比如()

15、()是一个有效的括号，()是有效的括号，()也是有效的括号。并且当我们每次删除一个最小的括号对时，我们会逐渐将括号删除完。这个思考的过程其实就是栈的实现过程。因此我们考虑使用栈，当遇到匹配的最小括号对时，我们将这对括号从栈中删除（即出栈），如果最后栈为空，那么它是有效的括号，反之不是。3)顺序栈的动手实践12345实现思路实训内容关键代码运行结果实训目的括号匹配栈的原理图3)顺序栈的动手实践12345实现思路实训内容关键代码运行结果实训目的请读者理解代码并填空，运行得到相应结果。public static boolean isValid(String s)throws Exception Se

16、qStack stk=new SeqStack(s.length();for(char c:s.toCharArray()/如果c是(则入栈if(c=(|c=|c=)/如果c是)并且栈不为空 则判断栈顶是否为与之对应的左括号。是则出栈，不是则返回fasleelse if(c=)&!stk.isEmpty()&(char)stk.getTop()=()else if(c=&!stk.isEmpty()&(char)stk.getTop()=)else if(c=&!stk.isEmpty()&(char)stk.getTop()=)else/如果c是)栈为空 那么返回false/如果c是)栈不为

17、空，但是 栈顶不是与c对应的左括号 那么返回falsereturn false;/例如()，如果最后栈不为空，那么就是有多余的左括号了return stk.isEmpty();3)顺序栈的动手实践12345实现思路实训内容关键代码运行结果实训目的public static void main(String args)throws Exception Scanner input=new Scanner(System.in);System.out.println(请输入一个字符串：);String text=input.next();boolean flag=isValid(text);if(fl

18、ag)System.out.println(text+括号匹配);elseSystem.out.println(text+括号不匹配);测试端代码3)顺序栈的动手实践12345实现思路实训内容关键代码运行结果实训目的顺序存储实现下，每个栈都需要按最大需求留足存储空间，这必将造成存储空间的大量浪费。解决此问题的方法之一就是采取栈的链式存储实现。1)栈的链式存储结构2)链栈的基本运算3)链栈的动手实践4链栈1)栈的链式存储结构栈的链式存储表示也称为链栈，它实际上是一个单链表，并以其链头指针作为栈顶指针。链栈的结构示意图如下：因此，进出栈的运算都只能在链头进行。即链栈=单链表+栈顶指针4链栈链栈Li

19、nkStack类同样实现了IStack接口，其数据类型描述如下：public class LinkStack implements IStack Node top;/栈顶节点int size;/节点个数 其中节点类Node符合单链表中节点类的设计思路，即由两个类成员组成，一个表示元素本身，一个存储下一个节点的引用，其类型描述如下:public class NodeObject data;/数据元素Node next;/表示下一个结点的对象引用Node(Node nextval)/用于头结点的构造函数1next=nextval;Node(Object obj,Node nextval)/用于其他

20、结点的构造函数2data=obj;next=nextval;4链栈栈空条件：top=null；2)链栈的基本运算4链栈栈初始化进栈操作判断栈是否为空出栈操作求栈的长度获取栈顶元素栈初始化2)链栈的基本运算 栈初始化public class LinkStack implements IStack Node top;/栈顶节点 int size;/节点个数/构造函数public LinkStack()top=null;/空栈size=0;2)链栈的基本运算 判断栈是否为空此处实现接口中的isEmpty方法。在判断栈是否为空时，只需将栈顶节点top与null相比即可，代码如下:public bool

21、ean isEmpty()return top=null;2)链栈的基本运算 求栈的长度此处实现接口中的getSize方法，代码如下:public int getSize()return size;2)链栈的基本运算 进栈操作此处实现接口中的push方法。假设元素e要进栈，进栈过程如图所示:相关的操作可按以下步骤进行。(1)形成元素e对应的节点p；Node p=new Node(e,null);(2)p结点指向原栈顶节点top；p.next=top;(3)栈顶节点top指向p结点。top=p;此外，当进栈时，表示栈长的size也要加1，代码如下:public void push(Object

22、e)throws Exception Node p=new Node(e,null);p.next=top;top=p;size+;2)链栈的基本运算 出栈操作现接口中的pop方法。假设栈顶节点top要出栈，出栈过程如图：出栈操作可按照以下步骤进行。(1)首先判断栈是否为空，为空则无法进行出栈操作，抛出一个异常；if(size=0)throw new Exception(堆栈已空);(2)获取当前栈顶节点top的元素值，用于返回该出栈元素Object obj=top.data;(3)栈顶节点top沿链指向下一节点；释放之前top的存储空间。top=top.next;2)链栈的基本运算 出栈操作

23、当出栈时，表示栈长的size也要减1，代码如下：public Object pop()throws Exception if(size=0)throw new Exception(堆栈已空);Object obj=top.data;top=top.next;size-;return obj;2)链栈的基本运算 打印栈中所有元素此方法非接口中定义的功能，可利用单链表的特点进行栈的元素遍历，实现代码如下：public void print()Node curr=top;while(curr!=null)System.out.print(curr.data+);curr=curr.next;Syst

24、em.out.println();2)链栈的基本运算 打印栈中所有元素 要测试上述这些方法，可以编写测试端代码如下所示，相关结果如图所示：public static void main(String args)throws Exception/创建一个栈类LinkStack ls=new LinkStack();/判断是否为空System.out.println(是否为空：+ls.isEmpty();/进栈操作,10个随机数进栈Random rnd=new Random();for(int i=0;i10;i+)ls.push(rnd.nextInt(100);/显示栈中元素ls.print(

25、);/显示栈顶元素System.out.println(当前栈顶元素为+ls.getTop();/出栈5次，并显示每一次的出栈元素for(int i=0;i5;i+)System.out.println(出栈元素为+ls.pop();/显示栈长System.out.println(当前栈长为+ls.size();在顺序栈的遍历中，我们是从下标为0的数组进行遍历，因此出栈元素为遍历序列的最后一个元素。而链栈的遍历中，我们从top栈顶开始进行遍历，因此出栈元素为遍历序列的第一个元素。2)链栈的基本运算 获取栈顶元素实现接口中的getTop方法。此处直接返回栈顶节点top的数值域部分即可，代码如下：

26、public Object getTop()throws Exception return top.data;3)链栈的动手实践实训目的掌握链栈的进栈、出栈等操作，学会较为复杂问题的求解。实训内容十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：N=(N div d)d+N mod d (其中:div为整除运算,mod 为求余运算)假设现要编制一个满足下列要求的程序：对于输入的任意一个非负十进制整数N，选择一个要转换的进制d，打印输出与其等值的d进制数。4链栈3)链栈的动手实践实现思路首先你需要先了解这几种数据类型之间的转换规则4链栈3)链

27、栈的动手实践实现思路在上述计算过程中，第一次求出的值为最低位，最后一次求出的值为最高位。而打印时应从高位到低位进行，恰好与计算过程相反。根据这个特点，我们可以通过入栈出栈来实现，即将计算过程中依次得到的d进制数码按顺序进栈，计算结束后，再顺序出栈，并按出栈顺序打印输出，即可得到给定的二进制数。这是利用栈后进先出特性的经典例子。4链栈3)链栈的动手实践关键代码public static void dataConversion(int N,int d)throws ExceptionLinkStack ls=new LinkStack();while(N!=0)int x=N%d;/将x入栈 N=

28、N/d;/打印ls 4链栈3)链栈的动手实践关键代码public static void main(String args)throws Exception Scanner input=new Scanner(System.in);System.out.println(请输入待转换的十进制正整数：);int number=input.nextInt();System.out.println(请输入要转换的进制：);int type=input.nextInt();System.out.println(转换结果);dataConversion(number,type);4链栈3)链栈的动手实践运

29、行结果4链栈图2-16 括号匹配运行结果截图 项目实现任务1：限制队长的歌曲播放器任务2：不限制队长的歌曲播放器这个任务要求限制队长，考虑用顺序栈实现，队长可由用户手动输入限制。用顺序栈实现点歌程序代码如下:public class PutPlateAction extends BaseAction /顺序栈private int listCount=1;private SeqStack seqStack;private List listStack;/*设置长度*/public ActionForward toPutPlateList(ActionMapping mapping,Action

30、Form form,HttpServletRequest request,HttpServletResponse response)throws Exception listCount=1;int length=Integer.valueOf(request.getParameter(length);seqStack=new SeqStack(length);listStack=new ArrayList();request.setAttribute(length,length);return new ActionForward(/pages/three/putPlateList.jsp);任

31、务1：限制队长的歌曲播放器/*更新长度*/public ActionForward ajaxUpdateLength(ActionMapping mapping,ActionForm form,HttpServletRequest request,HttpServletResponse response)throws Exception listCount=1;int length=Integer.valueOf(request.getParameter(length);seqStack=new SeqStack(length);listStack=new ArrayList();return

32、 null;/*装载已播歌曲*/public ActionForward ajaxLoadList(ActionMapping mapping,ActionForm form,HttpServletRequest request,HttpServletResponse response)throws Exception List list=seqStack.getObjs();for(String str:listStack)list.add(new ShowBean(str,true);renderText(response,getJSON(list);return null;任务1：限制队

33、长的歌曲播放器/*添加歌曲*/public ActionForward ajaxPushList(ActionMapping mapping,ActionForm form,HttpServletRequest request,HttpServletResponse response)throws Exception String obj=歌曲+listCount;try seqStack.push(obj);/进入待播栈 catch(Exception e)renderText(response,1);return null;listCount+;/待播歌曲加1renderText(response,0);return null;任务1：限制队长的歌曲播放器/*播放歌曲*/public ActionForward ajaxPopList(ActionMapping mapping,Act