《数据结构 Java语言版 教学课件 ppt 王学军 第四章》由会员分享，可在线阅读，更多相关《数据结构 Java语言版 教学课件 ppt 王学军 第四章（84页珍藏版）》请在金锄头文库上搜索。
1、数据结构（Java语言版）,人民邮电出版社,第4章 栈和队列,主编:王学军,【内容简介】 本章通过实例引入栈和队列的概念，理解栈的“后进先出”和队列的“先进先出”的特点，掌握栈和队列在顺序存储和链式存储结构的特点以及相应的运算，以及栈和队列的实例应用。,【知识要点】 栈和队列的相关概念； 栈的“后进先出”、队列的“先进先出”的结构特点； 栈在顺序存储结构、链式存储结构下的特点及相应算法实现； 队列在顺序存储结构、链式存储结构下的特点及相应算法实现； 实例应用。,第一节,1.实例引入 【学习任务】 通过工程实例引入，重点理解栈的“后进先出”和队列的“先进先出”的操作特点。,实例：自古华山一条道。
2、 图4.1所示为华山上山的一段石路。自古华山一条道，假设道路只能允许一个人通过，那么，游客在登山游览的过程中，只能顺着石路一个接着一个上山，先登山的游客先到达目的地。这就类似于数据结构中的队列，满足“先进先出”的原则。如果在登山的过程中，由于某种原因，有一部分游客不想上山了，在返回的过程中，必须按照后上山的游客先下山，先上山的游客后下山的原则返回。这类似于数据结构中的栈，满足“后进先出”的原则。,图4.1 华山道路的一段,第二节,2.栈的相关概述 掌握栈的定义及相关概念，熟悉栈的操作顺序及元素进出栈的顺序，了解栈的存储结构。,2.1 栈的定义 栈是一种特殊的线性表，其全部操作都被限制在表的固定
3、一端进行，而且构成栈的元素必须是同一数据类型。 例如，对于【例4.1】，假设有10名游客组成的一个旅游团，其上山的顺序为游客1、游客2、游客3、游客10，由于某种原因，这10位游客不想上山了，其下山顺序为游客10、游客3、游客2、游客1，如图4.2所示，该过程和数据结构中栈的操作一致，其入栈对应上山顺序，其出栈对应下山顺序，满足“后进先出”的顺序。,2.2 栈的相关概念 栈的特点是在线性表的固定端（如图4.2所示的top端）进行操作，将进行操作的一端称为栈顶，用top表示；另一端称为栈底，用bottom表示。 栈的常用操作包括建立栈、元素进入栈（入栈）、元素退出栈（出栈）、取栈顶元素等。,图4
4、.2 栈示意图,2.3 栈的操作过程 栈的操作全部是在固定端（栈顶）进行的。 【例4.2】 停车场问题。 设有一个可以容纳4量车存放的停车场，一端封闭，另一端为车辆入口，如图4.3所示，设有4量编号为001、002、003、004的车按顺序进入停车场，每个车在停车场停留的时间最多不超过1小时，试写出其可能离开停车场的顺序。 （提示：由于某种原因，可能存在如下情况，当00x号车离开该停车场时，00（x+1）号车可能还没有进入停车场）。,分析：根据该问题的特点可知，进入和离开停车场只有一个口，因此该问题可归结为栈的问题，其操作全部是在左侧位置，即停车场的入口位置，因此某车预离开停车场，必须要等到停
5、车场中在其后面停放的车都离开后，该车才能离开。,图4.3 停车场模拟示意图,假设汽车进入停车场的顺序为001，002，003，004，如图4.4所示，求其离开停车场的顺序。,（a）一辆车在停车场,（b）两辆车在停车场,（c）3辆车在停车场,（d）4辆车在停车场 图4.4 进入停车场,第一种情况：001进入停车场，下面的操作可能出现两种情况。 （1）001在停车场已停留一个小时，其他车还没有进入停车场，此时001号车在其他车进入之前离开，所以退出顺序001排在第一位，如图4.4（a）所示。 （2）在001离开停车场之前，002进入停车场，此时001无法离开停车场，只有等待002离开后，001才可
6、以离开停车场，如图4.4（b）所示。,第二种情况：001和002都在停车场，可能出现如下情况。 （1）在其他车进入停车场之前，002离开停车场，过1小时后，001离开停车场，退出顺序为：002，001，如图4.4（b）所示。 （2）002离开停车场，在001离开停车场之前，003进入停车场，此时，停车场里的车是003和001，情况类似如图4.4（b）所示。,第三种情况：001和002都在停车场，003也进入停车场，可能出现如下情况。 （1）003离开停车场，分别在1小时和2小时后，002和001分别离开停车场，退出顺序：003，002，001，如图4.4（c）所示。 （2）003离开停车场，在
7、其他车离开之前，004进入停车场，此时，停车场里的车是004、002和001，情况类似如图4.4（c）所示。 （3）003离开停车场，1小时后，002也离开停车场，在001离开停车场之前，004进入停车场，此时，停车场里的车是004和001，情况类似如图4.4（b）所示。,第四种情况：001、002和003都在停车场，004也进入停车场，此时出现的情况只有一种，如图4.4（d）所示。离开停车场的顺序为：004、003、002、001。 因此，离开停车场的顺序可能为 001，002，003，004，001，002，004，003，001，003，002，004，001，003，004，002，0
8、02，001，003，004，002，001，004，003，002，003，001，004，002，003，004，001，其余情况请读者考虑。,综上所述，栈是一个后进先出（Last In First Out，LIFO）的线性表，即最后进栈的元素最先出栈，最先入栈的元素最后出栈。,2.4 栈的存储结构 栈是特殊的线性表，因此其存储结构和线性表非常类似，也可以分为顺序存储结构和链式存储结构。 1顺序栈 将栈在顺序存储结构下所得到的结构，称为顺序栈。顺序栈类似于高级语言中的数组，因此可以使用数组实现顺序栈的相关运算。,利用Java语言实现数组表示栈类的定义如下： public class Sta
9、ckX /定义栈 private final int SIZE = 20; private int st; private int top; public StackX() /构造方法 st = new intSIZE; top = -1; public void push(int j) /压栈 st+top = j; ,public int pop() /出栈 return sttop-; public int peek() return sttop; public boolean isEmpty() /空栈 return (top = -1); ,2链式栈 将栈在链式存储结构下所得到的结构
10、，称为链式栈。链式栈类似于高级语言中的指针，在Java语言中可以通过类的对象引用实现指针运算。,第三节,3 . 用数组实现顺序栈及操作 【学习任务】 理解顺序栈连续存储的特点，基本运算方法及利用Java语言实现程序的方法和特点。 顺序栈的结构和高级语言中的数组一样，可用一段连续的空间存储栈中的各个元素，如图4.5所示。,图4.5 顺序栈的数组表示示意图,将数组的一端固定作为栈底（一般指下标小的一端），用bottom表示；另一端为栈顶，是栈的操作端，用top表示。当增加元素时，top随着变化，总是指向栈顶元素。当top达到数组的最大值an时，表示栈满状态，此时，只能进行出栈操作，而不能进行入栈操
11、作。,【例4.3】 根据【例4.2】中的停车场问题，再结合如图4.3所示的图形，完成停车场中有关车辆的相应操作： 判断目前停车场是否有车辆，即是否为空； 目前有00x号的汽车进入停车场，如何实现操作； 现停车场最外边的车号为00y，该车离开停车场，如何实现操作； 若想判断停车场最外面的车是哪辆车，如何操作。 根据对题目分析可知，此操作为栈的相关操作，为实现该操作，采用数组方式描述栈，令数组下标为0端为栈底，不允许操作；另一端为栈顶，完成栈的操作，实现程序如下。, 判断停车场是否为空： public boolean empty() return top = -1; /如果栈是空的话，return
12、 true; 现有某车进入停车场，算法实现如下： public void push(Object element) if(top=stack.length-1) System.out.println(“栈满“); stack+top=theElement; , 现停车场最外边的某车出停车场，算法实现如下： public Object pop() if(empty() System.out.println(“栈空“); Object topElement=stacktop; stacktop-=null; return topElement; 若想判断停车场最外面车辆的车号，算法实现如下： pu
13、blic Object peek() if(empty() System.out.println(“栈空“); return stacktop; ,针对以上个步骤算法，则车辆入栈和出栈实现如下： public class OrderStack int top = -1; String stack; public OrderStack(int initcap)throws Exception if(initcap=0) throw new Exception(“容量必须大于或等于1“); else stack = new Stringinitcap; ,public boolean empty(
14、) return top = -1; /如果栈是空 return true; public void push(String element) if(top=stack.length-1) System.out.println(“栈满“); stack+top=element; ,public String pop() if(empty() System.out.println(“栈空“); String topElement=stacktop; stacktop-=null; return topElement; public static void main(String args) tr
15、y String bus = new String “001“, “002“, “003“, “004“ ; OrderStack os = new OrderStack(bus.length); for(int i = 0; i bus.length; i+) os.push(busi); ,while(os.top -1) System.out.println(os.pop(); catch (Exception e) e.printStackTrace(); ,程序运行的结果为 004 003 002 001,第四节,4 .用类实现链式栈及相应操作 【学习任务】 理解链栈的非连续存储特点，基本运算方法及利用Java语言实现程序的方法和特点。,图4.6 链式栈的表示示意图,【算法4.2】 通过下面的【例4.4】实现链栈的各种运算。 【例4.4】 根据【例4.2】中的停车场问题，再结合如图4.3所示的图形，完成停车场中有关车辆的相应操作： 判断目前停车场是否有车辆，即是否为空； 目前有00x号的汽车进入停车场，如何实现操作； 现停车场最外边的车号为00y，该车离开停车场，如何实现操作； 若想判断停车场最外面的车是哪辆车，如何操作。 根据对题目分析可知，此操作为链栈的
