第4章 栈与队列(已看)

1、第4章栈与队列4.1 栈24.1.1栈的定义栈插入、删除只在线性表进行的线性表被称为。删除4.1.2 栈的抽象数据类型栈的接口StackInterfacepackage ds_java;public interface StackInterface /栈的接口public boolean isEmpty(); /判断栈的状态是否为空public boolean isFull(); /判断栈的状态是否已满public boolean push(Object k); /k对象入栈public Object pop(); /出栈public Object get(); /获得栈顶元素，未出栈顺序栈链

2、式存储结构：链栈1栈的顺序存储结构及操作实现4.1.3 栈的存储结构及实现package ds_java;import ds_java.StackInterface;public class Stack1 implements StackInterface /栈的顺序存储结构private Object table;private final int empty=-1;/声明整数常量private int top=empty; /top为栈顶元素下标栈空时，top=-1；非空时，top位于栈顶元素的位置;顺序栈的空间可不断追加top4321top9（3）判断栈是否已满当top>=tabl

3、e.length时，栈已满：public boolean isFull() return top>=table.length;（4）获得栈顶数据元素值当栈非空时，获得top位置处栈顶数据元素，此时该数据元素未出栈，top值不变。public Object get() /获得栈顶数据元素，未出栈if(!isEmpty()return tabletop;elsereturn null;12(5)入栈：ktop43top+;tabletop=k;21（5）入栈当栈不满时，栈顶数据元素下标top加1，将k放入top位置中，作为新的栈顶数据元素。此时入栈的数据元素是String等对象。算法如下：O

4、bject对象，可以是Integer或public boolean push(Object k) /k对象入栈if(!isFull() /栈不满top+;tabletop=k;return true;else System.out.println("栈已满，"+k+"值无法入栈！");return false; /栈溢出(6)出栈toptopk=tabletop; tabletop=null;top-;/取得栈顶元素当栈不空时，取走top位置处栈顶数据元素，top减1，下一位置数据元素作为新的栈顶数据元素。此时出栈的数据元素是Object对象，可以转化为

5、Integer或String等对象。算法如下：public Object pop() /出栈Object k=null;if(!isEmpty() /栈不空k=tabletop; /取得栈顶元素tabletop=null;top-;return k; /栈空时返回null16（6）出栈【例4.1】使用顺序栈的基本操作2栈的链式存储结构及操作实现import ds_java.OnelinkNode; /引用单链表结点类import ds_java.Onelink1;public class Stack2 extends Onelink1/栈的链式存储结构private OnelinkNode t

6、op;图4.3 栈的链式存储结构*链式栈的基本操作data nexttop=null(a) 栈状态为空top=null(e) 最后一个元素出栈后，栈为空4.1.4 栈的应用举例1栈是嵌套调用机制的实现基础2实现深度遍历算法时使用栈32top=1021【例4.2】判断表达式中括号是否匹配假设在表达式中，允许现两种括号：（、）和、，试验证任意表达式所含括号匹配情况的正确性。（ （）括号不匹配情况：（ ）各类括号数量不同（）左少(栈空)；左多(栈非空)不（）当前出现的右括号确不是所期待的，即嵌（）套关系不正确判断表达式中括号是否匹配的算法描述逐一处理表达式中的每个字符ch：ch=非括号：不做任何处理

7、ch=左括号：入栈ch=右括号：if (栈空) return falseelse 出栈，检查匹配情况，if (不匹配) return false如果结束后，栈非空，返回false。public static String isValid(String expstr) Stack1 s1=new Stack1(30); /创建空栈char ch; int i=0; boolean yes=true;String out;while(yes && i<expstr.length() ch=expstr.charAt(i);i+; switch(ch) case '(&

8、#39;: s1.push(ch+""); /遇见左括号时,入栈break;case ')': out=(String)s1.pop(); /遇见右括号时,出栈if(out=null | !out.equals("(")yes=false; /判断出栈的是否为左括号 if(yes)if(s1.isEmpty()return "OK!"else return "期望)!"elsereturn "期望(!"4.2 队列4.2.1队列的定义4.2.2 队列的抽象数据类型4.2.3 队列

9、的存储结构及实现4.2.4 队列的应用举例4.2.1 队列的定义若线性表的插入操作在一端进行，删除操作在另一端进行，则称此线性表为。队头front队尾rear删除端插入端FIFO(irst n irst ut) 队头、队尾均是浮动的队列的接口QueueInterfacepublic interface QueueInterface /队列的接口public boolean isEmpty(); /判断队列状态是否为空public boolean isFull(); /判断队列状态是否已满public boolean enqueue(Object k); /k对象入队public Object

10、dequeue(); /出队4.2.2 队列的抽象数据类型1队列的数据元素2队列的基本操作队列的初始化，设置队列状态为空。判断队列的状态是否为空。判断队列的状态是否已满。入队：将数据元素从队尾处加入队列的过程。在入队之前必须判断队列的状态是否已满，如果队列不满，则接收新数据元素入队，队列满时数据元素不能入队，产生上溢错误（overflow）。出队：从队头处取出数据元素的过程。在出队之前，必须判断队列的状态是否为空。队列空时，取不到元素，产生下溢错误（underflow）。4.2.3 队列的存储结构及实现1队列的顺序存储结构123401234frontrear(a) 以数组存储队列的数据元素fr

11、ontrear(b) 队列的“假溢出”2顺序循环队列及操作实现循环42队满(Q.rear+1)%MAXSIZE=Q.front循环队列小结操作一致rear后移一位解决“假溢出”现象循环队列下标0.n-1队空、满标志相同修改队满标志43循环队列基本操作:（1）队列的初始化构造方法申请table数组的存储空间准备存放队列数据元素，设置队列初始状态为空，即front =0且rear=0。：public Queue1(int n) /构造长度为n的空队列table=new Objectn;front=rear=0;(2）判断队列状态是否为空当front=rear时，队列为空。public boolea

12、n isEmpty() /判断队列状态是否为空return front=rear;（3）判断队列是否已满当front=(rear+1)% table.length时，队列已满public boolean isFull() /判断队列状态是否已满 return front=rear%table.length+1; 45（4）入队当队列不满时，将k对象存放在rear位置作为新的队尾数据元素，rear循环加1。此时入队的数据元素是Object对象。public boolean enqueue(Object k) /k值入队if(!isFull() /队列不满tablerear=k;rear=(rea

13、r+1) % table.length;return true;elseSystem.out.println("队列已满，"+k+"值无法入队！return false; /队列溢出46");（5）出队当队列不空时，取走front位置上的队首数据元素，front循环加1，front位置上的数据元素成为新的队首数据元素。此时出队的数据元素是Object对象。public Object dequeue() /出队Object k=null;if(!isEmpty() /队列不空k=tablefront; /取得队头结点数据元素tablefront=null;

14、front=(front+1) % table.length;return k; /队列空时返回null47front=null rear=null(e) 最后一个元素出队后，队列状态为空链式队列的基本操作实现4.2.4 队列的应用举例1处理等待问题时系统设立队列队列具有“先进先出”的特性，当需要按一定次序等待时，系统需设立一个队列。2实现广度遍历算法时使用队列实现广度遍历算法，如按层次遍历二叉树、以广度优先算法遍历图，都需要使用队列。详细算法将在以后的章节中介绍。4.3 递归1问题的定义是递归的1n!=n(n-1)!n=0,1n2n=0，1nf(n)=f(n-1)+f(n-2)n22算法是递

15、归的 根据递归定义，编写能够直接反映递归定义的递归函数来求解。【例4.6】求n！。54*【例4.7】打印数字塔。打印如下形式的数字塔：1 1 2 1 1 2 3 2 1 1 2 3 4 3 2 1 1 2 3 4 5 4 3 2 1 1 2 3 4 5 6 5 4 3 2 1 1 2 3 4 5 6 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1 题目本身虽不是递归定义的，但可以用递归算法求解。程序如下：3数据结构是递归的 将单向链表结点类的next链与指向链表第1个结点的head递归定义为：next及head=null指向一个空链表非null指向一个单向链表data nexthead=null(a) 空链表(b) 单向链表*【例4.8】单向链表结点递归定实习41实验目的：使用栈、队列或递归算法求解问题2题意（1）走迷宫一个迷宫可以看成一个二维数组，如图4.17所示。每个迷宫都有一个入口和一个出口，其中白色单元表示通路，黑色单元表示路不通。试寻找一条通过迷宫的路径，从入口进入迷宫，每次移动只能从一个