第1章
线性结构

1.1 数组

1.1.1 数组的基本概念

数组（Array）是最简单的数据结构，是由有限个相同类型的变量（或对象）组成的有序集合。因为数组中各元素之间是按顺序线性排列的，所以数组是一种线性数据结构。图1-1为数组的结构示意。

从图1-1可以看出，数组有以下特征。

（1）数组用唯一的名字标识，例如图1-1中的数组名为array，通过数组名可以对数组中的元素进行引用，例如array[0]就表示数组中的第1个元素“1”。

（2）数组中的元素类型必须相同，例如图1-1中的数组元素类型为整型，当然也可以是其他类型的变量或对象。

（3）数组的内存单元是连续的，一个数组要占据一个地址连续的内存空间。

（4）数组中的数据元素都是顺序存放的，元素之间有先后关系，数组元素之间不能存在空隙。

综上所述，数组是一类物理空间和逻辑形式都连续的线性数据结构。

本书将用Java代码来实现数组的定义及操作。

1.1.2 数组的定义

可以通过以下方法定义一个整型数组。

或者，

上面两种定义数组的方法是等价的，不过这里更加推荐使用第1种方法定义数组，因为第1种方法更加符合Java的代码风格。

请注意，上面只是声明了一个引用变量array，其本质还是一个指针，而该数组本身并不存在，也就是说在内存中还没有开辟那段连续的存储空间。要使用该数组，必须先对数组进行初始化。

在Java中初始化数组有两种方法：静态初始化和动态初始化。

静态初始化指在定义数组时显式地指定数组的初始值，系统会根据初始值的个数和类型自动为数组在堆内存中开辟空间。例如，

或者

执行了上面的代码后，系统会在堆内存中分配6个int类型长度的内存空间，并为数组array初始化元素1、2、3、4、5、6。

动态初始化指在初始化数组时仅指定数组的长度，不指定数组元素的初始值，例如，

或者

执行了上面的代码后，系统会在堆内存中为数组array分配6个int类型长度的内存空间。需要注意的是，动态初始化数组不会显式地为数组指定初始值，系统会为该数组指定默认的初始值。

如果我们希望定义更加完备的数组结构，则可以定义一个数组类，对数组的属性和操作进行封装。下面这段代码描述了如何定义一个数组类。

MyArray是我们定义的数组类，在该类中包含两个成员变量：array表示一个int[]类型的数组，通过array[index]的形式可以引用到数组中的元素；成员变量elemNumber表示数组中元素的数量。在调用了MyArray（int capacity）构造函数初始化该数组后，elemNumber被赋值为0，这表示数组此时已在堆内存中开辟内存空间，但是还没有存入任何数据。

请注意区分数组的容量和数组中元素数量之间的区别。数组的容量指数组在堆内存中开辟出的内存单元的数量，也就是上述代码中构造函数的参数capacity所指定的大小，它表示该数组中最多可以存放多少个元素；而数组中元素的数量是变量elemNumber记录的数据，它表示该数组中当前存储的有效元素的数量，如图1-2所示。

我们可以通过array.length（）函数获取数组的容量，所以在MyArray类中不需要再定义一个变量专门记录数组的容量。但是变量elemNumber是必需的，因为数组的容量与数组中元素的数量可能不相等，如图1-2所示，这就需要通过一个变量来记录数组中有效元素的数量，否则可能从数组中取出无效值。

除了array和elemNumber，MyArray类还定义了一些操作数组的方法，例如向数组中插入元素的函数insertElem（），从数组中删除元素的函数deleteElem（）等，可以根据需要定义不同的操作方法，我们将在后续的章节中介绍如何实现这些方法。

1.1.3 数组的基本操作

数组的基本操作包括向数组中插入元素、从数组中删除元素等。

1.向数组中插入元素

前面已经给出了向数组中插入元素的函数，如下。

这个函数的作用是在整型数组中的第index个位置上插入一个整型元素elem。要实现该函数，首先要理解什么是数组的第index个位置以及什么是在数组的第index个位置上插入元素。

这里规定，数组中元素的位置是从1开始的，因此数组元素的下标与数组元素的位置相差1，如图1-3所示。

这是一种约定俗成的规则，很多数据结构的书籍都是这样规定的，所以本书也沿用这一规则。当然，从0开始计算数组中元素的位置也是可以的，大家应当根据具体情况灵活掌握。

所谓在数组的第index个位置上插入元素，就是插入的这个新的元素要位于数组的第index个位置上，原第index个位置上的元素以及后续元素都要顺序向后移动一个位置。

前面已经讲到，数组中的元素之间不能存在“空隙”，因此插入新元素的位置index的取值范围应在1（包含）到elemNumber+1（包含）之间，否则数组中会出现“空隙”，从而无法判断哪些是无效的数组元素，哪些是有效的数组元素。

可以按照下面步骤来实现在数组的第index个位置上插入一个元素。

（1）将数组中第index个元素及之后的所有元素都向后移动一个位置，将数组的第index个位置空出来，如图1-4所示。

需要注意的是，在移动数组元素时要从数组的最后一个元素开始，从后向前逐个移动，直到将第index个元素向后移动一个位置为止。在图1-4中，首先将第5个元素array[4]向后移动一个位置，再将第4个元素array[3]向后移动一个位置，最后将第3个元素array[2]向后移动一个位置。只有按照这种方式移动数组元素，数据才不会被覆盖，最终将数组的第index个位置空出来。

（2）将新的元素插入数组的第index个位置，即array[index-1]=elem；因为数组的下标与数组的位置之间相差1，所以array[index-1]就是数组的第index个元素。如图1-5所示。

经过以上两步操作，可以将元素elem插入数组的第index个位置。最后还要将记录数组元素数量的变量elemNumber加1，表示数组中元素的数量增加了1。

下面给出向数组中插入元素的Java代码描述。

需要指出的是，如果插入元素的位置是elemNumber+1，也就是在数组最后插入一个元素，则不需要执行移动数组元素的操作，直接将元素插入数组的elemNumber+1位置即可。在上面这段代码中，如果函数insertElem（）的参数index等于elemNumber+1，则代码中循环移动元素的操作实际上是不被执行的，因为循环变量i的初始值是elemNumber-1，不满足i≥index-1的循环条件，所以上述代码对于向数组的elemNumber+1位置插入一个元素的情形同样适用。

接下来，我们通过一个测试程序来检查这段代码的正确性。

上述这段测试程序模拟了图1-4和图1-5描述的实例。首先初始化一个容量为8的整型数组；然后通过调用MyArray类的insertElem（）函数，将整数元素3、5、2、7、8依次插入数组的第1至第5个位置；接下来调用printArray（）函数，打印该数组中的内容，该函数定义如下。

最后调用MyArray类的insertElem（）函数在数组的第3个位置上插入元素0；再次调用printArray（）函数打印该数组中的内容，运行结果如图1-6所示。

图1-6的运行结果是符合预期的，看来insertElem（）函数的实现似乎没有什么问题。但是如果我们对测试程序稍加修改，就能发现一些问题。

与之前的测试程序唯一的不同是，在上面这段测试程序中初始化了一个容量为5的数组，而不是容量为8的数组。这时如果在数组的第3个位置上插入元素0，就会抛出一个数组越界异常。因为该数组中已保存了5个数据元素，没有更多的空间存储新的元素了，所以在执行到array.insertElem（0，3）；时会抛出数组越界异常，如图1-7所示。

解决这个问题有两种方法，第1种方法是当数组中的元素数量达到数组的容量上限时，就不允许再向数组中插入新元素，而是直接返回false表示插入元素失败。但是这种方法限定了数组中元素的数量，不够灵活。这里推荐第2种方法——动态扩容方法。当向数组中插入元素，而数组中的元素数量又达到容量上限时，可以调用一个数组扩容方法对数组进行扩容，这样数组的存储空间就会随着数组元素的增多而不断增大，理论上该数组就能存放任意数量的元素了。

下面给出向数组中插入元素的带扩容机制的完整的Java代码描述。

increaseCapacity（）函数的实现如下。

每调用一次increaseCapacity（）函数，就将数组扩容至原来的2倍，同时保留原数组中已有的元素，这样再向该数组中插入元素时就不会报出数组越界异常了。

2.从数组中删除元素

前面已经给出了从数组中删除元素的函数定义，如下。

该函数的作用是删除数组中第index个位置上的元素。这个过程与插入元素的过程正好相反，我们只需将第index个位置之后的元素（不含第index个位置上的元素）顺序向前移动一个位置，并将数组元素的数量减1，就可以完成删除操作。如图1-8所示。

如图1-8所示，删除第3个元素的方法是将第3个元素（不含）之后的所有元素顺序向前移动一个位置，同时将记录数组元素数量的变量elemNumber减1。

在执行上述删除数组元素的操作时，有几点需要大家特别注意。

（1）被删除数组元素的位置只能在1（包含）到elemNumber（包含）之间，删除其他位置的元素是非法的。

（2）在移动数组元素时要从数组的第index+1个元素开始从前向后逐个进行，直到移动到第elemNumber个元素。如图1-8所示，首先将第4个元素array[3]向前移动一个位置，然后将第5个元素array[4]向前移动一个位置，最后将第6个元素array[5]向前移动一个位置。这样移动数组元素不会覆盖有效的元素值，同时可将第index个位置上的元素覆盖。

（3）数组的元素数量只能通过变量elemNumber记录，所以在删除一个数组元素后一定要将变量elemNumber的值减1，从而保证数组下标在elemNumber-1之外的元素都是无效元素。

下面给出从数组中删除元素的Java代码描述。

至此，我们完成了数组类MyArray的定义，并实现了insertElem（）、deleteElem（）、increaseCapacity（）等基本操作函数。以上完整的代码及测试程序可从“微信公众号＠算法匠人→匠人作品→《算法大爆炸》全书源代码资源→1-1”中获取。

1.1.4 数组的性能分析

数组是一种可随机访问的线性结构。由于数组存储于连续的地址空间，所以只要给定数组名（例如array）和数组的下标，就可以用 O （1）时间复杂度直接定位到对应的元素。这也是数组作为顺序存储结构的优势所在。

数组的缺点主要体现在以下两方面。

（1）由于数组中的元素都是顺序存储的，且数组元素之间不能存在空隙，因此在插入、删除元素时会有大量元素移动，将严重影响效率。在数组中插入或删除一个元素的时间复杂度都是 O （ n ）级的。

（2）没有扩容功能的数组的大小是固定的，在使用数组时容易出现越界问题。增加了自动扩容功能的数组虽然能避免内存越界问题，但在一定程度上又会导致内存资源的浪费（因为总会有一些空闲的数组空间）。

综上所述，数组比较适合读操作频繁，而插入、删除操作较少的场景。在定义数组时，应根据实际需求指定数组的大小。如果需要扩容，则应选择合适的扩容因子（扩容后数组容量是原容量的倍数），既要尽量提高空间的利用率、减少内存资源的浪费，又要最大限度地避免频繁扩容对数组性能的影响。

1.1.5 案例分析

案例1-1：数组元素的逆置

编写一个函数reverseArray（），将数组中的元素逆置。例如原数组中的元素顺序是{1，2，3，4，5}，那么逆置后数组中的元素顺序是{5，4，3，2，1}。

本题难度 ：★

题目分析 ：

数组元素的逆置操作一般要求不创建新数组，只在原数组内将数组元素的顺序颠倒过来，这样操作的效率比较高，实现起来也更加简单。

要将包含elemNumber个元素的数组进行逆置，需要定义一个临时变量tmpElem作为数据缓冲区，同时要设置变量low和high，作为数组的下标分别指向数组的第1个元素和最后一个元素。然后执行以下步骤。

（1）将low指向的元素和high指向的元素通过临时变量tmpElem交换位置。

（2）执行low++和high——，重复执行步骤（1）直到low≥high。

通过以上步骤可将一个包含elemNumber个元素的数组原地逆置。该算法的时间复杂度为 O （ n ），空间复杂度为 O （1）。该算法的Java代码描述如下。

请注意，函数reverseArray（）是MyArray类的成员函数，因此该函数可直接对数组array进行操作，不需要通过参数传递进来。

下面我们通过一个测试程序来检查reverseArray（）函数的正确性。

测试程序首先初始化了一个容量为5的数组，然后通过循环调用array.insertElem（）函数向数组中插入元素1、2、3、4、5，再调用array.printArray（）函数打印数组内容，接下来调用array.reverseArray（）函数将数组元素逆置，最后再次调用array.printArray（）函数打印数组内容。运行结果如图1-9所示。

本题完整的代码及测试程序可从“微信公众号＠算法匠人→匠人作品→《算法大爆炸》全书源代码资源→1-2”中获取。

案例1-2：删除数组中的重复元素

编写一个函数purge（），删除整数数组中的重复元素。例如，数组为{1，1，3，5，2，3，1，5，6，8}，删除重复元素后数组变为{1，3，5，2，6，8}。

本题难度 ：★★

题目分析 ：

本题是一道经典的数组问题，我们用三种方法求解。

要删除数组中的重复元素，最直观的方法就是先定位一个数组元素，然后从前向后扫描整个数组，如果发现与定位的元素相同的元素，就调用deleteElem（）函数将该元素删除。不断调整定位的元素，直到将整个数组中重复的元素全部删除为止。该方法的Java代码描述如下。

上述代码实现了删除整型数组中重复元素的操作。在代码中，变量i指向的元素array[i]即为定位的元素，也就是数组中最终要保留的元素，然后通过变量j从元素array[i+1]开始顺序遍历，将后续的每个元素都与array[i]进行比较，一旦发现array[i]与array[j]重复，就调用deleteElem（）函数将元素array[j]删除。

在函数purge（）中，内层的while循环在j等于数组元素的数量elemNumber后停止，表示数组中再没有与元素array[i]重复的元素了。外层的while循环由变量i控制，表示要在数组array中删除与当前元素array[i]重复的所有元素。外层循环在i等于elemNumber后停止，此时数组中所有的重复元素都将被删除（只保留一个，删掉重复的）。

下面我们通过一个测试程序检验函数purge（）的正确性。

运行结果如图1-10所示。

如图1-10所示，最初数组的内容是{1，1，3，5，2，3，1，5，6，8}，删除重复元素后数组的内容变为{1，3，5，2，6，8}，可见程序执行正确。

上述算法简单直观，但是时间复杂度很高，可达到（ n ³ ）。首先通过二重循环找出数组中存在的重复元素，这个操作的时间复杂度是 O （ n ² ）；而执行deleteElem（）函数的时间复杂度是 O （ n ），综合起来该算法的时间复杂度为 O （ n ³ ）。其实该算法还存在一些优化空间。

当找到重复元素后，可以不马上调用deleteElem（）函数，而是先做一个标记，这样就可以节省每次调用deleteElem（）函数时批量移动数组元素的时间。当找出了全部重复元素后再进行整体删除，这样只需要执行一次二重循环找出数组中的重复元素，再加上一次循环删除重复的元素即可，时间复杂度降为 O （ n ² ）+ O （ n ），整体的时间复杂度仍是 O （ n ² ）级别。改进后的算法描述如下。

在上述算法中，首先通过一个二重for循环找出数组中的全部重复元素，并将这些重复的元素用标记FLAG即-111覆盖。以数组{1，1，3，5，2，3，1，5，6，8}为例，经过这个二重循环处理后，其数组状态如图1-11所示。

然后执行一个一重循环，找到数组中第1个FLAG标记，并用变量i指向该数组元素，如图1-12所示。

接下来用一重for循环将FLAG标记的重复元素删除，也就是用后面的数组元素覆盖FLAG。具体做法如下。

（1）初始化变量j=i+1。

（2）用变量j扫描数组中的后续元素，如果array[j]不是FLAG，则用array[j]覆盖array[i]，然后i和j都向后移动一个位置（i++，j++）；如果array[j]是FLAG，则j++，寻找下一个非FLAG的有效值。按照这种方法用变量j扫描完整个数组后，所有FLAG都将被删除。

（3）最后还要修正elemNumber的值，因为删除数组中的重复元素后，数组元素的数量将减少。

如图1-13所示，在上面的操作过程中，变量i指向的是最终存放有效元素的位置，而变量j的作用是在数组中寻找有效元素，即未被FLAG标识的元素，并将这个有效元素的值赋给array[i]。只要经过这样一重循环操作，就可将数组中的FLAG全部删除。

下面我们通过相同的测试程序检验改进后的函数purge（）的正确性，运行结果如图1-14所示。

可见改进后的算法也可以得到正确的结果。

现在我们已将算法的时间复杂度从 O （ n ³ ）优化到了 O （ n ² ），还可以利用Java类库中提供的容器类HashSet来进行进一步的优化。

熟悉Java容器类的读者应当知道，HashSet是java.util包中的类，在向HashSet中添加新的对象时，HashSet会判断重复的对象。如果添加的对象与HashSet内已有对象重复则添加失败，同时返回false；如果没有重复则添加成功并返回true。向HashSet中添加元素并查重的操作的时间复杂度仅为 O （1），这是因为HashSet内部封装了HashMap，其本身是一个Hash表结构。

我们可以利用HashSet的这一特性，将数组中的元素依次添加到HashSet中（调用HashSet.add（）函数），如果添加成功，则说明当前添加的数组元素与HashSet中的已有元素不重复；如果添加失败，则说明当前添加的数组元素与HashSet中的已有元素有重复，且该元素就是数组中的重复元素。将找出的这些重复元素标记为FLAG，再通过一次for循环将数组中的FLAG全部删除，这样就可以删除数组中的重复元素。

不难看出，利用HashSet查找数组中重复元素的时间复杂度为 O （ n ），将数组中的FLAG全部删除的时间复杂度也为 O （ n ），所以整个算法的时间复杂度是 O （ n ）+ O （ n ），也是 O （ n ）级别。代价就是需要一个HashSet作为辅助工具，空间复杂度要高一些。

该算法的Java代码描述如下。

使用上面提供的测试程序检验改进后的purge（），程序的运行结果如图1-15所示。

可见改进后的算法也可以得到正确的结果。

其实还有一种更简单的方法甚至不需要给原数组中的重复元素标记FLAG。因为HashSet中已保存了过滤了重复元素的数组元素，所以可以直接将HashSet中保存的数据依次读出，再更新到原数组中。但是这种方法存在一个问题，就是HashSet中的数据是无序的，所以从HashSet中读取出的元素顺序可能与原数组中的元素顺序不一致。如果不在意数组中元素的顺序而只考虑删除重复元素，那么也可以采用这种方法。本题完整的代码及测试程序可从“微信公众号＠算法匠人→匠人作品→《算法大爆炸》全书源代码资源→1-3”中获取。

1.2 链表

1.2.1 链表的基本概念

链表也是一种常用的线性数据结构，与数组不同的是，链表的存储空间并不连续，它是用一组地址任意的存储单元来存放数据的，也就是将存储单元分散在内存的各个地址上。

这些地址分散的存储单元叫作链表的节点，链表就是由一个个链表节点连结而成的。那么这些地址分散的节点是如何关联到一起的呢？每个节点中都包含一个叫作“指针域”的成员，指针域中存储了下一个节点的内存地址，这样就可以连接后继节点。

每个链表都会有“链表头”，通常是一个指针（对于Java而言，它是链表节点对象的引用），用来存放链表中第1个节点的地址。同时，链表中最后一个节点的指针域通常会置为空（null），用来表示该节点是链表的最后一个节点，没有后继节点。

图1-16为链表在内存中的结构示意，通过这个图我们可以对链表有更加直观的认识。

从图1-16中可以看到链表具有以下特征。

链表在逻辑上是连续的，而在物理上并不一定连续，链表节点可能分散在内存的各个地址上。

（1）每个链表节点中都必须包含指针域，用来存放下一个节点的内存地址，数据域则用来存放节点的数据元素。这里需要注意，数据域可以是一个也可以是多个，由具体的需求而定。数据域的类型可以是任意类型（图1-16中是字符类型），而指针域的类型必须是定义的链表节点类型，或链表节点指针类型。

（2）只要获取了链表头（head）就可以通过指针遍历整个链表。以图1-16为例，获取了链表头就可以知道第1个节点的内存地址1249，继而访问到第1个节点中的数据A；然后通过第1个节点中的指针域1356可以访问到第2个节点中的数据B。以此类推，直到访问到最后一个节点（指针域为null）。所以获取链表头非常重要。

1.2.2 链表的定义

链表是由链表节点构成的，因此在定义链表结构之前，先要定义链表的节点类型。链表节点可以用Java语言描述如下。

类Node包含两个成员变量：data为整型的变量，是该链表节点的数据域，可用来存放一个整数；next是Node类型的变量（引用类型变量），是该链表节点的指针域，用来指向下一个节点。

定义完链表节点类Node，接下来我们可以定义链表类。链表是靠节点间的指针相互关联的，只要获取了链表头就可以通过头指针遍历整个链表。在一个链表类中没有必要包含该链表的所有节点，只需要定义一个head成员就足够了。操作链表的函数可根据需要而定，常见的函数包括向链表的指定位置插入一个节点、从链表的指定位置删除一个节点等，大家可以自行定义。下面给出用Java语言定义的链表类。

MyLinkedList是定义的链表类，在这个类中包含两个成员变量：head是Node类型的成员，它是链表中第1个节点的引用，也就是指向第1个节点的指针；length是整型变量，用来记录数组中元素的数量。同时定义了两个成员函数用来对链表进行操作：函数insertNode（int data，int index）表示在链表的第index个位置上插入一个整型变量data节点；函数deleteNode（int index）表示删除链表中第index个位置上的节点。我们会在后面的章节中介绍这些函数的实现。

1.2.3 链表的基本操作

链表的基本操作包括向链表中插入节点和从链表中删除节点，另外根据实际需要可以定义获取链表长度、销毁链表等操作。

向链表中插入节点

向链表中插入节点函数的定义如下。

这个函数表示在链表的第index个位置上插入一个整型变量data节点。在实现该函数之前，有两点需要特别注意。

（1）参数data指链表节点中的元素值而不是节点对象。因为我们定义的链表节点Node中的数据域是int类型，所以参数data也是int类型。

（2）参数index表示要将节点插入链表中的位置。与数组元素的位置相似，我们规定index只能是从1（包含）到length+1（包含）之间的值，其他的值都是非法的。

如图1-17所示，在链表的第1个位置上插入节点指将新节点插入链表中并使其位于链表的第1个位置；同理，在链表的第6个位置上插入节点指将新节点插入链表中并使其位于链表的第6个位置。不难理解，当一个链表的长度为length时，插入一个节点后其长度将变为length+1，所以新插入的节点只可能位于该链表的第1～length+1个位置上，在其他的位置上必然是非法的。

如何在链表的第index个位置上插入一个节点呢？可以依照下面的步骤进行。

（1）首先通过一个循环操作找到要插入位置的前一个节点，并用指针p指向该节点。如图1-18所示。

如图1-18所示，假设要在链表的第3个位置上插入一个新节点，首先要找到链表中的第2个节点，并用指针p指向该节点。

（2）创建一个新的节点，将节点元素赋值为6（data），同时用指针node指向该节点，如图1-19所示。

（3）将p所指节点的next域的值（即p的后继节点指针）赋给node节点的next域。

（4）再将node赋值给p节点的next域，如图1-20所示。

如图1-20所示，通过步骤（3）和步骤（4），节点插入p节点和p节点的后继节点之间。

注意，如果要在链表的第1个位置上（index=1）插入节点，那么因为第1个位置上之前并没有节点而只有一个头指针head，所以步骤（3）、步骤（4）不再适用。这里需要考虑两种情况。

（1）如果head==null，则说明链表是一个空链表，没有任何节点，此时将步骤（2）生成的新节点node赋值给head即可，这样head就指向了链表的第1个节点。

（2）如果head！=null，则说明链表中已存在节点，此时将head（即原链表中的第1个节点的引用）的值赋给node节点的next域，再将node赋值给head即可，如图1-21所示。

下面给出向链表中插入节点的Java代码描述。

相信大家注意到了，在插入节点成功后，成员变量length的值会加1，这样每次需要得到链表的长度时直接读取length值就可以了。当然也可以通过遍历链表的方法获取链表的长度，但是效率较低，其时间复杂度为 O （ n ）。

链表是一种动态的数据结构，可以随时在其中插入节点或删除节点，所以链表的长度是不断变化的。如果我们在插入、删除的过程中随时修改length值，让length始终记录链表当前的长度，那么在获取链表的长度时就不需要重新遍历整个链表了，直接返回length值即可，效率就会高很多，其时间复杂度为 O （1）。所以在设计算法时，应根据数据结构自身的特性选择性能最佳的方法。

从链表中删除节点

下面介绍如何从一个非空链表中删除指定位置的节点。前面已经给出了删除链表中index位置上的节点的函数定义。

这个函数表示将链表中第index个位置上的节点删除。在实现该函数之前，首先需要明确什么叫将链表中第index个位置上的节点删除。

如图1-22所示，删除链表中index=3的节点就是将链表中的第3个节点移除，使其前驱节点与后继节点直接连接。删除成功后，链表的长度减1。很显然，index的取值范围是从1（包含）到length（包含），其他的值都是非法的。

删除步骤如下。

（1）首先通过一个循环操作找到要删除节点的前一个节点（前驱节点），并用指针p指向该节点，如图1-23所示。

（2）执行“p.next=p.next.next；”语句完成删除节点的操作，如图1-24所示。

另外，如果要删除的节点是链表中的第1个节点，即index=1，则需要特殊处理。因为index=1的节点前面没有其他节点，所以不能按照步骤（1）、步骤（2）执行。这时只需要将head.next赋值给head即可，这样head就会指向原链表第1个节点的后继节点，也就是删除了原链表中的第1个节点，如图1-25所示。

下面给出从链表中删除节点的Java代码描述。

向链表中插入节点和从链表中删除节点是链表的最基本操作，除此之外，我们还可以根据需要定义其他操作。在后面的实战演练中会有更多关于链表的操作方法，大家可以参考学习。

1.2.4 链表的性能分析

上一节介绍了数组的性能问题，因为数组存储于连续的地址空间，所以支持随机访问，只要给定数组名和数组的下标，就可以在 O （1）的时间内定位到数组元素。而链表不支持随机访问，链表节点是分散存储的，无法通过一个索引在常量时间内定位到链表中的元素，必须从链表头开始顺序遍历链表，所以在链表中定位一个元素的时间复杂度是 O （ n ）级别。

但是与数组相比，在链表中插入元素和删除元素的效率要高很多，如果已知要插入或删除节点之前节点的指针，那么插入或删除操作的时间复杂度仅为 O （1）。

除此之外，在使用数组时需要预先开辟一整块内存空间，存在内存越界的风险，也可能导致内存资源的浪费。而链表只需要在使用时动态申请节点，不会产生内存越界，内存的使用效率也相对较高。

综上所述，相较于数组，链表的优势在于能够更加灵活地进行插入和删除操作，且内存使用效率更高。因此，对于线性表规模难以估计或插入删除操作频繁、随机读取数据的操作较少的场景，更建议使用链表。

表1-1是数组和链表的比较，可以帮助大家加深对数组和链表的认识。

1.2.5 不同形态的链表结构

我们将节点中只包含一个指针域且指针只能指向该节点的后继节点的链表称作单链表。除单链表外，链表家族中还有功能更加强大的循环链表和双向链表。

循环链表

循环链表是一种特殊形式的单链表，它的最后一个节点的指针域不为null，而指向链表的第1个节点，图1-26为循环链表的结构示意。

循环链表具备一些普通单链表所不具备的特性。例如普通的单链表只能沿着指针方向找到一个节点的后继节点，无法回到其前驱节点。而由于循环链表最后一个节点的指针域指向了链表的第1个节点，所以只要通过指针后移，就一定能够找到其前驱节点。在解决某些问题时，循环链表要比普通的单链表更有优势。

双向链表

双向链表在单链表的基础上进行了改进。单链表的节点中只有一个指针域，该指针域中保存其后继节点的指针。而双向链表的节点中存在两个指针域，一个指针域中的指针指向其直接前驱节点，另一个指针域中的指针指向其直接后继节点，如图1-27所示。

双向链表示意图如图1-28所示。

与循环链表类似，双向链表可以方便地访问到一个节点的前驱节点，这种访问不需要遍历整个链表，而是通过prior指针域直接访问，性能比循环链表更高。如果需要经常沿两个方向进行节点操作，那么更适合使用双向链表。

双向循环链表

如果把循环链表和双向链表结合起来，就是结构更为复杂的双向循环链表，如图1-29所示。

双向循环链表结合了循环链表和双向链表的优点，对节点的操作更加方便灵活。与此同时，双向循环链表的结构比其他类型的链表更加复杂，所以还要结合具体需要选择链表结构。

本书的后续章节将结合具体问题对前面介绍的各种链表结构进行更加深入的探讨。

1.2.6 案例分析

案例1-3：链表的综合操作

创建一个包含10个节点的单链表保存整型数据1～10，在屏幕上显示链表中的内容。在链表中第1、3、5、20个位置上分别插入一个节点，节点中的数据均为0，每插入一个节点，就在屏幕上显示链表中的内容。将插入的节点全部删除，再显示链表中的内容，最后将链表销毁。

本题难度 ：★

题目分析 ：

本题考查单链表的灵活操作，核心要点是掌握向链表中的指定位置插入元素以及从链表中的指定位置删除元素的操作。对于创建链表，可以通过插入节点的操作来实现。对于显示链表，则可以从链表的第1个节点开始顺序向后遍历整个链表，每访问一个节点，就在屏幕上显示该节点中的数据值，直到遍历到最后一个节点。

销毁链表的操作则稍显特殊，大家不要试图通过调用deleteNode（int index）函数将链表中的节点逐一删除，这是一种冗余操作。对Java而言，如果一个对象失去了引用，则该对象最终会被Java的垃圾回收机制回收并释放，因此用户没有必要，也无法显式地释放一个对象实例。所以，要销毁一个链表，只需要将链表的头指针head置为null即可，这样链表的第1个节点将失去引用（没有任何指针指向它），最终会被回收并释放；当第1个节点被释放后，第2个链表节点也将失去引用，最终被回收并释放，以此类推，最终整条链表中的节点都将被回收，从而完成了整条链表的销毁操作。

需要注意的是，C或C++没有垃圾回收机制，如果使用这两种语言实现链表，那么销毁链表时需要循环调用free（）函数或delete（）函数显式地释放内存，否则失去引用（无指针指向）的链表节点会造成内存泄漏，从而影响正常的内存使用。

下面给出本题完整的Java代码实现。

首先创建一个MyLinkedList类的实例list，然后调用list.insertNode（）函数向这个空链表中依次插入1，2，3，…，10，接下来调用list.printLinkedList（）函数打印链表的内容，此时链表的内容如下。

head → 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10

然后调用list.insertNode（）函数在链表的第1、3、5、20个位置上分别插入整数0。上述操作完成后链表的内容如下。

head → 0 → 1 → 0 → 2 → 0 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10

请注意，在向第20个位置上插入节点时，链表的长度为13，而插入的位置是20，是非法的，因此插入失败并在屏幕上显示错误信息。

接下来调用list.deleteNode（）函数将第1、2、3个位置上的节点删除。请注意，在删除第1个位置上的节点后，最初位于第3的0此时位于第2，所以需要删除链表中的第2个节点；同理删除了第2个0元素后，最初位于第5的0此时位于第3，所以需要删除链表中的第3个节点。经过上述操作，链表中的内容如下。

head->1->2->3->4->5->6->7->8->9->10

最后调用list.destroyLinkedList（）函数将链表销毁。

运行结果如图1-30所示。

本题及完整的代码测试程序可从“微信公众号＠算法匠人→匠人作品→《算法大爆炸》全书源代码资源→1-4”中获取。

案例1-4：将两个有序链表归并

编写一个函数MyLinkedList MergeLinkedList（MyLinkedList list1，MyLinkedList list2），实现将有序链表list1和list2合并成一个链表，要求合并后的链表依然按值有序，且不开辟额外的内存空间。

本题难度 ：★★★

题目分析 ：

本题是常见面试题。在解答本题时要注意以下几点。

（1）链表list1和list2都是按值有序的，将两个链表合并后要求链表依然按值有序。例如，list1为1->3->5，list2为2->4->6->7，那么合并后的链表list3应为1->2->3->4->5->6->7。

（2）本题要求不开辟额外的内存空间，也就是要利用原链表的内存空间，在不创建新节点的前提下实现链表的合并。

在设计算法时，要利用list1、list2的节点资源，在不创建和删除节点的前提下，通过改变节点指针域的指针来调整链表节点之间的先后顺序，从而实现链表合并的功能。

我们通过一个具体实例来详细分析。

初始条件：内存中已有list1和list2，其状态如图1-31所示。

操作步骤：

（1）定义一个Node类型的头指针head3指向list3的第1个节点。同时定义Node类型指针（引用）变量p、q、r辅助实现链表的合并。

（2）将head3指向head1节点和head2节点中的较小者。head1节点中的元素为1，head2节点中的元素为2，所以head3指向head1节点。初始化指针（引用）变量p、q、r。这里规定指针r始终指向list3的最后一个节点，因为当前head3指向head1节点，所以r指向head1节点，此时该节点就是list3的最后一个节点（list3会随着两个链表的合并不断变长）。同时规定指针p和q分别指向list1和list2中待合并的节点，因此p指向3，q指向2，下一步将比较这两个节点的大小。这一步完成后链表的状态如图1-32所示。

（3）循环并不断比较指针p和指针q指向的节点值。如果p指向的节点值小，则将p指向的节点插入r指向的节点后（因为r始终指向list3的最后一个节点），然后向后移动p和r；如果p指向的节点值大，则将q指向的节点插入r指向的节点后面，将指针r指向它，并将q指针后移，这样r指向的节点依然是list3的最后一个节点。本例中完成一次循环后链表的状态如图1-33所示。

此时已将list2的第1个节点（也就是head2节点）合并到了list3中，指针r指向该节点，说明它是list3当前的最后一个节点。在本次循环中，指针p没有发生改变，而指针q指向了下一个节点，在下一次循环中将继续比较指针p和指针q指向的节点值。

（4）不断重复步骤（3），不断比较p指向的节点值和q指向的节点值，将较小者插入r指向的节点后面，然后调整p、q、r的指向，当p等于null或者q等于null时结束循环，此时list1或者list2中至少有一个链表的节点已全部合并到list3中。

（5）将list1或list2中剩余的节点（尚未合并到list3中的链表）整体插入r指向的节点后面，实现完整的合并操作。本例中链表合并后的状态如图1-34所示。

在合并链表时需要不断地比较p节点和q节点的值，并将值较小的节点连接到r节点后，所以合并后的list3仍保持按值有序排列（从小到大排列）。同时，整个合并过程中没有开辟额外的内存空间，而是利用原链表的节点资源，通过调整指针实现链表的合并，因此符合题目要求。

下面给出完整的Java代码实现。

在代码中定义了一个MergeLinkedListTest类，类中定义了static函数MergeLinkedList（）用来将两个MyLinkedList链表合并，并返回新的MyLinkedList对象。

函数MergeLinkedList（）的具体实现是定义了p、q、r三个指针变量（Node类型的引用变量），通过对p节点值和q节点值的比较，将值较小的节点连接到r节点后面，再将剩余的链表连接到r节点的后面。需要注意的是，因为MergeLinkedList（）函数的参数是MyLinkedList类型对象引用，而一个MyLinkedList对象中包含了链表的头节点指针head，所以我们需要获取这个head指针才能对该链表进行操作，因此在MyLinkedList中需要新定义两个函数。

使用getHead（）函数将list1和list2的头节点取出，这样可以在MergeLinkedList（）函数中对链表list1和list2进行处理。使用setHead（）函数可将一个链表的头节点指针设置给一个MyLinkedList对象，这样可将合并后的链表头节点指针head3设置给新的链表对象list3并返回。

代码中的MyLinkedList类、insertNode（）函数及printLinkedList（）函数等都是前面已经定义过的，这里不再给出。

运行结果如图1-35所示。

list1为1->3->5->7->9，list2为2->4->6->8->10，合并后的链表为1->2->3->4->5->6->7->8->9->10。

本题完整的代码及测试程序可从“微信公众号＠算法匠人→匠人作品→《算法大爆炸》全书源代码资源→1-5”中获取。

1.3 栈

1.3.1 栈的基本概念

栈（Stack）是一个后进先出（Last In First Out，LIFO）的线性表，它要求只在表尾对数据执行删除和插入等操作。说得通俗一些，栈就是一个线性表（可以是数组，也可以是链表），但是它在操作上有别于一般的线性表。栈的元素必须先进后出，也就是先进入栈的元素必须后出栈，而不能像一般的链表或数组那样从任意位置读取元素；另外，栈的操作只能在线性表的表尾进行，这个表尾被称为栈的栈顶（top），相应的表头被称为栈的栈底（bottom）。

栈的形态很像一个子弹匣，最先压入弹匣的子弹一定最后弹出，而最后压入弹匣的子弹一定最先弹出，如图1-36所示。

栈的数据必须从栈顶进入，也必须从栈顶取出，先入栈的数据在后入栈的数据的下面。栈中不含有任何数据时的状态叫作空栈，此时栈顶等于栈底（top等于bottom），随着数据不断地从栈顶进入栈中，栈顶与栈底逐渐分离（top逐渐增大）。数据出栈时从栈顶弹出，栈顶下移（top逐渐减小），当数据全部出栈后栈顶又重新等于栈底（top等于bottom）。

1.3.2 栈的定义

前面讲到，作为一个线性结构，栈既可以用数组实现也可以用链表实现。在大多数情况下，人们使用数组来实现栈，本书中只介绍用数组实现的顺序栈。

可以用下面这段代码定义一个栈。

MyStack是我们定义的栈类，在该类中包含3个成员变量：stack是int[]类型的数组，说明用一个整型数组来实现栈。top表示栈顶位置在数组stack中的下标，一般规定top始终指向栈顶元素的上一个空间，例如在图1-36中，栈顶元素是3，而top指向该元素的上一个空间，所以真正的栈顶元素是stack[top-1]。成员变量capacity用来记录栈当前的容量，随着栈中元素不断增加，可对栈进行扩容，变量capacity的值也应随之进行调整。

需要注意的是，MyStack类中并没有定义栈底位置bottom的值，这是因为我们是使用数组来实现栈的，所以bottom的值恒等于0，不需要定义成员变量bottom。如果采用链表的形式实现栈，则需要定义bottom的值，它应当是指向栈底节点的指针变量（引用变量）。

在调用构造函数MyStack（int capacity）初始化一个栈后，会在系统的堆内存上开辟大小为capacity的栈空间，但此时top的值为0，即栈顶等于栈底，也就是说，此时该栈中还没有任何数据（空栈），如图1-37所示。

在MyStack类中还定义了入栈操作push（）、出栈操作pop（）、栈扩容操作increaseCapacity（）等函数，我们将在后续的章节中介绍。

1.3.3 栈的基本操作

1.入栈

入栈就是向栈中存入数据。入栈要在栈顶进行，每当向栈中压入一个数据，栈顶指针top都要增加1，直到栈满。可以用下面这段代码实现入栈操作。

通过上面这段代码，可将一个整型元素elem压入MyStack栈中，它的具体操作步骤如下。

（1）在将数据入栈前要判断栈是否已满，这里通过if（top==capacity）条件语句来判断栈是否已满。

因为规定了top始终指向栈顶元素的上一个空间，而stack本质是一个数组（顺序栈），其下标top是从0开始计算的，所以stack[top-1]是栈顶元素，并且top值等于该栈中元素的个数。当top等于capacity时，栈中元素的个数等于capacity，top已经指向stack数组的外面，所以不能再向栈中压入元素，需要调用increaseCapacity（）函数对栈进行扩容。increaseCapacity（）函数的定义如下。

这一步操作如图1-38所示。

（2）将参数elem存入栈顶，即执行“stack[top]=elem；”操作。

（3）将top加1，这样top就指向了栈顶元素的上一个空间，栈顶元素为stack[top-1]。

入栈的过程如图1-39所示。

2.出栈

出栈与入栈正好相反，它是从栈顶取出元素，同时栈顶指针top减1。每从栈顶取出一个元素，栈内元素就减少一个。若重复执行出栈操作，那么最终可将栈内元素全部取出，使得栈顶等于栈底，此时该栈成为空栈。可以用下面这段代码实现出栈。

函数pop（）的作用是将栈顶元素取出并返回，同时调整栈顶指针top的值（减1）。它的具体操作步骤如下。

（1）在从栈顶取出元素前，需要判断栈内是否有元素，这里通过条件语句if（top==0）来判断。当top值等于0时，栈顶等于栈底（bottom恒等于0），此时栈内没有任何元素。如果栈内没有元素，则pop操作就是非法的，所以要返回一个无效值ERROR_ELEM_VALUE。该值可以是任意整数，可根据具体需要自行定义，但要注意的是，一旦将某个整数赋值给常量ERROR_ELEM_VALUE，该整数就不能作为栈中的有效元素了。

（2）将top值减1，使其指向栈顶元素。

（3）将stack[top]返回，完成出栈。

出栈的过程如图1-40所示。

下面通过一个测试程序验证我们定义的push（）函数和pop（）函数。

在上面这段测试程序中，首先初始化了一个容量为3的MyStack类型的栈，然后将整数1、2、3、4、5依次入栈，最后将这些元素依次出栈并打印出来。运行结果如图1-41所示。

入栈顺序为1->2->3->4->5，出栈顺序为5->4->3->2->1，符合栈的先进后出（FIFO）原则。同时需要注意到，初始化该栈对象时指定的栈容量为3，而实际压入栈中的元素数量为5，这说明在入栈过程中成功地实现了栈的扩容，因此运行结果符合预期。

至此，我们完成了栈类MyStack的定义，并实现了push（）、pop（）、increaseCapacity（）等基本函数。以上完整的代码及测试程序可从“微信公众号＠算法匠人→匠人作品→《算法大爆炸》全书源代码资源→1-6”中获取。

1.3.4 案例分析

案例1-5：二/十进制转换器

利用栈结构将二进制数转换为十进制数。

本题难度 ：★

题目分析 ：

二进制数是计算机中数据的存储形式，它是由一串只包含0和1的编码组成的。每个二进制数都可以转换成对应的十进制数，每个十进制数也可以转换为相应的二进制数。二进制数和十进制数的转换规则如下。

举例来说，将二进制数11001转换为十进制数，方法就是：1×2 ⁰ +0×2 ¹ +0×2 ² +1×2 ³ +1×2 ⁴ =25。

由于栈具有后进先出的特性，所以可以利用栈方便地将二进制数转换为十进制数。具体方法如下。

首先将二进制数从高位到低位顺序入栈。然后从栈顶依次取出每一个元素（0或1），当取出第 i 个元素时，就对应地乘以2 ^{i -1} ，并将结果累加起来。最终得到的和即为该二进制数对应的十进制数。

图1-42可以形象地展示出利用栈将二进制数11001转换为十进制数的过程。

下面给出将二进制数转换为十进制数的Java代码描述。

函数String BiToDec（String binary）的作用是将参数binary指定的二进制串转换成对应的十进制串并返回。这里需要注意的是，参数binary是String类型，由字符0和1组成，表示一个二进制数。为了与之对应，该函数的返回值也是String类型，表示一个十进制数。

在该函数内部，首先通过一个循环操作将二进制串binary从高位到低位顺序入栈。为了计算方便，这里将字符0或1转换为整数0或1后再存入栈，然后通过一个循环操作将栈中的二进制字符串从低位到高位顺序出栈。这里通过变量i控制每一个二进制位对应的积，Math.pow（2，i）表示2 ⁱ 。通过语句“sum=sum+（int）（e*Math.pow（2，i））；”达到将二进制数的第 i 位元素乘以2 ^{i -1} ，再逐一累加在一起的目的。累加的结果存放在变量sum中。最后将计算结果sum转换为String类型并返回。

下面我们通过一个测试程序检验函数BiToDec（）的正确性。

上述测试程序的运行结果如图1-43所示。

本题完整的代码及测试程序可从“微信公众号＠算法匠人→匠人作品→《算法大爆炸》全书源代码资源→1-7”中获取。

案例1-6：括号匹配问题

已知表达式中只允许有两种括号——圆括号（）和方括号[]，它们可以任意地嵌套使用，例如[（）]、[（）（）]、[（）（[]）]等都是合法的表达式。括号必须成对出现，[（]）、（[）]、[（））等不成对出现的情况是非法的。编写一个程序，判断一个括号表达式是否合法。

本题难度 ：★★

题目分析 ：

括号匹配问题是一道栈的经典问题。由于题目要求括号必须成对出现且可以任意嵌套，所以可以利用栈来保存输入的括号，并判断输入的括号表达式是否合法，具体做法如下。

每输入一个括号就与栈顶的括号进行比较。如果输入的括号与栈顶中保存的括号匹配，例如输入的括号是]，栈顶保存的括号是[，则将栈顶的括号出栈；如果输入的括号与栈顶中保存的括号不匹配，例如输入的括号是[，而栈顶保存的括号是），则将输入的括号入栈。不难想象，按照这样的规律进行下去，如果输入的括号完全匹配，即括号表达式合法，那么当输入完毕时，栈应该恰好为空。如果输入完毕而栈中仍有元素，则表明输入的括号不完全匹配，也就是括号表达式非法。

我们通过具体实例来进一步理解该算法。

假设括号表达式为“[（）]”，按照上述方法判断的过程如图1-44所示。

当括号表达式输入完毕后，栈中为空，因此表达式“[（）]”是合法的。假设括号表达式为“[（]）”，按照上述方法判断的过程如图1-45所示。

如图1-45所示，当括号表达式输入完毕后，栈中不为空，所以可以判定表达式“[（]）”是非法的。

下面给出上述算法的Java代码实现。

函数MatchBracket（String expression）的作用是判断参数expression指定的括号表达式是否完全匹配（是否合法），如果完全匹配，则返回true，否则返回false。

在该函数中通过一个循环操作将括号表达式expression中的字符逐一取出并与栈顶元素进行比较。如果括号不匹配，也就是match（c，expression.charAt（i））的返回值为false，则将这个从表达式中取出的括号字符expression.charAt（i）入栈。这里请注意，因为此时栈顶元素c已经出栈，所以要先将出栈的栈顶元素c重新入栈，再将expression.charAt（i）入栈。如果expression.charAt（i）与栈顶元素c匹配，也就是match（c，expression.charAt（i））的返回值为true，则不用做任何操作（因为此时栈顶元素c已经出栈）。另外，如果取出的栈顶元素为无效值ERROR_ELEM_VALUE，则说明当前栈中还没有任何内容，也就是输入的是第1个括号，此时要将第1个括号字符入栈。

判断括号是否匹配的函数match（）的定义如下。

当上述循环操作结束时，如果栈为空，则说明表达式合法，即表达式中的括号完全匹配，因此返回true；如果栈不为空，则说明表达式非法，即表达式中存在不相匹配的括号，因此返回false。

需要注意的一点是，上述代码中使用的栈MyStack与案例1-5中使用的MyStack略有不同，这里的MyStack中存放的是字符型（char类型）元素，而案例1-5中的MyStack中存放的是整型（int类型）元素，所以MyStack类要稍加修改才能使用。

下面我们通过一个测试程序检验函数MatchBracket（String expression）的正确性。

上述测试程序的运行结果如图1-46所示。本题完整的代码及测试程序可从“微信公众号＠算法匠人→匠人作品→《算法大爆炸》全书源代码资源→1-8”中获取。

1.4 队列

1.4.1 队列的基本概念

队列（Queue）是一种先进先出（First In First Out，FIFO）的线性表。与一般的数组和链表不同，队列要求所有的数据只能从一端进入，从另一端离开。在队列中，数据进入的一端叫队尾（rear），数据离开的一端叫队头（front）。队列的逻辑结构如图1-47所示。

图1-47示意了队列操作的逻辑特性，即数据只能从队尾进入队列，从队头离开队列。而队列的具体实现并无一定之规，既可以使用数组，也可以使用链表。本书将重点介绍用链表实现的链队列。

1.4.2 队列的定义

链队列的定义与普通的链表定义很相似，需要先定义队列的节点类，再定义队列类。

队列的节点可以用Java语言描述如下。

MyQueueNode是队列节点类型，与链表节点类Node相似，该类中包含两个成员变量：数据域成员data和指针域成员next。其中数据域data是int类型，说明该队列是一个可以存放整型元素的队列。MyQueueNode（int data）函数是队列节点类的构造函数，用来初始化队列节点实例。

接下来定义队列类。因为数据必须从队尾进入队列，从队头离开队列，所以在队列类中要包含队头和队尾两个指针，用来进行数据的入队列操作和出队列操作。此外，要定义诸如入队列、出队列、获取队列长度等基本操作。下面给出队列类的Java语言描述。

MyQueue类是我们定义的队列类，该类中包含两个MyQueueNode类型的成员变量——front和rear。front表示队头，指向队头节点；rear表示队尾，指向队列的尾节点。函数MyQueue（）是MyQueue类的构造函数，用来初始化MyQueue类的对象。在构造函数中将成员变量front和rear都初始化为null，表示当前队列中没有任何元素，也就是队列为空。

此外，在MyQueue类中还定义了队列操作的基本函数——入队列操作enQueue（）和出队列操作deQueue（），我们将在后续的章节中介绍这些函数的实现。

1.4.3 队列的基本操作

队列的基本操作包括入队列操作和出队列操作，根据实际需要还可以在队列类中定义其他函数。

1.入队列操作

入队列操作是让指定元素从队列的尾部进入队列的操作。元素进入队列后，队尾指针rear要修改，而队头指针front一般不变（除非最初的队列为空）。可以用下面这段代码实现入队列操作。

enQueue（）函数的作用是让整型元素data进入队列。

程序首先调用MyQueueNode类的构造函数创建一个队列节点，并将data作为构造函数的参数传入，这样该节点中包含的数据（data域中的值）就是data；然后将新生成的队列节点连接到队列的尾部，也就是执行“rear.next=node；”操作；最后修改队尾指针rear的值，使之指向新入队的node节点。

需要注意的是，当front==null且rear==null时，说明当前队列为空，入队列操作直接将node赋值给front和rear即可，说明入队列后队列中仅有一个元素，该元素既是队头也是队尾。

入队列操作的过程如图1-48所示。

2.出队列操作

出队列操作是将队头元素从队列中取出的操作。元素出队列后，队头指针front将指向原队头节点的后继节点，而队尾指针rear一般不变（除非出队列后队列变为空）。可以用下面这段代码实现出队列操作。

deQueue（）函数的作用是将队头元素取出。首先要判断front是否为null，如果front为null，则说明该队列是一个空队列，直接返回无效值ERROR_ELEM_VALUE（该值可定义为该队列中不会存在的值）即可；如果队列不为空，则通过语句“data=front.data；”将队头元素取出并赋值给变量data，再执行“front=front.next；”操作将队头节点删除；最后返回队头的元素值data。

需要注意的是，在执行完“front=front.next；”操作后，还要判断front是否等于null，如果front等于null，则说明删除队头节点后队列为空，此时也要将rear置为null，使队列恢复到图1-48中（1）的状态，否则队头节点会始终被变量rear引用而无法被回收释放。

出队列操作的过程如图1-49所示。

下面通过一个测试程序来验证上面实现的队列操作函数。

在测试程序中首先创建了一个包含整型元素的队列queue，然后让整数1、2、3、4依次进入队列，并在屏幕上打印出该队列的长度；接下来执行两次出队列操作，并将取出的元素打印出来，在屏幕上显示出该队列的长度；最后将队列销毁，在屏幕上显示出该队列的长度。运行结果如图1-50所示。

整数1、2、3、4依次进入队列后，队列中的元素为1->2->3->4，队列长度为4；执行两次出队列操作，在屏幕上依次显示整数1和2，此时队列的长度变为2。执行销毁队列操作后，队列的长度变为0。运行结果符合预期。

在测试程序中调用了getQueueLength（）函数获取队列的长度，该函数定义如下。

这里通过遍历队列节点的方式获取队列的长度。当然我们也可以参照1.2节中介绍的获取链表长度的方法，通过设置成员变量length来记录队列的长度，更加节省时间。

销毁队列的操作是通过函数destroyQueue（）实现的，该函数定义如下。

销毁一个队列与销毁一个链表的方法相似，只要将队头指针front和队尾指针rear都置为null即可，系统的垃圾回收机制会将队列链表逐一回收并释放。

至此，我们完成了队列类MyQueue的定义，并实现了enQueue（）、deQueue（）、getQueueLength（）、destroyQueue（）等基本函数。以上完整的代码及测试程序可从“微信公众号＠算法匠人→匠人作品→《算法大爆炸》全书源代码资源→1-9”中获取。

1.4.4 双端队列

除了前面介绍的从一端插入数据从另一端删除数据的普通队列，还有其他形式的队列，例如双端队列。

双端队列结合了队列和栈的优点，从队列的两端都可以插入数据（入队列）和删除数据（出队列），如图1-51所示。

与普通队列相比，双端队列的操作更加灵活。虽然双端队列不及普通队列和栈应用广泛，但在某些特殊场景下有其独特的优势。

有关双端队列的内容在这里不详述，感兴趣的读者可以查阅相关书籍。

1.4.5 案例分析

案例1-7：打印符号三角形

规定这样一种符号三角形，如图1-52所示。

该符号三角形的特点是：仅由“+”和“-”这两种符号构成；同号下面是“+”，异号下面是“-”。因此第1行决定了整个符号三角形的“+”和“-”的数量以及排列状态。编写一个程序，输入任意符号三角形的第1行，打印出符合规则的符号三角形。

本题难度 ：★★

题目分析 ：

“打印符号三角形”是一道经典的使用队列处理的问题。我们可以使用一个队列，并利用它先进先出的特性，先将第1行的 n 个符号入队列，再依次将符号取出。在取出第 i 个符号时，要判断它是否跟第 i -1个符号相同。如果相同，则将“+”入队列；如果不同，则将“-”入队列。在第1行的 n 个符号全部出队列并打印出来后，第2行的 n -1个符号也已全部进入队列。重复上述操作，一共打印 n 行，即可打印出完整的符号三角形，实现该过程的Java代码如下。

函数printCharacterTriangle（String firstLine）的作用是在屏幕上打印出符合要求的符号三角形。该函数包含一个字符串类型的参数firstLine，它指定了符号三角形中第1行的符号。

在函数printCharacterTriangle（）中首先创建一个队列实例（MyQueue类的对象），然后将firstLine中的字符逐一取出并保存到该队列中。接下来通过一个二重循环打印这个符号三角形。

外层循环的作用是控制符号三角形输出的行数。该符号三角形的行数就是第1行符号的数量，也就是说，如果第1行的符号数量为count，则该符号三角形的行数是count。

内层循环包括两个for循环，第1个for循环的作用是在每一个符号行的开始位置打印空格符，其目的是控制符号三角形的输出形状，如图1-53所示。

第2个for循环的作用是打印符号三角形中某一行的符号。这个过程较复杂，因此通过一个具体实例来说明。假设队列中已存放第1行符号，如图1-54所示。

在执行第2个for循环操作前，通过queue.deQueue（）函数取出队首元素+，并保存到变量 a 中，再打印出来。

然后通过一个for循环依次从队列queue中取出第2个至最后一个元素，过程如下。

（1）通过queue.deQueue（）函数取出元素+，并保存到变量 b 中。

（2）如果变量 a 和 b 中的元素相同，则 a 、 b 下面的符号为+，将“+”从队尾插入队列；否则，将“-”从队尾插入队列，如图1-55所示。

（3）将变量 b 赋值给变量 a ，重复（1）的操作。

该循环操作在本行中的全部符号都被取出并打印后停止。此时，队列中保存的是下一行应当输出的符号。对本例而言，此时队列的状态如图1-56所示。

回到外层循环，继续打印下一行，直到把count行的符号三角形全部打印出来。

下面通过一个测试程序验证函数printCharacterTriangle（）的正确性。

在main（）函数中给出了符号三角形的第1行符号+——+++——+，调用printCharacterTriangle（）函数打印出这个符号三角形。运行结果如图1-57所示。

本题完整的代码及测试程序可从“微信公众号＠算法匠人→匠人作品→《算法大爆炸》全书源代码资源→1-10”中获取。

案例1-8：用两个栈实现一个队列

请用两个栈实现一个队列的以下操作。

◎ 入队列：enQueue（int elem）。

◎ 出队列：int deQueue（）。

◎ 判断队列是否为空：boolean inEmptyQueue（）。

◎ 获取队列中元素的数量：int getCount（）。

请编程实现这个队列。

本题难度 ：★★

题目分析 ：

跟前面介绍的链队列不同，本题要求用两个栈实现一个队列的功能，所以需要重新设计。

无论怎样实现队列，最核心的一点都是要满足队列的逻辑特性，即先进先出。而同作为线性结构的栈，它与队列的本质区别在于其逻辑特性与队列不同——栈是先进后出（FILO）的线性表。所以要用栈实现队列的功能，就必须通过一种方式将先进后出转化为先进先出，从而模拟队列的逻辑特性。

一种普遍的做法是使用两个栈实现一个队列的功能，一个栈（stack1）用来存放数据，另一个栈（stack2）作为缓冲区。在入队列时，将元素压入stack1；在出队列时，将stack1中的元素逐个弹出并压入stack2，然后将stack2的栈顶元素取出作为出队元素；接下来将stack2中的元素逐个弹出并压入stack1。这样就能通过两个栈之间的数据交换实现入队列和出队列。如图1-58所示。

细心的读者可能已经发现，其实出队列的“元素出栈”完成后，没有必要将stack2的数据压入stack1，因为下一次出队列还要在stack2中完成，并且下一次出队列取出的数据仍是stack2的栈顶元素。如果约定每次出队列时都从stack2的栈顶获取数据，入队列时都把数据压入stack1，当stack2中的数据为空后再将stack1中的数据压入stack2，那么stack2中的数据就会始终排在stack1中数据的前面，stack1的栈顶相当于队列的队尾，stack2的栈顶相当于队列的队首。如图1-59所示。

总结一下改进后的方法：在入队列时，将元素压入stack1；在出队列时，判断stack2是否为空，如果stack2不为空，则直接取出stack2的栈顶元素，如果stack2为空，则将stack1中的元素逐一弹出并压入stack2，再取出stack2的栈顶元素。

下面给出用两个栈实现一个队列的Java代码及测试程序。

上述Java代码实现了用两个栈模拟一个队列的功能，通过两个栈之间的数据交换实现了入队列和出队列，同时定义了判断队列是否为空的函数boolean inEmptyQueue（），以及获取队列中元素数量的函数int getCount（）。

代码中用到的栈类MyStack就是前面给出的MyStack的定义。这里需要注意的是，在实现inEmptyQueue（）函数和getCount（）函数时，会用到MyStack类的函数isEmpty（）和getCount（），这两个函数在MyStack类中的定义如下。

在测试程序中，首先将整数1、2、3、4、5顺序入队列，此时队列的状态为1->2->3->4->5；然后将队头的两个元素出队列，此时队列状态为3->4->5；最后将后3个元素出队列，此时队列为空。运行结果如图1-60所示。

本题完整的代码及测试程序可从“微信公众号＠算法匠人→匠人作品→《算法大爆炸》全书源代码资源→1-11”中获取。 6gJ70TNNfSMpeT5Jm+jT+4PtckGG5iARzQGnNM0xBNGkMa7C66dqW0Gny9rfqaOF