第3章 栈与队列(java版)

1、第三章第三章 栈与队列栈与队列第三章第三章 栈栈 与与 队队 列列3.2 队列队列3.1 栈栈3.4 栈与队列的综合应用举例栈与队列的综合应用举例3.3 栈与队列的比较栈与队列的比较第三章第三章 栈栈 与与 队队 列列重点：重点：u栈、队列的特点；栈、队列的特点；u栈、队列基本操作的实现算法栈、队列基本操作的实现算法难点：难点：u栈、队列的应用栈、队列的应用第三章第三章 栈栈 与与 队队 列列 通常称，栈和队列是限定插入插入和删除只能删除只能在表的“端点端点”进行的线性表。 线性表线性表 栈栈 队列队列 Insert(i, x) Insert(n, x) Insert(n, x) 0in De

2、lete(i) Delete(n-1) Delete(0) 0in-1 栈和队列是两种栈和队列是两种操作受限操作受限的的线性线性表表，是两种常用的数据类型。，是两种常用的数据类型。3.1 栈栈3.1.1 3.1.1 栈的概念栈的概念a0 a1 a2 an-1进进出出(2) 栈栈是是“后进先出后进先出”的线性表（的线性表（LIFO）或）或 “先先 进后出进后出”的线性表（的线性表（FILO）3.1 栈栈3.1.1 3.1.1 栈的概念栈的概念 如下图所示的是铁路调度站形象地如下图所示的是铁路调度站形象地表示栈的表示栈的“后进先出后进先出”特点。特点。3.1 栈栈3.1.1 3.1.1 栈的概念栈

3、的概念 设有编号为设有编号为1 1，2 2，3 3，4 4的四辆的四辆列车，顺序进一个栈式结构的站台列车，顺序进一个栈式结构的站台，具体写出这四辆列车开出车站的，具体写出这四辆列车开出车站的所有可能的顺序。所有可能的顺序。3.1 栈栈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、

4、2、4、1；13）3、4、2、1； 3.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 栈栈3.1.2 3.1.2 栈的抽象数据类型描述栈的抽象数据类型描述 2. 2.栈的抽象数据类型的栈的抽象数据类型的JavaJava接口描述接口描述pu

5、blic interface IStackpublic void clear();public boolean isEmpty();public int length();public Object peek();public void push(Object x) throws Exception;public Object pop();实现此接口的方法有两种实现此接口的方法有两种: 顺序栈顺序栈链栈链栈3.1 栈栈3.1.3 3.1.3 顺序栈及其基本操作的实现顺序栈及其基本操作的实现1. 顺序栈顺序栈非空栈非空栈空栈空栈a0a1an-1 top=n stackElem maxSize-1

6、0 1 n-1 top=0stackElem maxSize-10 1 2 3.1 栈栈3.1.3 3.1.3 顺序栈及其基本操作的实现顺序栈及其基本操作的实现1. 顺序栈顺序栈思考思考栈空条件栈空条件?栈满条件栈满条件?栈的长度栈的长度?栈顶元素栈顶元素?如下问题如何描述如下问题如何描述?top=0top=stackElem.lengthtopstackElemtop-1a0a1an-1 top=n stackElem 0 1 n-13.1 栈栈3.1.3 3.1.3 顺序栈及其基本操作的实现顺序栈及其基本操作的实现2.2.顺序栈类的描述顺序栈类的描述( (书书P71-P71-与与P33P3

7、3顺序表类对照学习顺序表类对照学习) )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;3.1 栈栈2. 顺序栈类的描述顺序栈类的描述( (见教材见教材P71)P71)public class SqStack impl

8、ements IStack / / 栈栈判判空空public boolean isEmpty( ) / / 求栈数据元素个数函数求栈数据元素个数函数 public int length( ) / / 取栈顶元素的函数取栈顶元素的函数 public Object peek ( ) return top= 0;return top;if (!isEmpty() / / 栈非空栈非空return stackElemtop-1; / / 栈顶元素栈顶元素 elsereturn null;3.1 栈栈2. 顺序栈类的描述顺序栈类的描述( (见教材见教材P71)P71)public class SqSta

9、ck 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 栈栈3. 顺序栈基本操作的实现顺序栈基本操作的实现1)顺序栈的入栈操作顺序栈的入栈操作 push (x)的实现（算法的实现（算

10、法 3.1)插入元素插入元素x使其成为顺序栈中新的栈使其成为顺序栈中新的栈顶元素。顶元素。 x a0a1an-1 toptop3.1 栈栈 a.判断顺序栈是否为满，若满则抛出异常判断顺序栈是否为满，若满则抛出异常 b.若栈不满，则若栈不满，则将新元素将新元素x 压入栈顶，并修压入栈顶，并修正栈顶指针正栈顶指针 if (top = stackElem.length) throw new Exception(栈已满栈已满) 1)顺序栈的入栈操作顺序栈的入栈操作 push (x)的实现（算法的实现（算法 3.1)statckElemtop+=xstatckElemtop=x;top=top+1;3.

11、1 栈栈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.1 栈栈3. 顺序栈基本操作的实现顺序栈基本操作的实现2)顺序栈的出栈操作顺序栈的出栈操作 pop ( )的实现（算法的实现（算法 3.2) 将栈顶元素从栈中移去，并返回被移将栈顶元素从栈中移去，并

12、返回被移去的栈顶元素值。去的栈顶元素值。 a0a1an-1 an-2top3.1 栈栈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.1 栈栈public Object pop () throws Exce

13、ption /算法3.2结束if (isEmpty() ) return null;elsereturn stackElem-top;2) 顺序栈的出栈操作顺序栈的出栈操作 pop ()的实现（算法的实现（算法 3.2)时间复杂度为：时间复杂度为：O(1)3.1 栈栈3.1.4 3.1.4 链栈及其基本操作的实现链栈及其基本操作的实现1. 链栈链栈 栈的链式存储结构称为栈的链式存储结构称为链栈链栈，是运算受限，是运算受限的单链表，其插入和删除操作仅限制在的单链表，其插入和删除操作仅限制在链表的链表的表头位置上表头位置上进行，故链栈没有必要象单链表一进行，故链栈没有必要象单链表一样附加头结点，样

14、附加头结点，栈顶指针栈顶指针即为链表的即为链表的头指针头指针。 topa0an-1注意注意: : 链栈中链栈中指针的方向指针的方向an-2栈底栈底3.1 栈栈3.1.4 3.1.4 链栈及其基本操作的实现链栈及其基本操作的实现1. 链栈链栈思考思考栈空条件栈空条件?栈的长度栈的长度?栈顶元素栈顶元素?如下问题如何描述如下问题如何描述?top=null需从栈顶开始沿着需从栈顶开始沿着nextnext指针依次对结点逐个进指针依次对结点逐个进行点数才能确定。行点数才能确定。top.data topa0an-1an-23.1 栈栈3.1.4 3.1.4 链栈及其基本操作的实现链栈及其基本操作的实现2.

15、 链栈类的描述链栈类的描述( (书中书中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;3.1 栈栈2. 链栈类的描述链栈类的描述(书中书中P73-74)public class LinkStack implements IStack / / 求栈数据元素个数函数求栈数

16、据元素个数函数 public int length( ) / / 取栈顶元素的函数取栈顶元素的函数 public Object peek ( ) if (!isEmpty() / 栈非空栈非空 return top.data; / 栈顶元素栈顶元素else return null;3.1 栈栈2. 链栈类的描述链栈类的描述(书中书中P73-74)public class LinkStack implements IStack / / 入栈操作的函数入栈操作的函数public void push( Object x) / / 出栈操作的函数出栈操作的函数public void pop ( ) /

17、 / 输出函数输出函数( (从栈顶到栈底从栈顶到栈底) )public void display () Node p=top;System.out.print(p.data.tostring( )+ )p=p.next;while(p!=null) 3.1 栈栈03. 链栈基本操作的实现链栈基本操作的实现1) 求链栈的长度操作求链栈的长度操作 length ()的实现的实现 计算出链栈中所包含的数据元素的个计算出链栈中所包含的数据元素的个数并返回其值。数并返回其值。 与求单链表长度的方法相同。与求单链表长度的方法相同。 ppplength1 2 3211830754256topp4p5p6p3

18、.1 栈栈public int length ( ) /算法3.3结束Node p = top; int length = 0;时间复杂度为：时间复杂度为：O(n)1) 求链栈的长度操作求链栈的长度操作 length ()的实现的实现(算法算法 3.3)while (p != null) p = p.next; +length; 3.1 栈栈3. 链栈基本操作的实现链栈基本操作的实现2) 链栈的入栈操作链栈的入栈操作 push (x )的实现（算法的实现（算法 3.4) 将数据域值为将数据域值为x x的新结点插入到链栈的栈顶，的新结点插入到链栈的栈顶，使其成为新的栈顶元素。使其成为新的栈顶元素

19、。 x1830754256toptopNode p = new Node(x); p.next=top; top = p; p3.1 栈栈public void push (object x) /算法3.4结束Node p = new Node(x); 2) 链栈的入栈操作链栈的入栈操作 push (x )的实现（算法的实现（算法 3.4)时间复杂度为：时间复杂度为：O(1)p.next=top; top = p; 3.1 栈栈3. 链栈基本操作的实现链栈基本操作的实现3) 链栈的出栈操作链栈的出栈操作 pop ( )的实现（算法的实现（算法 3.5) 将首结点（或栈顶结点）从链栈中移去，将首

20、结点（或栈顶结点）从链栈中移去，并返回该结点的数据域的值。并返回该结点的数据域的值。Node p = top; top=top.next;return (p.data); 211830754256topp3.1 栈栈public Object pop ( ) /算法3.5结束3) 链栈的出栈操作链栈的出栈操作 pop ( )的实现（算法的实现（算法 3.5)时间复杂度为：时间复杂度为：O(1)Node p = top; top=top.next; return (p.data); if (isEmpty() return null;else3.1 栈栈3.1.5 3.1.5 栈的应用栈的应用例

21、例1. 分隔符匹配问题分隔符匹配问题例例2. 大数加法问题大数加法问题例例3. 表达式求值问题表达式求值问题例例4. 栈与递归问题栈与递归问题3.1 栈栈【例例1 1】分隔符匹配问题分隔符匹配问题- -问题分析问题分析 假设在表达式中（）或（ /* */）等为正确正确的格式，（ ）或（）)或（ ）均为不正确不正确的格式。则则 检验分隔符是否匹配检验分隔符是否匹配的方法可用的方法可用“期待的急迫程度期待的急迫程度”这个概念来描述。这个概念来描述。 Java Java程序中分隔符有圆、方、花括程序中分隔符有圆、方、花括号和注释符号和注释符“/ /* *”和和“* */ /”。3.1 栈栈分析可能出

22、现的分析可能出现的不匹配不匹配的情况的情况:l到来的右分隔符到来的右分隔符并非是所并非是所“期待期待”的；的；例如：考虑下列括号序列：例如：考虑下列括号序列：（ ）或或（ ）)或或（ ）1 2 3 4 1 2 3 4 5 6 1 2 3 4 5l到来的是到来的是“不速之客不速之客”；l直到结束，也没有到来直到结束，也没有到来所所“期待期待”的括的括弧。弧。【例例1 1】分隔符匹配问题分隔符匹配问题- -问题分析问题分析3.1 栈栈【例例1 1】分隔符匹配问题分隔符匹配问题- -问题分析问题分析这这三种情况三种情况对应到栈的操作即为：对应到栈的操作即为： 1 1和栈顶的左分隔符不相匹配；和栈顶的

23、左分隔符不相匹配； 2 2栈中并没有左分隔符等在那里；栈中并没有左分隔符等在那里； 3 3栈中还有左分隔符没有等到和它栈中还有左分隔符没有等到和它相匹配的右括弧。相匹配的右括弧。3.1 栈栈1）凡出现）凡出现左括弧左括弧，则，则进栈进栈；2）凡出现）凡出现右括弧右括弧，首先检查栈是否空，首先检查栈是否空 若若栈空栈空，则表明该，则表明该“右括弧右括弧”多余多余， 否则和栈顶元素比较，否则和栈顶元素比较， 若若相匹配相匹配，则，则“左括弧出栈左括弧出栈” ， 否则否则表明表明不匹配不匹配。3）表达式检验）表达式检验结束结束时，时， 若若栈空栈空，则表明表达式中，则表明表达式中匹配正确匹配正确，

24、否则否则表明表明“左括弧左括弧”有余有余。【例例1 1】分隔符匹配问题分隔符匹配问题- -问题分析问题分析3.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 verifyFla

25、g(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;3.1 栈栈public class Example3_1 / 检验左分隔符检验左分隔符str1和右分隔符和右分隔符str2是否匹配是否匹配publ

26、ic 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）3.1 栈栈public class Example

27、3_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-

28、73.1 栈栈【例例3 3】表达式求值表达式求值问题分析问题分析先找运算符，先找运算符， 再找操作数再找操作数 例如：例如： a b c d e / f +a bd/ec-d/e(c-d/e) f动画动画3-3-6a b+(c-d/e) f3.1 栈栈【例例3 3】表达式求值表达式求值问题分析问题分析1) 设立一个设立一个操作数栈；操作数栈；2) 从左到右依次读入后缀表达式中的字符从左到右依次读入后缀表达式中的字符:若若当前字符当前字符是操作数是操作数，则压入操作数栈。，则压入操作数栈。后缀式求值的操作步骤为：后缀式求值的操作步骤为：若若当前字符当前字符是运算符是运算符，则从栈顶弹出两，则从栈

29、顶弹出两个操作数参与运算，并将运算结果压入操个操作数参与运算，并将运算结果压入操作数栈内。作数栈内。动画动画3-3-63.1 栈栈【例例3 3】表达式求值表达式求值程序代码程序代码Example3_3.javaExample3_3.java3.1 栈栈【例例4 4】栈与递归问题栈与递归问题 在程序设计中，经常会碰到多个函在程序设计中，经常会碰到多个函数的嵌套调用。和汇编程序设计中主程数的嵌套调用。和汇编程序设计中主程序和子程序之间的链接和信息交换相类序和子程序之间的链接和信息交换相类似，在高级语言编制的程序中，调用函似，在高级语言编制的程序中，调用函数和被调用函数之间的链接和信息交换数和被调用

30、函数之间的链接和信息交换也是由编译程序通过也是由编译程序通过栈栈来实施的。来实施的。3.1 栈栈【例例4 4】栈与递归问题栈与递归问题 当在一个函数的运行期间当在一个函数的运行期间调用另一调用另一个函数个函数时，在时，在运行该被调用函数之前运行该被调用函数之前，需先完成三项任务：需先完成三项任务：3.1 栈栈【例例4 4】栈与递归问题栈与递归问题3.1 栈栈【例例4 4】栈与递归问题栈与递归问题多个函数嵌套调用的规则是：多个函数嵌套调用的规则是：此时的内存管理实行此时的内存管理实行“栈式管理栈式管理”后调用先返回后调用先返回 ！例如：例如：void main( ) void a( ) void

31、 b( ) a( ); b( ); /main / a / b函数函数a的数据区的数据区函数函数b的数据区的数据区Main的数据区的数据区3.1 栈栈【例例4 4】栈与递归问题栈与递归问题递归工作栈：递归工作栈：递归过程执行过程中占用的递归过程执行过程中占用的 数据区。数据区。递归工作记录：递归工作记录：每一层的递归参数合成每一层的递归参数合成 一个记录。一个记录。当前活动记录：当前活动记录：栈顶记录指示当前层的栈顶记录指示当前层的 执行情况。执行情况。当前环境指针：当前环境指针：递归工作栈的栈顶指针。递归工作栈的栈顶指针。 递归函数执行的过程可视为递归函数执行的过程可视为同一函数同一函数进进

32、行嵌套调用，例如：行嵌套调用，例如：3.1 栈栈【例例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上，并仍按同样顺序叠排。圆盘移动时必上，并仍按同样顺序叠排。圆盘移动时必须遵循下列规则：须遵循下列规则： 每次只能移动一个圆

33、盘；每次只能移动一个圆盘； 圆盘可以插在圆盘可以插在X X，Y Y和和Z Z中的任何一个塔中的任何一个塔座上；座上； 任何时刻都不能将一个较大的圆盘压在任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。较小的圆盘之上。3.1 栈栈【例例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(

34、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 3.1 栈栈【例例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

35、, y, x, z); 8 9 3.1 栈栈【例例4】汉诺塔问题汉诺塔问题程序代码程序代码Example3_4.javaExample3_4.java3.2 队列队列3.2.1 3.2.1 队列的概念队列的概念队列队列是只允许在表的一端进行插入，而在表是只允许在表的一端进行插入，而在表 的另一端进行删除操作的一种的另一端进行删除操作的一种特殊线性表特殊线性表。 允许插入的一端称为允许插入的一端称为“队尾队尾”，允许删除的，允许删除的一一 端称为端称为“队首队首”。(2) 队列队列是是“先进先出先进先出”的线性表（的线性表（FIFO）或）或 “后进后出后进后出”的线性表（的线性表（LILO）a0

36、 a1 a2 an-1队首队首队尾队尾入队入队出队出队3.2 队列队列3.2.2 3.2.2 队列的抽象数据类型描述队列的抽象数据类型描述 clear( )1 1）队列的置空操作：）队列的置空操作： isEmpty( )2 2）队列的判空操作：）队列的判空操作： length( )3）求队列的长度：）求队列的长度：4）取队首元素操作：）取队首元素操作：5）入队操作：）入队操作：peek( )offer( x )6）出队操作：）出队操作：poll ( ) 1. 1.基本操作基本操作3.2 队列队列3.1.2 3.1.2 栈的抽象数据类型描述栈的抽象数据类型描述 2. 2.队列的抽象数据类型的队列

37、的抽象数据类型的JavaJava接口描述接口描述public interface IQueuepublic void clear();public boolean isEmpty();public int length();public Object peek();public void offer(Object x) throws Exception;public Object popll();实现此接口的方法有两种实现此接口的方法有两种: 顺序队列顺序队列链式队列链式队列3.2 队列队列3.2.3 3.2.3 顺序队列及其基本操作的实现顺序队列及其基本操作的实现1. 顺序队列顺序队列非空队

38、列非空队列空队列空队列a0a1an-1 rear(队尾指针) maxSize-1queueElemfront(队首指针)0 1 n-1frontqueueElemrear maxSize-10 1 2 3.2 队列队列3.1.3 3.1.3 顺序栈及其基本操作的实现顺序栈及其基本操作的实现1. 顺序队列顺序队列思考思考队空条件队空条件?队列满条件队列满条件?如下问题如何描述如下问题如何描述?front=rearrear=queueElem.length入队入队offer(x): queueElemrear+=x;出队出队poll ( ): return queueElem front+;队首元

39、素队首元素?queueElemfront队尾元素队尾元素?queueElemrear-13.2 队列队列3.2.3 3.2.3 顺序栈及其基本操作的实现顺序栈及其基本操作的实现1. 顺序队列顺序队列 序号值：序号值：0 1 2 3 4 5a0a1a3a3a4假溢出假溢出现象现象maxSize=6a5front front front front frontrearrear3.2 队列队列3.2.3 3.2.3 顺序栈及其基本操作的实现顺序栈及其基本操作的实现2. 循环顺序队列循环顺序队列 将顺序队列看成是首尾相联的队列。将顺序队列看成是首尾相联的队列。动画动画3-3-133.2 队列队列3.2

40、.3 3.2.3 顺序栈及其基本操作的实现顺序栈及其基本操作的实现2. 循环顺序队列循环顺序队列假设：假设：maxSize=6循环队空条件：循环队空条件：循环队满条件：循环队满条件：front=rearfront=rear队空与队满的条件相同队空与队满的条件相同, ,无法判断无法判断, ,怎么办？怎么办？054321 frontreara0a1a2a3a4a53.2 队列队列3.2.3 3.2.3 顺序栈及其基本操作的实现顺序栈及其基本操作的实现2. 循环顺序队列循环顺序队列 1. 1.设一个标志变量设一个标志变量flagflag并置初值为并置初值为0,0, 每当入队操作成功后就置每当入队操作

41、成功后就置flag=1flag=1；每当；每当出队操作成功后就置出队操作成功后就置flag=0 flag=0 。循环队空条件：循环队空条件：循环队满条件：循环队满条件：front=rear&flag=0front=rear&flag=13.2 队列队列3.2.3 3.2.3 顺序栈及其基本操作的实现顺序栈及其基本操作的实现2. 循环顺序队列循环顺序队列 2. 2.设置一个计数变量设置一个计数变量numnum并置初值为并置初值为0,0,每当入队操作成功后每当入队操作成功后numnum加加1 1；每当出；每当出队操作成功后队操作成功后numnum减减1 1。循环队空条件：循环队空条

42、件：循环队满条件：循环队满条件：num=0或或front=rear& num=0num=queueElem.length或或front=rear&num03.2 队列队列3.2.3 3.2.3 顺序栈及其基本操作的实现顺序栈及其基本操作的实现2. 循环顺序队列循环顺序队列3. 3. 少用一个元素空间：如下图少用一个元素空间：如下图循环队空条件：循环队空条件：循环队满条件：循环队满条件：front=rear（rear+1）% queueElem.length = =front054321 frontreara0a1a2a3a4空空3.2 队列队列3.2.3 3.2.3 顺序栈及其

43、基本操作的实现顺序栈及其基本操作的实现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 Objectmax

44、Size;front=rear = 0; front=rear= 0; 3.2 队列队列3. 循环顺序队列类的描述循环顺序队列类的描述( (见书见书P91)P91)public class CircleSqQueue implements IQueue public boolean isEmpty( ) / 判判空函数空函数public int length( ) / / 求队列当前长度函数求队列当前长度函数 public Object peek ( ) / 读取队首元素的函数读取队首元素的函数 return front=rear;return (rear-front+queueElem.le

45、ngth)%queueElem.length;if (front=rear) / 队列为队列为空空elsereturn null ; return queueElemfront; / 返回队首返回队首元素元素3.2 队列队列public class CircleSqQueue implements IQueue /循环顺序队列类的描述结束循环顺序队列类的描述结束/ / 入队操作的函数入队操作的函数public void offer( Object x) / 出队操作的函数出队操作的函数public void poll ( ) / / 输出函数输出函数( (从队首到队尾从队首到队尾) )publ

46、ic 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(此队列为空此队列为空);3.2 队列队列4. 循环顺序队列基本操作的实现循环顺序队列基本操作的实现1)循环顺序队列的入队操作循环顺序队列的入队操作 offer (x)的实现（算法的实现（算法 3.

47、6) 将新元素将新元素x插入到一个循环队插入到一个循环队列的队尾。列的队尾。rear054321fronta3a4a5x3.2 队列队列 1）若）若，则抛出异常后结束操作；，则抛出异常后结束操作； 2）若队非满，则将）若队非满，则将x进队，尾指针加进队，尾指针加1queueElemrear = x; /x入队入队if (rear+1)%queueElem.length=front) throw new Exception(队列已满队列已满);4. 循环顺序队列基本操作的实现循环顺序队列基本操作的实现1)循环顺序队列的入队操作循环顺序队列的入队操作 offer (x)的实现（算法的实现（算法 3

48、.6)rear=(rear+1)% queueElem.length;3.2 队列队列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 (

49、x)的实现（算法的实现（算法 3.6)3.2 队列队列2)循环顺序队列的出队操作循环顺序队列的出队操作poll( )的实现（算法的实现（算法 3.7)4. 循环顺序队列基本操作的实现循环顺序队列基本操作的实现将队首元素删除，并返回其值。将队首元素删除，并返回其值。a5front021054reara6a73.2 队列队列 1）若）若，则返回空值；，则返回空值； 2）若队非空，则返回队首元素且首指针加）若队非空，则返回队首元素且首指针加1Object t=queueElemfront /读取队首元素读取队首元素if (front=rear) return null;4. 循环顺序队列基本操作的实

50、现循环顺序队列基本操作的实现front=(front+1)% queueElem.length;2)循环顺序队列的出队操作循环顺序队列的出队操作poll( )的实现（算法的实现（算法 3.7)return t;3.2 队列队列public Object poll ( ) /算法3.7结束if (front = rear) return null;else Object t = queueElemfront; front = (front + 1) % queueElem.length; return t; 时间复杂度为：时间复杂度为：O(1)4. 循环顺序队列基本操作的实现循环顺序队列基本操作

51、的实现2)循环顺序队列的出队操作循环顺序队列的出队操作poll( )的实现（算法的实现（算法 3.7)3.2 队列队列3.2.4 3.2.4 链队列及其基本操作的实现链队列及其基本操作的实现1. 链队列链队列 队列的链式存储结构称为队列的链式存储结构称为链队列链队列，其链式存，其链式存储结构在此用储结构在此用不带头结点不带头结点的单链表来实现的单链表来实现. . frontan-1a0a1 rear队首指针队首指针队尾指针队尾指针3.2 队列队列3.2.4 3.2.4 链队列及其基本操作的实现链队列及其基本操作的实现1. 链队列链队列思考思考队列空的条件队列空的条件? ?队列的长度队列的长度?

52、 ?队首元素队首元素? ?如下问题如何描述如下问题如何描述? ?front=null需从队首开始沿着需从队首开始沿着nextnext指针依次对结点逐个进指针依次对结点逐个进行点数才能确定。行点数才能确定。front.data队尾元素队尾元素? ?rear.data3.2 队列队列3.2.4 3.2.4 链队列及其基本操作的实现链队列及其基本操作的实现2. 链队列类的描述链队列类的描述( (书中书中P93-94)P93-94)import cho2.Node;public class LinkQueue implements IQueue private Node front; private

53、Node rear; / 队列置空函数队列置空函数 public void clear( ) / / 判判空函数空函数public boolean isEmpty( ) front=rear= null; return front= null;3.2 队列队列public class LinkQueue implements IQueue / / 求队列长度函数求队列长度函数public int length( ) 2. 链队列类的描述链队列类的描述( (书中书中P93-94)P93-94)Node p = front;int length = 0;while (p !=null) p = p

54、.next; /指针下移指针下移 +length; /计数器加计数器加1 return length;3.2 队列队列public class LinkQueue implements IQueue / / 取队首元素的函数取队首元素的函数 public Object peek ( ) 2. 链队列类的描述链队列类的描述( (书中书中P93-94)P93-94)if (!isEmpty() / 队列队列非空非空 elsereturn front.data; / 返回队首返回队首元素元素return null;3.2 队列队列public class LinkQueue implements I

55、Queue / / 入队操作的函数入队操作的函数public void push( Object x) / / 出队操作的函数出队操作的函数public void pop ( ) / / 输出函数输出函数( (从队首到队尾从队首到队尾) )public void display () 2. 链队列类的描述链队列类的描述( (书中书中P93-94)P93-94)Node p=front;while( p!=null ) System.out.print(p.data.tostring( )+ )p=p.next;3.2 队列队列3. 链队列基本操作的实现链队列基本操作的实现1) 链队列的入队操作

56、链队列的入队操作 offer(x )的实现（算法的实现（算法 3.8) 插入新元素插入新元素x x使其成为新的队尾元素。使其成为新的队尾元素。 1830754256frontrearNode p = new Node(x); rear.next; rear = p; rearxp a）产生新的结点）产生新的结点pb）将新结点插入链队的尾部（修改链）将新结点插入链队的尾部（修改链）队非空时队非空时: :队空时队空时: :front=rear = p; 3.2 队列队列public void offer (object x) /算法3.8结束 Node p = new Node(x); if (f

57、ront != null) / 队列非空队列非空 rear.next=p; rear = p; else front = rear = p; 时间复杂度为：时间复杂度为：O(1)3. 链队列基本操作的实现链队列基本操作的实现1) 链队列的入队操作链队列的入队操作 offer(x )的实现（算法的实现（算法 3.8)3.2 队列队列3. 链队列基本操作的实现链队列基本操作的实现2) 链队列的出队操作链队列的出队操作 poll()的实现的实现 移去队首元素并返回其值移去队首元素并返回其值1830754256frontrearif (front=null) return null; Node p=f

58、ront; front = front.next; a）若队列为空）若队列为空,则返回空值则返回空值b）若队列非空）若队列非空,则移去队首元素则移去队首元素p3.2 队列队列3. 链队列基本操作的实现链队列基本操作的实现2) 链队列的出队操作链队列的出队操作 poll()的实现的实现 移去队首元素并返回其值移去队首元素并返回其值1830754256frontrearpc) 若删除的是队尾元素，则修改队尾指针若删除的是队尾元素，则修改队尾指针if ( rear=p) rear=null;d) 返回队尾元素值返回队尾元素值return p.data;3.2 队列队列public Objext po

59、ll( ) Node p = new Node(x); if (front != null) / 队列非空队列非空 Node p=front; front=front.next; if (rear=p) rear=null; return p.data; else return null;时间复杂度为：时间复杂度为：O(1)3. 链队列基本操作的实现链队列基本操作的实现2) 链队列的出队操作链队列的出队操作 poll()的实现的实现3.2 队列队列【例例 】编程实现求解的素数环问题编程实现求解的素数环问题3.2.5 3.2.5 队列的应用队列的应用【问题描述】【问题描述】将将1 1n n的的

60、n n个自然数排列成个自然数排列成环形，使得每相邻两数之和为素数，从而构成环形，使得每相邻两数之和为素数，从而构成一个素数环。一个素数环。【方法方法】 先引入顺序表类先引入顺序表类SqlistSqlist和链队列类和链队列类LinkQueueLinkQueue，再创建，再创建SqlistSqlist类的一个对象类的一个对象L L作作为顺序表，用于存放素数环的数据元素；创建为顺序表，用于存放素数环的数据元素；创建LinkQueueLinkQueue类的一个对象类的一个对象Q Q，作为队列用于存放，作为队列用于存放还未加入到素数环中的自然数。还未加入到素数环中的自然数。3.2 队列队列【例例 】编程实现求解的素数环问题编程实现求解的素数环问题3.2.5 3.2.5 队