栈与队列(java版).ppt

第三章第三章 栈与队列栈与队列教学内容教学内容3.2 队列队列3.1 栈栈3.4 栈与队列的综合应用举例栈与队列的综合应用举例3.3 栈与队列的比较栈与队列的比较教学重点与难点教学重点与难点重点：重点：u栈、队列的特点；栈、队列的特点；u栈、队列基本操作的实现算法栈、队列基本操作的实现算法难点：难点：u栈、队列的应用栈、队列的应用 通常称，栈和队列是限定插入插入和删除只能删除只能在表的“端点端点”进行的线性表。线性表线性表 栈栈 队列队列 Insert(i,x)Insert(n,x)Insert(n,x)0in Delete(i)Delete(n-1)Delete(0)0in-1 栈和队列是两种操作受限的线性栈和队列是两种操作受限的线性表，是两种常用的数据类型。表，是两种常用的数据类型。3.1.1 3.1.1 栈的概念栈的概念(1)(1)栈是栈是栈是栈是仅限制在表尾进行插入和删除操作仅限制在表尾进行插入和删除操作仅限制在表尾进行插入和删除操作仅限制在表尾进行插入和删除操作的特的特的特的特 殊线性表，限制操作的表尾端称为殊线性表，限制操作的表尾端称为殊线性表，限制操作的表尾端称为殊线性表，限制操作的表尾端称为“栈顶栈顶栈顶栈顶”,另一另一另一另一 端称为端称为端称为端称为“栈底栈底栈底栈底”a0 a1 a2 an-1栈底栈底栈底栈底栈顶栈顶栈顶栈顶进进出出(2)栈是栈是“后进先出后进先出”的线性表（的线性表（LIFO）或）或 “先先 进后出进后出”的线性表（的线性表（FILO）3.1.1 3.1.1 栈的概念栈的概念 如下图所示的是铁路调度站形象地如下图所示的是铁路调度站形象地表示栈的表示栈的“后进先出后进先出”特点。特点。3.1.1 3.1.1 栈的概念栈的概念思考题：思考题：设有编号为设有编号为1 1，2 2，3 3，4 4的四辆的四辆列车，顺序进一个栈式结构的站台，列车，顺序进一个栈式结构的站台，具体写出这四辆列车开出车站的所具体写出这四辆列车开出车站的所有可能的顺序。有可能的顺序。3.1.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；3.1.2 3.1.2 栈的抽象数据类型描述栈的抽象数据类型描述 clear()1 1）栈的置空操作：）栈的置空操作：isEmpty()2 2）栈的判空操作：）栈的判空操作：length()3）求栈的长度：）求栈的长度：4）取栈顶元素操作：）取栈顶元素操作：5）入栈操作：）入栈操作：peek()push(x)6）出栈操作：）出栈操作：pop()1.1.基本操作基本操作3.1.2 3.1.2 栈的抽象数据类型描述栈的抽象数据类型描述 2.2.栈的抽象数据类型的栈的抽象数据类型的JavaJava接口描述接口描述public interface IStack public void clear();public boolean isEmpty();public int length();public Object peek();public void push(Object x)throws Exception;public Object pop();实现此接口的方法有两种实现此接口的方法有两种:顺序栈顺序栈链栈链栈3.1.3 3.1.3 顺序栈及其基本操作的实现顺序栈及其基本操作的实现1.顺序栈顺序栈非空栈非空栈空栈空栈a0a1an-1 top=n stackElem maxSize-10 1 n-1 top=0stackElem maxSize-10 1 2 3.1.3 3.1.3 顺序栈及其基本操作的实现顺序栈及其基本操作的实现1.顺序栈顺序栈思考思考栈空条件栈空条件?栈满条件栈满条件?栈的长度栈的长度?栈顶元素栈顶元素?如下问题如何描述如下问题如何描述?top=0top=stackElem.lengthtopstackElemtop-1a0a1an-1 top=n stackElem 0 1 n-13.1.3 3.1.3 顺序栈及其基本操作的实现顺序栈及其基本操作的实现2.2.顺序栈类的描述顺序栈类的描述(书书P71-P71-与与P33P33顺序表类对照学习顺序表类对照学习)public class SqStack implements IStack private Object stackElem;private int top;/构造一个容量为构造一个容量为maxSize的空栈的空栈 public SqStack(int maxSize)/栈置空栈置空 public void clear()stackElem=new ObjectmaxSize;top=0;top=0;2.顺序栈类的描述顺序栈类的描述(见教材见教材P71)P71)public class SqStack implements IStack /栈栈判判空空public boolean isEmpty()/求栈数据元素个数函数求栈数据元素个数函数 public int length()/取栈顶元素的函数取栈顶元素的函数 public Object peek()return top=0;return top;if(!isEmpty()/栈非空栈非空return stackElemtop-1;/栈顶元素栈顶元素 elsereturn null;2.顺序栈类的描述顺序栈类的描述(见教材见教材P71)P71)public class SqStack implements IStack /入栈操作的函数入栈操作的函数public void push(Object x)/出栈操作的函数出栈操作的函数public void pop()/输出函数输出函数(从栈顶到栈底从栈顶到栈底)public void display()for(int i=top-1;i=0;i-)System.out.print(stackElemi.toString()+);3.顺序栈基本操作的实现顺序栈基本操作的实现1)顺序栈的入栈操作顺序栈的入栈操作 push(x)的实现（算法的实现（算法 3.1)(1)操作要求：操作要求：插入元素插入元素x使其成为顺序栈中新的栈使其成为顺序栈中新的栈顶元素。顶元素。x a0a1an-1 toptop a.判断顺序栈是否为满，若满则抛出异常判断顺序栈是否为满，若满则抛出异常 b.若栈不满，则将新元素若栈不满，则将新元素x 压入栈顶，并修压入栈顶，并修正栈顶指针正栈顶指针 (2)(2)算法步骤：算法步骤：算法步骤：算法步骤：if(top=stackElem.length)throw new Exception(栈已满栈已满)1)顺序栈的入栈操作顺序栈的入栈操作 push(x)的实现（算法的实现（算法 3.1)statckElemtop+=xstatckElemtop=x;top=top+1;(3)(3)算法算法算法算法public void push(Object x)throws Exception /算法3.1结束if(top=stackElem.length)throw new Exception(栈已满栈已满);else stackElemtop+=x;1)顺序栈的入栈操作顺序栈的入栈操作 push(x)的实现（算法的实现（算法 3.1)时间复杂度为：时间复杂度为：O(1)3.顺序栈基本操作的实现顺序栈基本操作的实现2)顺序栈的出栈操作顺序栈的出栈操作 pop()的实现（算法的实现（算法 3.2)(1)操作要求：操作要求：将栈顶元素从栈中移去，并返回被移将栈顶元素从栈中移去，并返回被移去的栈顶元素值。去的栈顶元素值。a0a1an-1 an-2top(2)(2)算法步骤：算法步骤：算法步骤：算法步骤：2)顺序栈的出栈操作顺序栈的出栈操作 pop()的实现（算法的实现（算法 3.2)a）若栈空，则返回空值）若栈空，则返回空值 b)若栈不空，则移去栈顶元素并返回其值若栈不空，则移去栈顶元素并返回其值if(top=0)return null;a1a2an an-1top或或 if(isEmpty()return null;return stackElemtop;return stackElem-top;top=top-1;(3)(3)算法算法算法算法public Object pop()throws Exception /算法3.2结束if(isEmpty()return null;elsereturn stackElem-top;2)顺序栈的出栈操作顺序栈的出栈操作 pop()的实现（算法的实现（算法 3.2)时间复杂度为：时间复杂度为：O(1)3.1.4 3.1.4 链栈及其基本操作的实现链栈及其基本操作的实现1.链栈链栈 栈的链式存储结构称为链栈，是运算受限的栈的链式存储结构称为链栈，是运算受限的单链表，其插入和删除操作仅限制在链表的表头单链表，其插入和删除操作仅限制在链表的表头位置上进行，故链栈没有必要象单链表一样附加位置上进行，故链栈没有必要象单链表一样附加头结点，栈顶指针即为链表的头指针。头结点，栈顶指针即为链表的头指针。topa0an-1注意注意:链栈中链栈中指针的方向指针的方向an-2栈底栈底3.1.4 3.1.4 链栈及其基本操作的实现链栈及其基本操作的实现1.链栈链栈思考思考栈空条件栈空条件?栈的长度栈的长度?栈顶元素栈顶元素?如下问题如何描述如下问题如何描述?top=null需从栈顶开始沿着需从栈顶开始沿着nextnext指针依次对结点逐个进指针依次对结点逐个进行点数才能确定。行点数才能确定。top.getData()topa0an-1an-23.1.4 3.1.4 链栈及其基本操作的实现链栈及其基本操作的实现2.链栈类的描述链栈类的描述(书中书中P73-74)P73-74)Import cho2.Node;public class LinkStack implements IStack private Node top;/栈置空函数栈置空函数 public void clear()/判判空函数空函数public boolean isEmpty()top=null;return top=null;2.链栈类的描述链栈类的描述(书中书中P73-74)public class LinkStack implements IStack /求栈数据元素个数函数求栈数据元素个数函数 public int length()/取栈顶元素的函数取栈顶元素的函数 public Object peek()if(!isEmpty()/栈非空栈非空 return top.getData();/栈顶元素栈顶元素else return null;2.链栈类的描述链栈类的描述(书中书中P73-74)public class LinkStack implements IStack /入栈操作的函数入栈操作的函数public void push(Object x)/出栈操作的函数出栈操作的函数public void pop()/输出函数输出函数(从栈顶到栈底从栈顶到栈底)public void display()Node p=top;System.out.print(p.getData().tostring()+)p=p.getNext();while(p!=null)03.链栈基本操作的实现链栈基本操作的实现1)求链栈的长度操作求链栈的长度操作 length()的实现的实现(1)操作要求：操作要求：计算出链栈中所包含的数据元素的个计算出链栈中所包含的数据元素的个数并返回其值。数并返回其值。(2)方法方法 与求单链表长度的方法相同。与求单链表长度的方法相同。ppplength1 2 3211830754256topp4p5p6p(3)(3)算法算法算法算法public int length()/算法3.3结束Node p=top;int length=0;时间复杂度为：时间复杂度为：O(n)1)求链栈的长度操作求链栈的长度操作 length()的实现的实现(算法算法 3.3)while(p!=null)p=p.getNext();+length;3.链栈基本操作的实现链栈基本操作的实现2)链栈的入栈操作链栈的入栈操作 push(x)的实现（算法的实现（算法 3.4)(1)操作要求：操作要求：将数据域值为将数据域值为x x的新结点插入到链栈的栈顶，的新结点插入到链栈的栈顶，使其成为新的栈顶元素。使其成为新的栈顶元素。x1830754256toptopNode p=new Node(x);p.setNext(top);top=p;p(2)(2)算法算法算法算法public void push(object x)/算法3.4结束Node p=new Node(x);2)链栈的入栈操作链栈的入栈操作 push(x)的实现（算法的实现（算法 3.4)时间复杂度为：时间复杂度为：O(1)p.setNext(top);top=p;3.链栈基本操作的实现链栈基本操作的实现3)链栈的出栈操作链栈的出栈操作 pop()的实现（算法的实现（算法 3.5)(1)操作要求：操作要求：将首结点（或栈顶结点）从链栈中移去，将首结点（或栈顶结点）从链栈中移去，并返回该结点的数据域的值。并返回该结点的数据域的值。Node p=top;top=top.getNext()return(p.getData();211830754256topp(2)(2)算法算法算法算法public Object pop()/算法3.5结束3)链栈的出栈操作链栈的出栈操作 pop()的实现（算法的实现（算法 3.5)时间复杂度为：时间复杂度为：O(1)Node p=top;top=top.getNext()return(p.getData();if(isEmpty()return null;else3.1.5 3.1.5 栈的应用栈的应用例例1.分隔符匹配问题分隔符匹配问题例例2.大数加法问题大数加法问题例例3.表达式求值问题表达式求值问题例例4.栈与递归问题栈与递归问题【例例1 1】分隔符匹配问题分隔符匹配问题-问题分析问题分析 假设在表达式中（）或（/*/）等为正确正确的格式，（）或（）)或（）均为不正确不正确的格式。则则 检验分隔符是否匹配的方法可用检验分隔符是否匹配的方法可用“期待的急迫程度期待的急迫程度”这个概念来描述。这个概念来描述。Java Java程序中分隔符有圆、方、花括号程序中分隔符有圆、方、花括号和注释符和注释符“/*/*”和和“*/”。分析可能出现的分析可能出现的不匹配不匹配的情况的情况:l到来的右分隔符并非是所到来的右分隔符并非是所“期待期待”的；的；例如：考虑下列括号序列：例如：考虑下列括号序列：（）或（）或（）)或（或（）1 2 3 4 1 2 3 4 5 6 1 2 3 4 5l到来的是到来的是“不速之客不速之客”；l直到结束，也没有到来所直到结束，也没有到来所“期待期待”的括的括弧。弧。【例例1 1】分隔符匹配问题分隔符匹配问题-问题分析问题分析【例例1 1】分隔符匹配问题分隔符匹配问题-问题分析问题分析这三种情况对应到栈的操作即为：这三种情况对应到栈的操作即为：1 1和栈顶的左分隔符不相匹配；和栈顶的左分隔符不相匹配；2 2栈中并没有左分隔符等在那里；栈中并没有左分隔符等在那里；3 3栈中还有左分隔符没有等到和它栈中还有左分隔符没有等到和它相匹配的右括弧。相匹配的右括弧。算法的设计思想：算法的设计思想：1）凡出现左括弧，则进栈；）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空）凡出现右括弧，首先检查栈是否空 若栈空，则表明该若栈空，则表明该“右括弧右括弧”多余，多余，否则和栈顶元素比较，否则和栈顶元素比较，若相匹配，则若相匹配，则“左括弧出栈左括弧出栈”，否则表明不匹配。否则表明不匹配。3）表达式检验结束时，）表达式检验结束时，若栈空，则表明表达式中匹配正确，若栈空，则表明表达式中匹配正确，否则表明否则表明“左括弧左括弧”有余。有余。【例例1 1】分隔符匹配问题分隔符匹配问题-问题分析问题分析【例例1 1】分隔符匹配问题分隔符匹配问题-程序代码（程序代码（P77-78P77-78）public class Example3_1 private final int LEFT=0;/记录记录左左分隔符分隔符private final int RIGHT=1;/记录记录右右分隔符分隔符private final int OTHER=2;/记录其他字符记录其他字符Import java.util.Scanner;public int verifyFlag(String str)if(.equals(str)|.equals(str)|.equals(str)|/*.equals(str)/左分隔符左分隔符 return LEFT;else if().equals(str)|.equals(str)|.equals(str)|*/.equals(str)/右分隔符右分隔符 return RIGHT;else /其它的字符其它的字符 return OTHER;public class Example3_1 /检验左分隔符检验左分隔符str1和右分隔符和右分隔符str2是否匹配是否匹配public boolean matches(String str1,String str2)if(.equals(str1)&).equals(str2)|(.equals(str1)&.equals(str2)|(.equals(str1)&.equals(str2)|(/*.equals(str1)&*/.equals(str2)return true;else return false;【例例1 1】分隔符匹配问题分隔符匹配问题-程序代码（程序代码（P77-78P77-78）public class Example3_1 /检验串中分隔符是否匹配检验串中分隔符是否匹配private boolean isLegal(String str)throws Exception if(!.equals(str)&str!=null)SqStack S=new SqStack(100);int length=str.length();for(int i=0;i#3 *(7-2)4 *(7-2)5 37 *(-2)-(6 37 *(-2)7 372 *(-)遇）8 372-*()遇(9 372-*10 372-*结束 动画动画3-3-7【例例3 3】表达式求值表达式求值问题分析问题分析2.如何从后缀式求值？如何从后缀式求值？先找运算符，先找运算符，再找操作数再找操作数 例如：例如：a b c d e/f +a bd/ec-d/e(c-d/e)f动画动画3-3-6a b+(c-d/e)f【例例3 3】表达式求值表达式求值问题分析问题分析1)设立一个操作数栈；设立一个操作数栈；2)从左到右依次读入后缀表达式中的字符从左到右依次读入后缀表达式中的字符:若当前字符是操作数，则压入操作数栈。若当前字符是操作数，则压入操作数栈。后缀式求值的操作步骤为：后缀式求值的操作步骤为：若当前字符是运算符，则从栈顶弹出两若当前字符是运算符，则从栈顶弹出两个操作数参与运算，并将运算结果压入操个操作数参与运算，并将运算结果压入操作数栈内。作数栈内。动画动画3-3-6【例例3 3】表达式求值表达式求值程序代码程序代码Example3_3.javaExample3_3.java(书书P84-85)P84-85)【例例4 4】栈与递归问题栈与递归问题 在程序设计中，经常会碰到多个函在程序设计中，经常会碰到多个函数的嵌套调用。和汇编程序设计中主程数的嵌套调用。和汇编程序设计中主程序和子程序之间的链接和信息交换相类序和子程序之间的链接和信息交换相类似，在高级语言编制的程序中，调用函似，在高级语言编制的程序中，调用函数和被调用函数之间的链接和信息交换数和被调用函数之间的链接和信息交换也是由编译程序通过栈来实施的。也是由编译程序通过栈来实施的。【例例4 4】栈与递归问题栈与递归问题 1.将所有的实在参数、返回地址将所有的实在参数、返回地址等等信息信息传递给被调用函数传递给被调用函数保存保存；2.为被调用函数的局部变量为被调用函数的局部变量分配分配存储区存储区；3.将将控制转移控制转移到被调用函数的入到被调用函数的入口。口。当在一个函数的运行期间调用另一当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，个函数时，在运行该被调用函数之前，需先完成三项任务：需先完成三项任务：【例例4 4】栈与递归问题栈与递归问题 1.保存保存被调函数的被调函数的计算结果计算结果；2.释放释放被调函数的被调函数的数据区数据区；3.依照被调函数保存的返回地依照被调函数保存的返回地址将址将控制转移控制转移到调用函数。到调用函数。从被调用函数返回调用函数之前，从被调用函数返回调用函数之前，应该完成下列三项任务：应该完成下列三项任务：【例例4 4】栈与递归问题栈与递归问题多个函数嵌套调用的规则是：多个函数嵌套调用的规则是：此时的内存管理实行此时的内存管理实行“栈式管理栈式管理”后调用先返回后调用先返回！例如：例如：void main()void a()void b()a();b();/main /a /b函数函数a的数据区的数据区函数函数b的数据区的数据区Main的数据区的数据区【例例4 4】栈与递归问题栈与递归问题递归工作栈：递归工作栈：递归过程执行过程中占用的递归过程执行过程中占用的 数据区。数据区。递归工作记录：递归工作记录：每一层的递归参数合成每一层的递归参数合成 一个记录。一个记录。当前活动记录：当前活动记录：栈顶记录指示当前层的栈顶记录指示当前层的 执行情况。执行情况。当前环境指针：当前环境指针：递归工作栈的栈顶指针。递归工作栈的栈顶指针。递归函数执行的过程可视为递归函数执行的过程可视为同一函数同一函数进进行嵌套调用，例如：行嵌套调用，例如：【例例4 4】栈与递归问题栈与递归问题汉诺塔问题描述汉诺塔问题描述 n n阶汉诺塔问题：假设有三个分别命名为阶汉诺塔问题：假设有三个分别命名为X X，Y Y和和Z Z的塔座，在塔座的塔座，在塔座X X上插有上插有n n个直径大小各个直径大小各不相同，且从小到大编号为不相同，且从小到大编号为1 1、2 2、n n的圆的圆盘。现要求将塔座盘。现要求将塔座X X上的上的n n个圆盘借助塔座个圆盘借助塔座Y Y移至移至塔座塔座Z Z上，并仍按同样顺序叠排。圆盘移动时必上，并仍按同样顺序叠排。圆盘移动时必须遵循下列规则：须遵循下列规则：每次只能移动一个圆盘；每次只能移动一个圆盘；圆盘可以插在圆盘可以插在X X，Y Y和和Z Z中的任何一个塔座中的任何一个塔座上；上；任何时刻都不能将一个较大的圆盘压在任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。较小的圆盘之上。【例例4 4】栈与递归问题栈与递归问题汉诺塔问题汉诺塔问题public void hanoi(int n,char x,char y,char z)/将塔座x上按直径由小到大且至上而下编号为1至n的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1 2 if(n=1)3 move(x,1,z);/将编号为的圆盘从x移到z4 else 5 hanoi(n-1,x,z,y);/将x上编号为至n-1的 /圆盘移到y,z作辅助塔6 move(x,n,z);/将编号为n的圆盘从x移到z7 hanoi(n-1,y,x,z);/将y上编号为至n-1的 /圆盘移到z,x作辅助塔8 9 【例例4 4】栈与递归问题栈与递归问题汉诺塔问题汉诺塔问题public void hanoi(int n,char x,char y,char z)1 2 if(n=1)3 move(x,1,z);4 else 5 hanoi(n-1,x,z,y);6 move(x,n,z);7 hanoi(n-1,y,x,z);8 9【例例4】汉诺塔问题汉诺塔问题程序代码程序代码Example3_4.javaExample3_4.java(书书P86-87)P86-87)3.2.1 3.2.1 队列的概念队列的概念(1)(1)队列是只允许在表的一端进行插入，而在表队列是只允许在表的一端进行插入，而在表 的另一端进行删除操作的一种特殊线性表。的另一端进行删除操作的一种特殊线性表。允许插入的一端称为允许插入的一端称为“队尾队尾”，允许删除的，允许删除的一一 端称为端称为“队首队首”。(2)栈是栈是“先进先出先进先出”的线性表（的线性表（FIFO）或）或 “后进后出后进后出”的线性表（的线性表（LILO）a0 a1 a2 an-1队首队首队尾队尾入队入队出队出队3.2.2 3.2.2 队列的抽象数据类型描述队列的抽象数据类型描述 clear()1 1）队列的置空操作：）队列的置空操作：isEmpty()2 2）队列的判空操作：）队列的判空操作：length()3）求队列的长度：）求队列的长度：4）取队首元素操作：）取队首元素操作：5）入队操作：）入队操作：peek()offer(x)6）出队操作：）出队操作：poll()1.1.基本操作基本操作3.1.2 3.1.2 栈的抽象数据类型描述栈的抽象数据类型描述 2.2.队列的抽象数据类型的队列的抽象数据类型的JavaJava接口描述接口描述public interface IQueue public void clear();public boolean isEmpty();public int length();public Object peek();public void offer(Object x)throws Exception;public Object popll();实现此接口的方法有两种实现此接口的方法有两种:顺序队列顺序队列链式队列链式队列3.2.3 3.2.3 顺序队列及其基本操作的实现顺序队列及其基本操作的实现1.顺序队列顺序队列非空队列非空队列空队列空队列a0a1an-1 rear(队尾指针)maxSize-1queueElemfront(队首指针)0 1 n-1frontstackElemrear maxSize-10 1 2 3.1.3 3.1.3 顺序栈及其基本操作的实现顺序栈及其基本操作的实现1.顺序队列顺序队列思考思考队空条件队空条件?队列满条件队列满条件?如下问题如何描述如下问题如何描述?front=rearrear=queueElem.length入队入队offer(x):queueElemrear+=x;出队出队poll():return queueElem front+;队首元素队首元素?queueElemfront队尾元素队尾元素?queueElemrear-13.2.3 3.2.3 顺序栈及其基本操作的实现顺序栈及其基本操作的实现1.顺序队列顺序队列 序号值：序号值：0 1 2 3 4 5a0a1a3a3a4假溢出现象假溢出现象maxSize=6a5front front front front frontrearrear3.2.3 3.2.3 顺序栈及其基本操作的实现顺序栈及其基本操作的实现2.循环顺序队列循环顺序队列 将顺序队列看成是首尾相联的队列。将顺序队列看成是首尾相联的队列。动画动画3-3-133.2.3 3.2.3 顺序栈及其基本操作的实现顺序栈及其基本操作的实现2.循环顺序队列循环顺序队列假设：假设：maxSize=6循环队空条件：循环队空条件：循环队满条件：循环队满条件：front=rearfront=rear队空与队满的条件相同队空与队满的条件相同,无法判断无法判断,怎么办？怎么办？054321 frontreara0a1a2a3a4a53.2.3 3.2.3 顺序栈及其基本操作的实现顺序栈及其基本操作的实现2.循环顺序队列循环顺序队列 1.1.设一个标志变量设一个标志变量flagflag并置初值为并置初值为0,0,每当入队操作成功后就置每当入队操作成功后就置flag=1flag=1；每当；每当出队操作成功后就置出队操作成功后就置flag=0 flag=0。解决方法有解决方法有3 3种：种：循环队空条件：循环队空条件：循环队满条件：循环队满条件：front=rear&flag=0front=rear&flag=13.2.3 3.2.3 顺序栈及其基本操作的实现顺序栈及其基本操作的实现2.循环顺序队列循环顺序队列 2.2.设置一个计数变量设置一个计数变量numnum并置初值为并置初值为0,0,每当入队操作成功后每当入队操作成功后numnum加加1 1；每当出；每当出队操作成功后队操作成功后numnum减减1 1。解决方法有解决方法有3 3种：种：循环队空条件：循环队空条件：循环队满条件：循环队满条件：num=0或或front=rear&num=0num=queueElem.length或或front=rear&num03.2.3 3.2.3 顺序栈及其基本操作的实现顺序栈及其基本操作的实现2.循环顺序队列循环顺序队列3.3.少用一个元素空间：如下图少用一个元素空间：如下图循环队空条件：循环队空条件：循环队满条件：循环队满条件：front=rear（rear+1）%queueElem.length =front054321 frontreara1a2a3a4a5空空解决方法有解决方法有3 3种：种：3.2.3 3.2.3 顺序栈及其基本操作的实现顺序栈及其基本操作的实现3.循环顺序队列类的描述循环顺序队列类的描述(书中书中P91)P91)public class CircleSqQueue implements IQueue private Object queueElem;private int front;private int rear;/构造一个容量为构造一个容量为maxSize的空循环队列函数的空循环队列函数 public CircleSqQueue(int maxSize)/队列置空函数队列置空函数 public void clear()queueElem=new ObjectmaxSize;front=rear=0;front=rear=0;3.循环顺序队列类的描述循环顺序队列类的描述(见书见书P91)P91)public class CircleSqQueue implements IQueue public boolean isEmpty()/判判空函数空函数public int length()/求队列当前长度函数求队列当前长度函数 public Object peek()/读取队首元素的函数读取队首元素的函数 return front=rear;return (rear-front+queueElem.length)%queueElem.length);if(front=rear)/队列为队列为空空 else return null;return queueElemfront;/返回队首返回队首元素元素public class CircleSqQueue implements IQueue /循环顺序队列类的描述结束循环顺序队列类的描述结束/入队操作的函数入队操作的函数public void offer(Object x)/出队操作的函数出队操作的函数public void poll()/输出函数输出函数(从队首到队尾从队首到队尾)public void display()3.循环顺序队列类的描述循环顺序队列类的描述(见书见书P91)P91)if(!isEmpty()else for(int i=front;i!=rear;i=(i+1)%queueElem.length)System.out.print(queueElemi.toString()+);System.out.println(此队列为空此队列为空);4.循环顺序队列基本操作的实现循环顺序队列基本操作的实现1)循环顺序队列的入队操作循环顺序队列的入队操作 offer(x)的实现（算法的实现（算法 3.6)将新元素将新元素x插入到一个循环队插入到一个循环队列的队尾。列的队尾。操作思路：操作思路：操作思路：操作思路：基本要求：基本要求：基本要求：基本要求：rear054321fronta3a4a5x 1）若）若队满队满，则抛出异常后结束操作；，则抛出异常后结束操作；2）若队非满，则将）若队非满，则将x进队，尾指针加进队，尾指针加1queueElemrear=x;/x入队入队操作步骤：操作步骤：if (rear+1)%queueElem.length=front)throw new Exception(队列已满队列已满);4.循环顺序队列基本操作的实现循环顺序队列基本操作的实现1)循环顺序队列的入队操作循环顺序队列的入队操作 offer(x)的实现（算法的实现（算法 3.6)rear=(rear+1)%queueElem.length;public void offer(Object x)throws Exception /算法3.6结束if(rear+1)%queueElem.length=front)throw new Exception(“队列已满队列已满);else queueElemrear=x;rear=(rear+1)%queueElem.length;时间复杂度为：时间复杂度为：O(1)算法：算法：4.循环顺序队列基本操作的实现循环顺序队列基本操作的实现1)循环顺序队列的入队操作循环顺序队列的入队操作 offer(x)的实现（算法的实现（算法 3.6)2)循环顺序队列的出队操作循环顺序队列的出队操作poll()的实现（算法的实现（算法 3.7)4.循环顺序队列基本操作的实现循环顺序队列基本操作的实现基本要求：基本要求：操作思路：操作思路：将队首元素删除，并返回其值。将队首元素删除，并返回其值。a5front021054reara6a7 1）若）若队空队空，则返回空值；，则返回空值；2）若队非空，则返回队首元素且首指针加）若队非空，则返回队首元素且首指针加1Object t=queueElemfront /读取队首元素读取队首元素操作步骤：操作步骤：if (front=rear)return null;4.循环顺序队列基本操作的实现循环顺序队列基本操作的实现front=(front+1)%queueElem.length;2)循环顺序队列的出队操作循环顺序队列的出队操作poll()的实现（算法的实现（算法 3.7)return t;public Object poll()/算法3.7结束if(front=rear)return null;else Object t=queueElemfront;front=(front+1)%queueElem.length;return t;时间复杂度为：时间复杂度为：O(1)算法：算法：4.循环顺序队列基本操作的实现循环顺序队列基本操作的实现2)循环顺序队列的出队操作循环顺序队列的出队操作poll()的实现（算法的实现（算法 3.7)3.2.4 3.2.4 链队列及其基本操作的实现链队列及其基本操作的实现1.链队列链队列 队列的链式存储结构称为链队列，其链式存队列的链式存储结构称为链队列，其链式存储结构在此用不带头结点的单链表来实现储结构在此用不带头结点的单链表来实现.frontan-1a0a1 rear队首指针队首指针队尾指