第3章
栈和队
列
在第2章当中通过对数组和链表相关知识的学习可以发现:数组和链表属于数据结构
当中最基本的物理结构,在具体业务场景中使用时,往往需要进一步地进行封装,简化其操
作方式,提升其操作效率。在对数组和链表进行高级封装的过程中,如果从元素的操作顺序
上加以约束,就能够得到两种逻辑结构:栈和队列。
在对栈和队列这两种逻辑结构进行具体实现的过程中,其底层既可以使用数组进行实
现,也可以使用链表进行实现。例如在Java语言的原生API中,对于栈结构的实现有Stack
类型,其内部与ArayList相似,都是使用数组进行封装的;对于队列结构的实现有
LinkedList类型,其内部使用双链表结构进行封装,6版本开始,LinkedList
但是从JDK1.
同样实现了栈结构的相关操作,可以作为栈结构的实现进行使用,所以从这一点看来,对于
栈和队列的学习重点应该放在两种结构的元素操作逻辑及相应的使用场景上。
本章内容的思维导图如图3-1所示。
图3-1 栈和队列章节思维导图
55
3.栈结构
1
3.1
栈结构概述
1.
栈结构的逻辑特点是元素后进先出(LastInFirstOut,LIFO )。可以将栈结构理解为
一个一端开口而另一端封闭的容器,在向容器中添加元素时,后加入的元素会“压住”先加入
的元素,只有将后加入的元素逐个退出栈结构,才能将先加入其中的元素取出,而元素加入、
退出栈结构的操作都是从同一端进行的。
在栈结构中,将元素加入栈结构的操作称为入栈(push),将元素从栈结构中退出的操
作称为出栈(pop)。最先入栈元素所在的位置称为栈底(botom),元素入栈、出栈所操作的
一端称为栈顶(p)。栈底元素一定是栈结构中最先入栈的元素,而位于栈顶的元素一定是
最后入栈的元素
to
。在执行出栈操作时,栈顶元素最先出栈,栈底元素最后出栈。在Java中
栈结构的实现类Stack类型下,还提供了看栈顶(pek)操作,即仅返回栈顶元素取值,但不
将栈顶元素出栈操作的方法实现。
需要注意的是,当栈结构为空时对其继续执行出栈操作或看栈顶操作被认为是不正确
的,此时通常以抛出异常的方式结束操作。
栈结构示意图如图3-2所示。
图3-2 栈结构示意图
用一个形象恰当的例子解释栈结构:影视剧中所展示的枪支的弹夹与栈结构高度相
似。在枪支的弹夹中,第一颗被压入的子弹将会被最后一个打出去,而最后一颗被压入的子
弹将会被第1个打出去,所以很多编程人员也将元素入栈称为“元素压栈”,而将元素出栈也
称为“元素弹栈”。
3.2
栈结构的实现
1.
在通过数组实现栈结构时,通常使用一个inttop变量保存数组中栈顶元素的下标取
56
值,初始化状态下top=-1。元素入栈的操作通过数组元素尾追加的方式实现,即以数组
中有效元素的尾端为栈顶方向,此时top++,而元素出栈操作则相当于删除数组中top下
标指向的元素,元素删除后top--。需要注意的是,在通过数组实现栈结构时,同样需要
考虑因为元素入栈导致的数组扩容的相关需求。
通过数组实现的栈结构及相关操作如图3-3所示。
图3-3 通过数组实现的栈结构及相关操作
在通过链表实现栈结构的时候,元素入栈通常采用头节点插入的方式进行实现,即以链
表头部为栈顶方向。相对地,元素出栈操作则是使用头节点删除的方式进行实现。
通过链表实现的栈结构及相关操作如图3-4所示。
3.3
栈结构的应用场景
1.
对于栈结构来讲容易理解的是,如果将一组数据按顺序逐个进行入栈,然后逐个出栈,
即可得到一个数据顺序与原始序列完全相反的新序列,而栈结构也因为这种特性在各种开
发场景中广泛用于“逆序”操作。
栈结构“逆序”的特点,大体上可以分为两种使用方式:①直观的数据逆序操作。例如
将数据序列{2,4,中的数据依次入栈后再依次出栈, 5,3,1}
1,3,5} 即可得到元素顺序为{4,2,
的新序列。这种操作还可以通过灵活地指定每个元素入栈、出栈的时机,实现数据序列整体
57
图3-4 通过链表实现的栈结构及相关操作
或者部分的逆序操作;②实现操作的延后性。假设现有A、B、C共3个方法,它们之间相互
调用,其中A方法内部调用B方法,B方法内部调用C方法,并且程序整体以A方法的调用
为起点。对于上述案例来讲,A方法虽然最先被调用,B方法次之,C方法最后被调用,但是
在内存中最先执行完毕的应该是C方法。因为只有C方法运行完成,并将运行结果返回B
方法,B方法才能继续向下运行,最终在运行结束时将结果返回给调用它的A方法,A方法
最终结束运行。如同在上述案例中这种“先调用、后结束”的操作场景,也可以通过栈结构进
行实现。
本节给出了栈结构比较常见的几种具体应用场景,并且结合一些问题案例进行说明与
实现。
1.
数据的逆序操作
对于使用栈结构实现最直观的数据逆序操作没有太大的难度,唯一需要注意的是,如果
将原始序列中的数据一次性全部加入栈结构中,再一次性全部出栈,最终只会得到整体逆序
的新序列,但是在某些应用场景下,原始序列中的元素可能通过部分入栈、部分出栈、再部分
入栈、再部分出栈的不规则操作,得到部分逆序的新序列。下面通过两个案例来对上述情况
进行演示。
【例3-1】存在一个空栈,现有4个元素,其入栈顺序为a、b、c、d,则不可以得到的出栈
顺序为( )。
A.a,c,B.c,a c,b,D.c,d
b,d d,b,C.a,d a,b,
在例3-1中,给出了元素入栈的顺序,但是对元素出栈的顺序并未进行要求,也就是说
58
此时有可能出现部分元素入栈、部分元素出栈的不规则操作的情况,但是不论如何进行元素
入栈、出栈操作都必须保证元素之间“后进先出”的顺序关系。下面对4个选项是否可能出
现分别进行分析。
选项A:a入栈,b入栈,c入栈,c出栈,d入栈,可行。
a出栈,b出栈,d出栈
,
选项B:a入栈,c入栈,d出栈,b出栈,可行
。
b入栈,d入栈,c出栈,a出栈,
选项C:a入栈,b入栈,c入栈,c出栈,此时b压在a上,所以不可能直接出栈a,不
可行。选
项D:a入栈,b入栈,c出栈,b出栈,d入栈,可行。
a出栈,c入栈,d出栈,
【例3-2】设有一栈结构S,元素s1、s2、s3、s4、s5、s6依次进栈,如果6个元素出栈的顺
序是s2、s3、s4、s6、s5、s1,则栈的容量至少应该是( )。
A.2 B.3 C.5 D.6
例3-2的分析思路与例3-1相似,元素的入栈顺序一定,为了得到目标的元素出栈顺
序,就需要通过元素部分入栈、部分出栈的方式进行操作。在操作过程中,栈结构内同时存
在元素数量的最大值,即为栈结构的最小容量。下面对分析过程进行说明。
1、
为了得到例3-2中元素的出栈顺序,需按照如下顺序对入栈元素进行操作:入栈s入
栈s2,此时栈内元素为{s1,s2}; 出栈s2,栈内元素为{s1}; 入栈s3,栈内元素为{s1,s3}; 出
栈s3,栈内元素为{s1}; 入栈s4,栈内元素为{s1,s4}; 出栈s4,栈内元素为{s1}; 入栈s5、s6,
栈内元素为{s1,s5,s6}; 出栈s6,栈内元素为{s1,s5}; 出栈s5,栈内元素为{s1}; 出栈s1,
栈空,操作完成。在上述过程中,栈内最多同时存在3个元素,所以栈结构最小容量为3。
2.
模式匹配与转换操作
模式匹配与转换操作可以认为是通过栈结构实现操作延后性的直观体现。
在一些应用场景当中,给出的某一部分数据可能无法直接进行运算操作。这一部分数
据需要等到一个合适的操作指令的出现,才能逐个回退着向前进行计算。这样的运算方式
在计算机的各种模式匹配与转换算法中经常会用到。下面通过两个具体案例对栈结构在模
式匹配和转换操作中的应用进行说明。
【例3-3】括号的匹配算法。在编译器对程序语法结构正确性进行检查的过程中,经
常需要对语句中出现的括号是否匹配进行测试。现有一表达式,其中只包含(、)及运算数,
例如(1+2)×3 、3×((1+2)+(5+4))÷12 等形式。表达式中,括号之间可以嵌套使用,如
(()), 也可以互相之间并列存在,如()()(()())。设计一个程序,验证以字符串形式输入的
表达式中括号是否相互匹配。
在例3-3中,当遇见表达式中的左括号时,无法立即确认后续表达式中是否存在与之匹
配的右括号,此时可以对遇见的左括号进行入栈操作,对后续表达式内容继续进行遍历,直
到遇见一个右括号,位于栈顶的左括号出栈,与之进行匹配。因为表达式中的括号可以嵌套
使用,所以在栈结构中可能同时存在多个左括号,而最先入栈的左括号,一定是表达式中最
外层括号的组成部分,所以随着表达式的遍历,栈底的左括号一定是最后被匹配上的,这一
点就表现出了括号匹配操作的延迟性。如果表达式遍历完成,栈结构中依然存在剩余的左
5 9
括号,则表示表达式中存在多余的左括号,表达式不合法;如果在表达式遍历过程中遇见右
括号,而此时栈结构已经为空,则表示表达式中存在多余的右括号,表达式不合法;只有在表
达式遍历到最后一个右括号的同时,栈结构恰好出栈最后一个左括号,才表示表达式匹配
正确。下
面给出通过栈结构实现的表达式括号匹配算法的示例代码:
/**
Chapter3_StackAndQueue
com.ds.stack
TestStack.java
栈结构的应用测试类
*/
public class TestStack {
//对表达式中的左右括号进行匹配,从而判断表达式是否合法
public boolean testExpression(String exp) {
//1.创建用于进行括号匹配的栈结构
Stack<Character> stack = new Stack<>();
//2.将表达式字符串转换成字符数组
char[] chs = exp.toCharArray();
//3.遍历表达式,进行括号匹配
for(char ch : chs) {
switch(ch) {
//遇见左括号:入栈等待匹配
case '(':
stack.push(ch);
break;
//遇见右括号
case ')':
//如果此时栈结构为空,则表示存在多余右括号,表达式不合法
if(stack.isEmpty()) {
return false;
}
//栈结构不为空,出栈栈顶左括号,表示匹配
stack.pop();
break;
//对于其他符号直接忽略
default:
continue;
}
}
60
/*
4.如果表达式遍历结束且栈结构不为空,则表示表达式中存在多余的左括号,表达式不
合法
*/
if(!stack.isEmpty()) {
return false;
}
//其余状况下,表达式合法
return true;
}
}
【例3-4】 逆波兰表达式的转换。逆波兰表达式是计算机当中用于存储运算表达式的
一种表示方式。在将一个正常的运算式转换为逆波兰表达式的时候,首先取得运算符左右
两侧运算数的优先表示,然后将运算符放在最后进行表示。例如运算式a+b 转换成逆波
兰表达式为ab+;运算式(a+b)×c 转换成逆波兰表达式为ab+c×,其中ab+可以看作
(a+b)部分的运算结果,与运算数c 同时表示×运算左右两侧的运算数。现给出一组由字
符串表示的逆波兰表达式,如{"a","b","c","d","+","e","×","+","f","+",
"×"},设计一个程序将逆波兰表达式转换为一般的运算式形式。例如将上述逆波兰表达式
转换为一般运算式可以表示为(a×((b+((c+d)×e))+f))。为了方便起见:①逆波兰
表达式中仅包含+、-、×、/四则运算;②在转换过程中,得到任意部分的子运算式后都要
在左右两端添加括号以表示子运算式的界限。
在进行逆波兰表达式转换过程中,首先扫描到的一定是运算数,但是在仅得到运算数的
情况下是没有办法执行运算操作的,所以此时运算数之间的运算延迟可以通过对运算数进
行入栈操作来完成。在继续扫描逆波兰表达式的过程中如果遇见运算符,则将位于栈顶的
两个运算数出栈,作为运算符两侧的运算数,结合运算符构成运算式的子部分,并将这一子
部分重新入栈,表示作为下一运算符的运算数使用。在逆波兰表达式数组遍历结束后,栈结
构中剩余的唯一字符串,即为逆波兰表达式转换得到的对应运算式。需要注意的是,对于减
法和除法这样不符合交换律的运算操作,栈顶最先出栈的运算数表示其右侧运算数,其次出
栈的栈顶元素表示其左侧运算数,而对于加法、乘法等符合交换律的运算,运算数的左右位
置并不重要。
下面给出通过栈结构实现的逆波兰表达式转换运算式算法的示例代码:
/**
Chapter3_StackAndQueue
com.ds.stack
TestStack.java
6 1
栈结构的应用测试类
*/
public class TestStack {
//逆波兰表达式转换运算式的方法
public String evalRPN(String[] rpn) {
//1.创建用于运算式转换的栈结构
Stack<String> stack = new Stack<>();
//2.遍历逆波兰表达式数组,进行转化
String left;
String right;
String tmp;
for(String str : rpn) {
switch(str) {
//对于四则运算符的操作
case "+":
case "-":
case "*":
case "/":
//先出栈的是右侧运算数
right = stack.pop();
//后出栈的是左侧运算数
left = stack.pop();
//拼接子运算式并入栈
tmp = "(" + left + str + right + ")";
stack.push(tmp);
break;
//对于一般运算数直接入栈
default:
stack.push(str);
break;
}
}
//转换结束,栈中唯一字符串为转换完毕的运算式
return stack.pop();
}
}
注意:在计算机中对运算式进行表示的方案可以分为前缀表达式、中缀表达式和后缀
62
表达式,其中前缀表达式亦称为波兰表达式;后缀表达式亦称为逆波兰表达式。中缀表达式
中的运算符出现在运算数的中间,也就是常见的一般运算式。
3.内存中的方法栈
在Java的内存模型当中,如果一个方法被调用,JVM 就会创建一个与被调用方法相对
应的“栈帧”,并将这个“栈帧”加入方法栈当中。如果在这个方法内部,存在对其他方法的调
用操作,则当执行到这一内部方法调用的时候,JVM 同样会为内部调用方法再创建新的栈
帧,并入栈方法栈。在Java的内存结构当中,之所以使用栈结构描述方法之间的相互调用
关系,是因为外部方法在执行过程中,总是依赖内部方法运行完毕后所产生的结果进一步向
下执行,所以先调用的方法总是后结束,而在内部被后续调用的方法总是需要先结束,而这
种“先调用后结束、后调用先结束”的延迟操作特性,正适合使用栈结构进行实现。
下面给出一组方法相互调用的示例,并以图示的方式演示方法栈中栈帧的变化过程,代
码如下:
/**
Chapter3_StackAndQueue
com.ds.stack
TestMethodStack.java
方法栈演示代码
*/
public class TestMethodStack {
public void methodA() {
//方法A 的执行代码
}
public void methodB() {
methodA();
}
public void methodC() {
methodB();
}
public void methodD() {
//方法D 的执行代码
}
public static void main(String[] args) {
TestMethodStack test = new TestMethodStack();
test.methodC();
test.methodD();
}
}
63
上述方法调用对应的方法栈的变化过程如图3-5所示。
图3-5 方法栈的变化过程
4.树和图的深度优先遍历
在第6章与第9章的内容当中,将会继续对树和图这两种非常重要的数据结构进行说
明。在针对树和图两种结构的基础操作当中都存在深度优先遍历(DepthFirstSearch,
DFS)操作,而在对树或者图进行深度优先遍历操作时,最常用的方式有两种:①通过栈结
构实现;②通过递归结构实现。在第4章介绍递归结构的内容中还会详细地讲解递归结构
在内存中的实现方式,而这一点仍然与前述讲解的方法栈息息相关。
鉴于目前尚未对树结构和图结构进行讲解,缺乏对于二者的基本认知,故而将此部分知
识点放在第6章与第9章中详细说明,在此不过多进行阐述。
3.队列结构
2
3.1
队列结构概述
2.
队列结构的逻辑特点是元素先进先出(FirstInFirstOut,FIFO )。可以将队列结构理
解成为一个两端开口,一端入、一端出的结构,最先加入队列的元素也是最先退出队列的元
素,最后加入队列的元素也是最后退出队列的元素。
在队列结构中,将元素从一端加入队列的操作称为入队列(ofer),将元素从另一端退
出队列的操作称为出队列(pol)。元素入队列的一端称为队列尾(rear),元素出队列的一端
称为队列头(t)。最先入队列的元素位于队列头位置,最后入队列的元素位于队列尾位
fron
置。在执行出队列操作的时候,队列头元素最先出队列,队列尾元素最后出队列。
与栈结构相似的是,当队列为空的时候执行出队列操作也是被视为不正确的,同样可以
通过抛出异常的方式结束操作。
队列结构示意图如图3-6所示。
64
图3-6 队列结构示意图
队列结构与现实生活中的排队非常相似,先来排队的人优先被服务,后来排队的人需要
等前面的人都离开后才能被服务,而在排队过程中,先来排队的人位于队伍最前端,最后来
的人位于队伍最末端。人员进入队伍和离开队伍的位置分别位于队伍两端,中间不允许
插队。
3.2
队列结构的实现
2.
队列结构同样可以使用数组或者链表实现。
在使用数组对队列结构进行实现时,通常设置两个int型变量front和rear,其中变量
front始终指向队列头元素所在下标,变量rear始终指向下一个入队列元素所要占用位置
的下标。初始状态下,rner的取值相等, 入队列元素加入
fot和ra均为0。在元素入队列时,
数组中rear取值下标的位置并执行rear++;在元素出队列时,从数组中front取值下标的
位置退出队列头元素并执行front++ 。在元素入队列、出队列过程中,如果front==rear
条件达成(注意此时front和rear取值可能并不是0),则表示队列为空。
需要注意的是,通过数组结构实现队列仍然需要考虑因为元素入队列导致的数组扩容
问题。同时因为在元素入队列、出队列操作过程中,t和rr变量都是单向递增的,所
fronea
以当元素出队列后,数组中下标取值小于front的部分将不会再被后续入队列元素占用,此
时将会导致数组空间的浪费。这一情况在通过数组实现的循环队列结构中有所改善,详细
内容将在3.4节中进行讲解。
2.
通过数组实现的队列结构及相关操作如图3-7所示。
通过链表对队列结构进行实现相对简单。在实现过程中,同样需要设置两个节点类型
的引用变量front和rear,分别指向链表中队列头节点和队列尾节点(此处注意区分与数组
实现队列结构过程中,rer变量指向位置的不同)。初始状态下,rner取值相同,
afot和ra都
指向nul,并且反向判断front和rear同时指向nul
也可以作为当前队列为空的判别标准。
元素入队列操作使用链表的尾追加方式实现。当初始队列为空时,保存入队列元素的新节
点直接追加在链表的head头节点后面,并且front和rear变量同时指向新节点;如果初始
队列非空,保存入队列元素的新节点追加在rear指向节点的后面,并且调整rear=rear.
next。元素出队列操作使用链表的头删除方式实现。首先删除front变量指向的节点,并使
用其中数据域取值作为返回值,然后调整fot=hanx即fot变量始终指向链表头
rned.et, rn
节点的直接后继节点。如果元素出队列后链表清空,则还需调整rear=nul
。
通过链表实现的队列结构及相关操作如图3-8所示。
65
图3-7 通过数组实现的队列结构及相关操作
3.3
队列结构的应用场景
2.
队列结构的应用场景,总是与等待、排队相关。先来排队的元素先被处理,后来排队的
元素后被处理。这种特点在很多算法与操作系统的底层应用中非常常见。下面通过两组具
体的案例对队列结构的应用场景进行讲解。
1.
顺序作业调度
【例3-5】作业调度是操作系统底层为不同请求分配系统资源时进行的操作。如果多
66
图3-8 通过链表实现的队列结构及相关操作
个请求需要申请同一系统资源进行支持,而操作系统对多个请求按照资源申请的先后顺序
进行处理,即为顺序作业调度。
现假设在一台具有单核k 线程CPU 的计算机上同时产生了n 个请求,每个请求需要
占用CPU 的某一线程一段时间进行处理,同一CPU 线程同一时间下只能处理一个请求,
并且每个请求所占用的CPU 线程都是由调度随机分配的。设计一个程序模拟上述场景,
并在n 个请求全部处理完毕后,统计CPU 每个线程被占用的时间。
上述需求是一个典型的顺序作业调度场景。在实现模拟的过程中,可以为每个CPU
的线程设计一个任务队列,当某一请求发出后,根据随机值为其分配一个用来处理的CPU
线程,并将这个任务加入对应线程编号的任务队列当中。当所有任务分配完毕后,对每个任
务队列循环执行任务出队列操作,直到任务队列为空为止。在出队列过程中,将每个任务对
线程的占用时间累加,即可得到每个CPU 线程被占用的时间总和。
上述模拟场景的实现代码如下:
/**
Chapter3_StackAndQueue
com.ds.queue
TestQueue.java
队列结构的应用测试类
*/
public class TestQueue {
6 7
/**
对顺序作业调度场景进行模拟的代码
参数int k 表示CPU 的线程数量
参数long[] taskMills 表示请求对CPU 线程的占用时间
返回值表示在处理完所有请求后,每个CPU 线程被占用的总时间
*/
public long[] sequentialJobScheduling(int k, long[] taskMills) {
/*
1.为每个CPU 线程创建一个任务队列
为方便操作,将所有任务队列保存在一个长度为k 的数组当中
*/
Queue<Long>[] taskQueues = new Queue[k];
for(int i = 0; i < k; i++) {
taskQueues[i] = new LinkedList<>();
}
/*
2.为每个请求分配一个CPU 线程进行操作
即将每个请求对应的操作时间根据随机值加入对应的任务队列
CPU 线程编号的取值范围为[0, k-1]
*/
int queueNum;
for(int i = 0; i < taskMills.length; i++) {
queueNum = (int)(Math.random() * k);
taskQueues[queueNum].offer(taskMills[i]);
}
//3.请求分配结束后,对所有线程的占用时间进行统计
long[] times = new long[k];
Queue<Long> q;
for(int i = 0; i < k; i++) {
q = taskQueues[i];
while(!q.isEmpty()) {
times[i] += q.poll();
}
}
return times;
}
}
2.树和图的广度优先遍历
在3.1.3节当中曾说明过,对于树和图两种结构可以使用栈结构或者递归实现其深度
优先遍历操作。在深度优先遍历操作之外,树和图两种结构还存在广度优先遍历(Breadth
FirstSearch,DFS)操作,而树和图的广度优先遍历操作则是通过队列结构实现的。同样
68
地,这一部分内容将留在第6章与第9章进行详细讲解。
3.4
队列结构的衍生
2.
1.双端队列
双端队列就是两端均可以进行元素出入队列操作的队列结构。在双端队列中,元素入
队列和出队列的操作又可以被详细地分为oferFirst、oferLast和polFirst、polLast两组。
通过上述4种操作,可以根据具体的业务需求灵活地实现对队列结构中任意一端顶端数据
的入队列、出队列操作。在双端队列的具体实现过程中,oferFirst和polFirst两种操作都
是从结构的起始端进行元素的入队列和出队列操作;oferLast和polLast两种操作都是从
结构的最末端进行元素入队列和出队列的操作。图3-9较为明确地演示了这4种操作与双
端队列实现结构两端的关系。
图3-9 双端队列结构
从理论上来讲,双端队列既可以通过数组方式实现,也可以通过双链表方式实现,但是
如3.2节讲解过的, 就有可能导致数组中
2.如果通过数组实现一个不限制长度的队列结构,
出现空间浪费的情况,况且双端队列的元素出入队列操作是在数组两端均可实现的,所以不
论选择数组结构的哪一端作为元素出入队列的起点都有更大的概率引起数组结构频繁地对
元素进行移动操作,所以在此对数组实现双端队列结构的方案不做过多阐述。
在通过双链表结构实现双端队列结构时,因为在双链表中存在head和tail两个节点,
分别从两端引起整个双链表结构,所以在定位链表结构的起始位置与结束位置的时候更加
方便。在双端队列不为空的前提下,polFirst操作相当于删除head节点的直接后继节点;
polLast操作相当于删除tail节点的直接前驱节点。不论双端队列是否为空,oferFirst操
作都相当于向head节点的直接后继位置进行新节点的插入;oferLast操作都相当于向tail
节点的直接前驱位置进行新节点的插入。
通过双链表实现的双端队列结构及相关操作如图3-10所示。
双端队列结构的一大经典应用是在“作业窃取”操作中的使用。
用一个相对通俗的案例解释“作业窃取”操作:假设某学校食堂有4个窗口可以打饭,
在每个窗口前都有一条相互独立的队伍进行排队,每位前来就餐的学生可以随机选择四个
队伍中的一个进行排队。如果在排队过程中,某一窗口前排队的学生都已经取餐完毕,则这
个窗口就已经处于空闲状态。空闲状态下的窗口就可以呼唤其他学生队伍中处于队伍末端
的同学前来打饭,这就是典型的“作业窃取”操作场景。
69
图3-10 双链表实现的双端队列结构及相关操作
如果将4个食堂窗口看作CPU 的4个独立线程,则在窗口前排队的学生队伍就是当前
CPU 线程的任务队列。每个CPU 线程每次从自己任务队列的最前端出队列一个任务进行
处理,而当有其他线程空闲时,这些空闲线程就可以从其他CPU 线程任务队列的末尾“窃
取(出队列)”一个任务进行处理。这样一来就可以最大限度地发挥多线程CPU 的性能优
势,不造成CPU 线程资源的浪费,从而提升整体的任务处理效率。
在Java中提供的ForkJoinPool线程池及其相关API 就是基于上述理论实现的,而其
70
中对于任务队列的实现正是使用了双端队列。
2.
循环队列
在3.2节中曾讲解过,如果使用数组实现队列,在不限定队列结构长度的情况下会在
2.
元素不断入队列、出队列的操作过程中产生大量数组空间的浪费,但是如果指定队列结构的
长度,则会在入队列元素数量达到数组总长度时导致队列结构在逻辑上为满。此时即使出
队列一些元素,队列头方向释放出来的数组空间也无法重复利用,依然会因为队列结构在逻
辑上为满,导致新元素不能入队列。这种数组结构中存在空闲空间,但是队列结构在逻辑上
为满、元素无法入队列的情况,称为队列结构的“假溢出”。如果将通过数组结构实现、限定
长度的队列结构设计为循环队列,则不仅能有效地解决假溢出的问题,还能够不断地重复利
用元素出队列后队列头方向产生的空闲数组空间。
在实现循环队列结构时,通常会在初始化阶段设置循环队列的长度。在通过设定的队
列长度创建底层数组结构时,要求数组长度为循环队列长度+1 。在循环队列结构中,同样
设置初值为0的front和rear两个变量,用来指定队列头元素所在下标和下一个入队列元
素所占用的数组下标,即在循环队列非空的情况下,er变量同样指向循环队列结构中队列
ra
尾元素所在下标+1 的位置。
初始状态下的循环队列结构如图3-11 所示。
图3-11 初始状态下的循环队列结构
假设当前循环队列内部数组的长度为size,即循环队列为满时可容纳size-1个元素。
当元素入队列时,占用数组中下标为rr的位置,并将rr移动到(e的
eaearear+1)%siz
位置,即执行ra=(er+1)%szer+1 的取值
erraie的操作。之所在执行上述计算时使用ra
对数组长度size进行取余运算,是因为在边界条件下如果入队列元素占用的是数组中最大
下标位置,则可以通过上述操作将rear标记位直接移动回数组下标取值为0的位置,相当
于重复利用数组结构中前序部分的空位,达到元素循环入队列的效果。例如在使用长度为
10 的数组实现的元素容纳数量为9的循环队列中,当前rear标记位已经指向数组中下标为
9的位置,那么在新元素入队列并占用数组中下标为9的位置后,计算rear=(rear+1)%
size=(9+1)%10=0,即可将rear标记位重新指回数组的起始位置。
元素加入循环队列的两种情况如图3-12 所示。
同样地,当元素出队列时,在取得数组中front下标位元素执行出队列操作后执行front=
(
的起始下标位置。
e操作,其目的同样是为了保证在边界条件下ft标记位能够返回数组
front+1)%sizron
71
图3-12 元素加入循环队列的两种情况
元素退出循环队列的两种情况如图3-13 所示。
图3-13 元素退出循环队列的两种情况
72
在判断循环队列是否为空时,同样可以使用front==rear的条件进行判断,但是如果要
判断循环队列为满的情况,则需要进行如下讨论:如果将数组结构被填满作为循环队列结构
为满的判断标准,则根据rear变量取值为队列尾元素下标+1 来计算,当数组被填满时同样会
得到front==rear的结果,也就是说如果将数组被填满视作循环队列为满,则判断循环队列
为满和循环队列为空的条件重叠。为了避免这种情况发生,则浪费掉数组中的1位空间,即当
数组中只有1位空间空闲时,就认为循环队列为满。此时,t和rr两变量之间的关系符
fronea
合(t。这种做法也解释了循环队列底层的数组结构的长度等于循环
rear+1)%size==fron
队列长度+1 的原因,数组结构+1 的长度就是在判断循环队列为满时浪费掉的1位空间。
循环队列为空与为满的情况如图3-14 所示。
图3-14 循环队列为空与为满的情况
3.
优先队列
在原生队列结构中,元素存储的顺序总是与元素入队列的顺序相关,但是在优先队列中元素
存储的顺序则是与元素的权值相关。在优先队列中允许使用者通过自定义的方式,对加入队列
的元素之间的权值进行比较,权值最大或者最小者处于队列头位置。也就是说优先队列每次出
队列操作得到的取值,总是其中具有最高权值或者最低权值的元素,与元素加入队列的顺序无
关。例如下列元素的取值,即代表元素的权值, 3,1,9,2,
元素取值为{5,0,4,8}。现将这些元素加
入一个高权值优先的优先队列当中,则上述元素出队列的顺序为{8,4,2,0}。
9,5,3,1,
Java中同样提供了优先队列的实现类,即PriorityQueue类型,而PriorityQueue类型
则是借助了堆结构实现其中元素的按照权值出队列功能。关于堆结构的知识将在第7章中
进行详细讲解,在此不做过多阐述。
第4章
递归、查找与排
序
第2章已经对数组和链表这两种物理结构进行了讲解,但是针对数组和链表结构中元素的
操作,除了基本的增、删、改、查外还有很多其他的方式,这其中较为常见的就是元素查找与排序
操作。对于数组和链表中元素的查找,除了基本的顺序查找方式外最为常用的就是二分查找。
二分查找虽然对数据序列中元素的排列顺序有一定要求,但是其可以在对数级别的时间复杂度
下完成对目标元素的查找,并且在二分查找的基础上,还衍生出了插值查找和斐波那契查找等其
他查找算法,而元素排序操作根据其实现思路的不同,又可以详细分为多种不同的排序算法,不
同的排序算法在时间复杂度、空间复杂度及稳定性方面也具有不同的表现,但是不论查找算法还
是排序算法,在实现的过程中又都有用到递归结构的场景,所以本章将对递归结构、多种查找及
排序算法进行说明。为了方便讲解,本章中所有的代码示例均以数组结构作为数据序列载体。
本章内容的思维导图如图4-1所示。
图4-1 递归、查找与排序章节思维导图
4.递归
递归结构一直以来都是数据结构与算法学习过程中的重点和难点,甚至夸张一些来讲,是
否熟练掌握递归结构及能否通过递归思想解决问题,可以作为衡量一个程序员水平的标杆。