1.1.1 数据结构的定义#

数据是描述客观事物的数、字符以及所有能输入计算机中并被计算机程序处理的符号的集合。例如，日常生活中使用的各种文字、数字和特定符号都是数据。从计算机的角度看，数据是所有能被输入计算机中且能被计算机处理的符号的集合。它是计算机操作的对象的总称，也是计算机处理的信息的某种特定的符号表示形式。

通常以数据元素作为数据的基本单位（例如，A班中的每个学生记录都是一个数据元素），也就是说数据元素是组成数据的有一定意义的基本单位，在计算机中通常作为整体处理，有些情况下数据元素也称为元素、结点、记录等。有时候，一个数据元素可以由若干个数据项组成。数据项是具有独立含义的数据最小单位，也称为域[例如，A班中的每个数据元素（学生记录）是由学号、姓名、性别和班号等数据项组成]。

数据对象是性质相同的有限个数据元素的集合，它是数据的一个子集，例如大写字母数据对象是集合 C = {‘A’, ‘B’, ‘C’, …, ‘Z’}；1～100 的整数数据对象是集合 N = {1, 2, …, 100}。在默认情况下，数据结构中的数据都是指的数据对象。

数据结构是指所涉及的数据元素的集合以及数据元素之间的关系，由数据元素之间的关系构成结构，因此可把数据结构看成是带结构的数据元素的集合。数据结构包括如下几个方面：

1. 数据元素之间的逻辑关系，即数据的逻辑结构，它是数据结构在用户面前呈现的形式。
2. 数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，也称为数据的物理结构。
3. 施加在该数据上的操作，即数据的运算。

数据的逻辑结构是从逻辑关系(主要是指数据元素的相邻关系)上描述数据的，它与数据的存储无关，是独立于计算机的，因此数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

1.1.2 数据的逻辑结构#

1. 逻辑结构的表示

   为了更通用地描述数据的逻辑结构，通常采用二元组表示数据的逻辑结构，一个二元组如下：

   $$B = (D, R)$$

   其中 B 是一种逻辑数据结构，D 是数据元素的集合，在 D 上数据元素之间可能存在多种关系，R 是所有关系的集合，即

   $$D = {dᵢ | 0 ≤ i ≤ n-1, n ≥ 0}$$ $$R = {rⱼ | 1 ≤ j ≤ m, m ≥ 0}$$

   其中 dᵢ 表示集合 D 中的第 i (0≤i≤n-1) 个数据元素（或结点），n 为 D 中数据元素的个数，特别地，若 n=0，则 D 是一个空集，此时 B 也就无结构可言；rⱼ (1≤j≤m) 表示集合 R 中的第 j 个关系，m 为 R 中关系的个数，特别地，若 m=0，则 R 是一个空集，表明集合 D 中的数据元素间不存在任何关系，彼此是独立的，这和数学中集合的概念是一致的。

   说明： 为了方便起见，数据结构中元素的逻辑序号统一从 0 开始。

   R 中的某个关系 rⱼ (1≤j≤m) 是序偶的集合，对于 rⱼ 中的任一序偶 <x, y> (x, y ∈ D)，把 x 叫作序偶的第一元素，把 y 叫作序偶的第二元素，又称序偶的第一元素为第二元素的前驱元素，称第二元素为第一元素的后继元素。例如在 <x, y> 的序偶中，x 为 y 的前驱元素，而 y 为 x 的后继元素。

   若某个元素没有前驱元素，则称该元素为开始元素；若某个元素没有后继元素，则称该元素为终端元素。

   对于对称序偶，满足这样的条件：若 <x, y> ∈ r (r ∈ R)，则 <y, x> ∈ r (x, y ∈ D)，可用圆括号代替尖括号，即 (x, y) ∈ r。

   对于 D 中的每个数据元素，通常用一个关键字来唯一标识，例如高等数学成绩表中学生成绩记录的关键字为学号。

   示例：全国部分城市交通图（假设城市名为关键字）的二元组表示如下。

   $$\begin{aligned}B &= (D, R) \\ D &= {北京, 郑州, 武汉, 长沙, 南京, 南昌, 杭州, 上海} \\ R &= \{r₁\} \space \text{->表示只有一种逻辑关系} \\ r₁ &= { (北京, 郑州), (北京, 南京), (郑州, 武汉), (武汉, 南京), (武汉, 长沙), (南京, 南昌), (南京, 上海), (南京, 杭州), (南昌, 杭州), (南昌, 上海) }\end{aligned}$$

2. 逻辑结构的类型

   在现实生活中数据呈现不同类型的逻辑结构，归纳起来数据的逻辑结构主要分为以下类型。

   （1）集合：结构中的数据元素之间除了“同属于一个集合”的关系外没有其他关系，与数学中集合的概念相同。

   （2）线性结构：若结构是非空的，则有且仅有一个开始元素和终端元素，并且所有元素最多只有一个前驱元素和一个后继元素。

   高等数学成绩表中，每一行为一个学生成绩记录（或成绩元素），其逻辑结构特性是只有一个开始记录（比如姓名为王华的记录）和一个终端记录（也称为尾记录，比如姓名为李英的记录），其余每个记录只有一个前驱记录和一个后继记录，也就是说记录之间存在一对一的关系，其逻辑结构特性为线性结构。

   （3）树形结构：若结构是非空的，则有且仅有一个元素为开始元素（也称为根结点），可以有多个终端元素，每个元素有零个或多个后继元素，除开始元素外每个元素有且仅有一个前驱元素。

   某大学组织结构图的逻辑结构特性是只有一个开始结点（即大学名称结点），有若干个终端结点（例如科学系等），每个结点有零个或多个下级结点，也就是说结点之间存在一对多的关系，其逻辑结构特性为树形结构。

   （4）图形结构：若结构是非空的，则每个元素可以有多个前驱元素和多个后继元素。

   全国部分城市交通线路图的逻辑结构特性是每个结点和一个或多个结点相连，也就是说结点之间存在多对多的关系，其逻辑结构特性为图形结构。

1.1.3 数据的存储结构#

1. 顺序存储结构

顺序存储结构是把逻辑上相邻的元素存储在物理位置上相邻的存储单元里，元素之间的逻辑关系由存储单元的邻接关系来体现（称为直接映射）。通常顺序存储结构是借助于计算机程序设计语言（例如 Java、C/C++语言等）的数组来实现。

顺序存储方法的主要优点是节省存储空间，因为分配给数据的存储单元全部用于存放元素值，元素之间的逻辑关系没有占用额外的存储空间。在采用这种方法时，可实现对结点的随机存取，即每个元素对应一个序号，由该序号可直接计算出元素的存储地址。顺序存储方法的主要缺点是初始空间大小难以确定，插入和删除操作需要移动较多的元素。

2. 链式存储结构

链式存储结构中每个逻辑元素用一个结点存储，不要求逻辑上相邻的元素在物理位置上也相邻，元素间的逻辑关系用附加的指针域来表示。由此得到的存储表示称为链式存储结构，它通常要借助于计算机程序设计语言的指针（或者引用）来实现。

链式存储方法的主要优点是便于进行插入和删除操作，实现这些操作仅需要修改相应结点的指针字段，不必移动结点。与顺序存储方法相比，链式存储方法的主要缺点是存储空间的利用率较低，因为分配给数据的存储单元有一部分被用来存储元素之间的逻辑关系。另外，由于逻辑上相邻的元素在存储空间中不一定相邻，所以链式存储方法不能对元素进行随机存取。

3. 索引存储结构

索引存储结构通常是在存储元素信息的同时还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是（关键字，地址），关键字唯一标识一个元素，索引表按关键字有序排列，地址作为指向元素的指针。这种带有索引表的存储结构可以大大提高数据查找的速度。

线性结构采用索引存储方法后可以对元素进行随机访问，在进行插入、删除运算时只需移动在索引表中对应元素的存储地址，而不必移动存放在元素表中的数据，所以仍保持较高的数据修改运算效率。索引存储方法的缺点是增加了索引表，降低了存储空间的利用率。

4. 哈希（或散列）存储结构

哈希存储结构的基本思想是根据元素的关键字通过哈希函数直接计算出一个值，并将这个值作为该元素的存储地址。

哈希存储方法的优点是查找速度快，只要给出待查元素的关键字就可以立即计算出该元素的存储地址。与前 3 种存储方法不同的是，哈希存储方法只存储元素的数据，不存储元素之间的逻辑关系。哈希存储方法一般只适用于要求对数据能够进行快速查找和插入的场合。

1.1.4 数据的运算#

将数据存放在计算机中的目的是为了实现一种或多种运算。运算包括功能描述(或运算功能)和功能实现(或运算实现)，前者是基于逻辑结构的，是用户定义的，是抽象的；后者是基于存储结构的，是程序员用计算机语言或伪码表示的，是详细的过程，其核心是设计实现某一运算功能的处理步骤，即算法设计。

1.1.5 数据结构和数据类型#

1. 数据类型

   数据类型是一组性质相同的值的集合和定义在此集合上的一组操作的总称。

   例如在高级语言中已实现的或非高级语言直接支持的数据结构即为数据类型。在程序设计语言中，一个变量的数据类型不仅规定了这个变量的取值范围，而且定义了这个变量可用的运算。

   总之，数据结构是指计算机处理的数据元素的组织形式和相互关系，而数据类型是某种程序设计语言中已实现的数据结构。在程序设计语言提供的数据类型的支持下，可以根据从问题中抽象出来的各种数据模型逐步构造出描述这些数据模型的各种新的数据结构。

2. 抽象数据类型

   抽象数据类型 (Abstract Data Type, ADT) 指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算，而不考虑计算机的具体存储结构和运算的具体实现算法。抽象数据类型中的数据对象和数据运算的声明与数据对象的表示和数据运算的实现相互分离，也称为抽象模型。

   “抽象”意味着应该从与实现方法无关的角度研究数据结构，只关心数据结构做什么，而不是如何实现。但是在程序中使用数据结构之前必须提供实现方法，并且还要关心运算的执行效率。

   一个具体问题的抽象数据类型的定义通常采用简洁、严谨的文字描述，一般包括数据对象（即数据元素的集合）、数据关系和基本运算 3 个方面的内容。抽象数据类型可用 (D, S, P) 三元组表示，其中 D 是数据对象，S 是 D 上的关系集，P 是 D 中数据运算的基本运算集。其基本格式如下：

   1
   ADT 抽象数据类型名
   2
   {
   3
       数据对象：数据对象的声明
   4
       数据关系：数据关系的声明
   5
       基本运算：基本运算的声明
   6
   }
   7
   ADT 抽象数据类型名
   

   其中基本运算的声明格式如下：

   1
   基本运算名(参数表)：运算功能描述
   

   示例：

   1
   ADT Stack
   2
   {
   3
       数据对象：D = {a_i | a_i ∈ ElemType, i = 1, 2, ..., n, n ≥ 0}
   4
                   （即栈中元素类型为 ElemType，个数 n 可以为 0）
   5
   
   6
       数据关系：R = {<a_{i-1}, a_i> | a_{i-1}, a_i ∈ D, i = 2, ..., n}
   7
                   （元素按线性顺序排列，后进先出）
   8
   
   9
       基本运算：
   10
           InitStack(&S)：初始化空栈 S。
   11
           DestroyStack(&S)：销毁栈 S，释放所占空间。
   12
           ClearStack(&S)：将栈 S 置为空栈。
   13
           StackEmpty(S)：若栈 S 为空返回 true，否则返回 false。
   14
           StackLength(S)：返回栈 S 中元素个数。
   15
           GetTop(S, &e)：若栈非空，用 e 返回栈顶元素。
   16
           Push(&S, e)：将元素 e 压入栈 S 的栈顶。
   17
           Pop(&S, &e)：若栈非空，删除栈顶元素，并用 e 返回其值。
   18
           StackTraverse(S, visit())：从栈底到栈顶依次对每个元素调用 visit() 函数。
   19
   }
   20
   ADT Stack
   

   抽象数据类型有两个重要特征，即数据抽象和数据封装。所谓数据抽象，是指用 ADT 描述程序处理的实体时强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。所谓数据封装，是指将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。抽象数据类型需要通过固有数据类型（高级编程语言中已实现的数据类型，例如 Java 中的类）来实现。

1.2.1 什么是算法#

数据元素之间的关系有逻辑关系和物理关系，对应的运算有逻辑结构上的运算（抽象运算）和具体存储结构上的运算（运算实现）。算法是在具体存储结构上实现某个抽象运算。

确切地说，算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示计算机的一个或多个操作。所谓算法设计，就是把逻辑层面设计的接口（抽象运算）映射到实现层面具体的实现方法（算法）。

（1）有穷性：指算法在执行有限的步骤之后自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。

（2）确定性：对于每种情况下执行的操作在算法中都有确定的含义，不会出现二义性，并且在任何条件下算法都只有一条执行路径。

（3）可行性：算法的每条指令都是可执行的，即便人借助纸和笔都可以完成。

（4）输入性：算法有零个或多个输入。在大多数算法中输入参数是必要的，但对于较简单的算法，例如计算 1+2 的值，不需要任何输入参数，因此算法的输入可以是零个。

（5）输出性：算法至少有一个或多个输出。算法用于某种数据处理，如果没有输出，这样的算法是没有意义的，算法的输出是和输入有着某些特定关系的量。

1.2.2 算法描述#

1.3.1 算法设计的要求#

算法设计应满足以下几个要求。

（1）正确性：要求算法能够正确地执行预先规定的功能和性能要求，这是最重要也是最基本的标准。

（2）可使用性：要求算法能够很方便地使用，这个特性也叫作用户友好性。

（3）可读性：算法应该易于人们理解，也就是可读性好。为了达到这个要求，算法的逻辑必须是清晰的、简单的和结构化的。

（4）健壮性：要求算法具有很好的容错性，即提供异常处理，能够对不合理的数据进行检查，不经常出现异常中断或死机现象。

（5）高时间性能与低存储量需求：对于同一个问题，如果有多种算法可以求解，执行时间少的算法时间性能高。算法存储量指的是算法执行过程中所需的存储空间。算法的时间性能和存储量都与问题的规模有关。

1.3.2 算法的时间性能分析#

一、基本概念

• 输入规模 ( n )：通常指问题的大小，例如数组长度、图的顶点数等。
• 基本操作：算法中最耗时、重复执行的操作，如比较、赋值、加法等。
• 时间复杂度：用大 O 记号（Big-O notation）表示，描述上界（最坏情况）的增长速率。

二、分析步骤

1. 确定输入规模 ( n )

   例如：对长度为 ( n ) 的数组排序。

2. 找出基本操作

   通常是循环体内的操作，如 a[i] == key、sum += a[i] 等。

3. 计算基本操作的执行次数 ( T(n) )

   • 单层循环（从 0 到 ( n-1 )）：执行约 ( n ) 次 → ( T(n) = n )
   • 双重嵌套循环（两层都到 ( n )）：执行约 ( n^2 ) 次 → ( T(n) = n^2 )
   • 对数循环（如 i *= 2）：执行约 ( \log_2 n ) 次
   • 分治算法（如归并排序）：( T(n) = 2T(n/2) + n ) → 解得 ( T(n) = O(n \log n) )

4. 用大 O 表示法简化 ( T(n) )

   保留最高阶项，忽略常数和低阶项：

   • ( T(n) = 3n^2 + 5n + 10 ) → ( O(n^2) )
   • ( T(n) = 100 \log n + 20 ) → ( O(\log n) )
   • ( T(n) = 5 )（与 ( n ) 无关）→ ( O(1) )

三、常见时间复杂度（从小到大）

实用建议：尽量设计 ( O(n \log n) ) 或更低的算法；( O(n^2) ) 在 ( n > 10^4 ) 时可能超时；指数级通常不可行。

四、示例分析

示例 1：双重循环

1
for (int i = 0; i < n; i++) {
2
    for (int j = 0; j < n; j++) {
3
        if (a[i] == a[j]) count++;  // 基本操作
4
    }
5
}

• 执行次数：( n \times n = n^2 )
• 时间复杂度：( O(n^2) )

示例 2：二分查找

1
while (low <= high) {
2
    mid = (low + high) / 2;
3
    if (arr[mid] == key) return mid;
4
    else if (arr[mid] < key) low = mid + 1;
5
    else high = mid - 1;
6
}

• 每次将问题规模减半 → 循环约 ( \log_2 n ) 次
• 时间复杂度：( O(\log n) )

1.3.3 算法的存储空间分析#

一个算法的存储量包括形参所占空间和临时变量所占空间。在对算法进行存储空间分析时只考虑临时变量所占空间，如图 1.17 所示，其中临时空间为变量 i、maxi 占用的空间。所以，空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度，一般也是问题规模 n 的函数，并以数量级形式给出，记作 S(n) = O(g(n))，其中“O”的含义与时间复杂度分析中的相同。若一个算法所需临时空间相对于问题规模来说是常数[或者说算法的空间复杂度为 O(1) ，则称此算法为原地工作或就地工作。

2.1.1 什么是线性表#

线性表严格的定义是具有相同特性的数据元素的一个有限序列。其特征有三，一是所有数据元素类型相同；二是线性表由有限个数据元素构成；三是线性表中的数据元素与位置相关，即每个数据元素有唯一的序号（或索引），这一点表明线性表不同于集合，在线性表中可以出现值相同的数据元素（它们的序号不同），而集合中不会出现值相同的数据元素。

线性表的逻辑结构一般表示为 $a_0, a_1, \cdots, a_i, a_{i+1}, \cdots, a_{n-1}$，用图形表示的逻辑结构如图 2.1 所示。

说明：线性表中每个元素 $a_i$ 的唯一位置通过序号或者索引 i 表示，为了使算法设计方便，将逻辑序号和存储序号统一，均假设从 0 开始，这样含 n 个元素的线性表的元素序号 i 满足 $0 \leq i \leq n-1$。

其中，用 $n (n \geq 0)$ 表示线性表的长度（即线性表中数据元素的个数）。当 n=0 时表示线性表是一个空表，不包含任何数据元素。

2.1.2 线性表的抽象数据类型描述#

线性表的抽象数据类型描述如下：

1
ADT List
2
{
3
    数据对象：
4
        D = {aᵢ | 0 ≤ i ≤ n-1, n ≥ 0, aᵢ 为 E 类型}          // E 是用户指定的类型
5

6
    数据关系：
7
        r = {<aᵢ, aᵢ₊₁> | aᵢ, aᵢ₊₁ ∈ D, i = 0, ..., n-2}
8

9
    基本运算：
10
        void CreateList(E[] a)：由 a 数组中的全部元素建立线性表的相应存储结构。
11
        void Add(E e)：将元素 e 添加到线性表末尾。
12
        int size()：求线性表的长度。
13
        void Setsize(int nlen)：设置线性表的长度为 nlen。
14
        E GetElem(int i)：求线性表中序号为 i 的元素。
15
        void SetElem(int i, E e)：设置线性表中序号为 i 的元素值为 e。
16
        int GetNo(E e)：求线性表中第一个值为 e 的元素的序号。
17
        void swap(int i, int j)：交换线性表中序号为 i 和序号为 j 的元素。
18
        void Insert(int i, E e)：在线性表中插入数据元素 e 作为第 i 个元素。
19
        void Delete(int i)：在线性表中删除第 i 个数据元素。
20
        String toString()：将线性表转换为字符串。
21
}

2.2.1 线性表的顺序存储结构——顺序表#

线性表的顺序存储结构是把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中。线性表的顺序存储结构称为顺序表。 这里采用 Java 语言中的一维数组 data 来实现顺序表,并设定该数组的容量(存放的最多元素个数)为 capacity。线性表的长度是线性表中实际的数据元素个数，用 size 表示，随着线性表的插入和删除操作，size 是 变化的，但在任何时刻 size 都应该小于等于容量 capacity; 否则应该扩大 data 数组的容量，通常按 size 的两倍来扩大 data 数组的容量。

假设线性表的元素类型为 E，设计顺序表泛型类为 SqListClass，主要包含 data 动态泛型数组，size 成员变量表示实际的元素个数：

1
public class SqListClass <E>
2
{   final int initcapacity = 10;          //顺序表的初始容量(常量)
3
    public E[] data;                      //存放顺序表中的元素
4
    public int size;                      //存放顺序表的长度
5
    private int capacity;                 //存放顺序表的容量
6
    public SqListClass()
7
    {   data = (E[])new Object[initcapacity]; //构造方法,实现 data 和 length 的初始化
8
        capacity = initcapacity;               //强制转换为 E 类型数组
9
        size = 0;
10
    }
11
    //线性表的基本运算算法
12
}

2.2.2 线性表的基本运算算法在顺序表中的实现#

1. 在顺序表中插入 e 作为第 i 个元素: Insert(i, e)

   

   对应的算法如下：

   1
   public void Insert(int i, E e)
   2
   {
   3
       if(i < 0 || i > size)
   4
           throw new IllegalArgumentException("插入:位置i不在有效范围内"); //参数错误抛出异常
   5
       if(size == capacity)
   6
           updatecapacity(2 * size); //满时倍增容量
   7
       for(int j = size; j > i; j--)
   8
           data[j] = data[j - 1]; //将 data[i] 及后面的元素后移一个位置
   9
       data[i] = e; //插入元素 e
   10
       size++; //顺序表的长度增 1
   11
   }
   

   本算法的主要时间花在元素的移动上，元素移动的次数不仅与表长 n 有关，而且与插入位置 i 有关。有效插入位置 i 的取值是 $0 \sim n$ ，共有 n + 1 个位置可以插入元素：

   （1）当 i = 0 时移动次数为 n ，达到最大值。

   （2）当 i = n 时移动次数为 0 ，达到最小值。

   （3）其他情况需要移动 $data[i..n-1]$ 的每个元素，移动次数为 (n - 1) - i + 1 = n - i 。

   假设每个位置插入元素的概率相同， $p_i$ 表示在第 i 个位置上插入一个元素的概率，则 $p_i = \frac{1}{n+1}$ ，这样在长度为 n 的线性表中插入一个元素时所需移动元素的平均次数为：

   $$\sum_{i=0}^{n} p_i (n - i) = \frac{1}{n + 1} \sum_{i=0}^{n} (n - i) = \frac{1}{n + 1} \times \frac{n(n + 1)}{2} = \frac{n}{2}$$

   因此插入算法的平均时间复杂度为 O(n) 。

2. 在线性表中删除第 i 个数据元素： Delete(i)

   对应的算法如下：

   1
   public void Delete(int i)
   2
   {
   3
       if(i < 0 || i > size - 1)
   4
           throw new IllegalArgumentException("删除:位置i不在有效范围内"); //参数错误抛出异常
   5
       for(int j = i; j < size - 1; j++)
   6
           data[j] = data[j + 1]; //将 data[i] 之后的元素前移一个位置
   7
       size--; //顺序表的长度减 1
   8
       if(capacity > initcapacity && size == capacity / 4) //满足要求容量减半
   9
           updatecapacity(capacity / 2);
   10
   }
   

   本算法的主要时间花在元素的移动上，元素移动的次数也与表长 n 和删除元素的位置 i 有关，有效删除位置 i 的取值是 $0 \sim n-1$，共有 n 个位置可以删除元素：

   （1）当 i = 0 时移动次数为 n - 1，达到最大值。

   （2）当 i = n - 1 时移动次数为 0，达到最小值。

   （3）其他情况需要移动 data[i+1..n-1] 的每个元素，移动次数为 (n - 1) - (i + 1) + 1 = n - i - 1。

   假设 $p_i$ 表示删除第 i 个位置上元素的概率，则 $p_i = \frac{1}{n}$，所以在长度为 n 的线性表中删除一个元素时所需移动元素的平均次数为：

   $$\sum{i=0}^{n-1} p_i (n - i - 1) = \frac{1}{n} \sum{i=0}^{n-1} (n - i - 1) = \frac{1}{n} \times \frac{n(n - 1)}{2} = \frac{n - 1}{2}$$

   因此删除算法的平均时间复杂度为 O(n)。

2.2.3 顺序表的应用算法设计示例#

1. 基于整体建立顺序表的算法设计

   【例 2.1】 对于含有 n 个整数元素的顺序表 L ，设计一个尽可能高效的算法删除所有相邻重复的元素，即多个相邻重复的元素仅仅保留一个，例如 L = (1, 2, 2, 2, 1) ，删除后 L = (1, 2, 1) ，并给出算法的时间复杂度和空间复杂度。

   解：采用例 2.4 中解法 1 的整体创建顺序表的算法思路，首先将序号为 0 的元素插入结果顺序表中， k 表示结果顺序表中元素的个数（初始时 k = 1 ，因为开始元素一定是要保留的元素），其末尾元素的序号为 k - 1 。从 i = 1 开始扫描原 L ，若当前元素值不等于结果顺序表中的末尾元素，则它不是相邻重复的元素，将其插入结果顺序表中。最后重新设置结果顺序表的长度。

   对应的算法如下：

   1
   public static void Delsame(SqListClass<Integer> L)
   2
   {
   3
       int k = 1;  // k: 左指针(= 最终有效元素个数 - 1)
   4
       for(i = 1; i < L.size(); i++)  // i: 右指针
   5
           if(L.GetElem(i) != L.GetElem(k)) //将不是相邻重复的元素插入
   6
           {
   7
               L.SetElem(++k, L.GetElem(i)); // 新的有效元素, k 向右移动一位
   8
           }
   9
       L.Setsize(k+1); //重置长度
   10
   }
   

   上述算法的时间复杂度为 O(n) ，空间复杂度均为 O(1) 。

2. 有序顺序表的算法设计

   【例 2.7】 一个长度为 $n ( n \geq 1)$ 的升序序列 S，处在第 $\lceil n/2 \rceil$ 个位置的数称为 S 的中位数。例如，若序列 $S_1 = (11, 13, 15, 17, 19)$，则 $S_1$ 的中位数是 15。两个序列的中位数是包含它们所有元素的升序序列的中位数。例如，若 $S_2 = (2, 4, 6, 8, 20)$，则 $S_1$ 和 $S_2$ 的中位数是 11。现有两个等长的升序序列 A 和 B，设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列 A 和 B 的中位数。假设两个升序序列分别用顺序表 A 和 B 存储，所有元素为整数。

   解：两个升序序列分别用 SqListClass<Integer> 对象 A 和 B 存储，它们的元素个数均为 n。若采用二路归并得到含 2n 个元素的升序序列 C，则其中序号为 n-1 的元素就是两个序列的中位数。

   实际上这里求出的中位数仅仅是一个元素，没有必要求出整个 C 中的 2n 个元素，为此用 k 累计归并元素的个数（初始为 0），当归并到第 n 个元素（此时 k == n）时，两个比较中较小的那个元素就是中位数。

   对应的算法如下：

   1
   public static int Middle(SqListClass<Integer> A, SqListClass<Integer> B)
   2
   {
   3
       int i=0, j=0, k=0;                      // i -> A; j -> B; k -> total step
   4
       int n = A.size();                       // 只获取一次 size，因为 A 和 B 等长
   5
       while(i < n && j < n)                   // 当前归并的元素个数增 1
   6
       {
   7
           k++;                                // 由于最终判断的是 k = n = A.size(); 所以 k 要提前+1
   8
           if(A.GetElem(i) < B.GetElem(j))     // 归并 A 中较小的元素
   9
           {
   10
               if(k == n)                      // 若当前归并的元素是第 n 个元素
   11
                   return A.GetElem(i);        // 返回 A 中的当前元素
   12
               i++;
   13
           }
   14
           else                                // 归并 B 中较小的元素
   15
           {
   16
               if(k == n)                      // 若当前归并的元素是第 n 个元素
   17
                   return B.GetElem(j);        // 返回 B 中的当前元素
   18
               j++;
   19
           }
   20
       }
   21
       return 0;
   22
   }
   

   上述算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

2.2.4 顺序表容器——ArrayList#

在 Java 中提供了列表接口 List (其中元素为对象序列)，它是 Collection 接口的子接口，List 有一个重要的实现类——ArrayList 类，它采用动态数组存储对象序列，可以看成是顺序存储结构的表在 Java 语言中的实现。在实际应用中可以用 ArrayList 类对象作为顺序表，使用其提供的各种方法完成更复杂问题的求解。

1. ArrayList 类的基本应用

ArrayList 类的构造方法如下。

(1) ArrayList()：构造一个初始容量为 10 的空列表。 (2) ArrayList(int initialCapacity)：构造一个具有指定初始容量的空列表。 (3) ArrayList(Collection<? extends E> c)：构造一个包含指定集合的元素的列表。

ArrayList 类的主要方法如下。

(1) boolean isEmpty()：如果列表中不包含元素，则返回 true。 (2) int size()：返回此列表中的元素数。 (3) add(E e)：向列表的尾部添加指定的元素。 (4) void add(int index, E element)：在列表的指定位置插入指定元素。 (5) boolean contains(Object o)：如果列表中包含指定的元素，则返回 true。 (6) E get(int index)：返回列表中指定位置的元素。 (7) E set(int index, E element)：用指定元素替换列表中指定位置的元素。 (8) int indexOf(Object o)：返回此列表中第一次出现的指定元素的索引。如果此列表中不包含该元素，则返回 -1。 (9) int lastIndexOf(Object o)：返回此列表中最后出现的指定元素的索引。如果列表中不包含此元素，则返回 -1。 (10) void clear()：从列表中移除所有元素。 (11) E remove(int index)：移除列表中指定位置的元素。 (12) boolean remove(Object o)：从此列表中移除第一次出现的指定元素（如果存在）。

2. ArrayList 类元素的排序

在许多应用中需要对顺序表元素排序，后面第 10 章专门讨论各种排序算法设计，这里从应用的角度介绍 ArrayList 类提供的几种排序方法。

若 ArrayList 对象中的元素属于 Java 基本数据类型，例如：

ArrayList<Integer> myarrlist = new ArrayList<Integer>(); //元素类型为整型

则排序方法如下。

(1) 按元素递增排序：Collections.sort(myarrlist); (2) 按元素递减排序：Collections.sort(myarrlist, Collections.reverseOrder());

若 ArrayList 对象中的元素属于类类型，则需要指定按什么成员变量排序、按什么次序排序等，主要方式如下：

1) 设置 Comparable 排序接口

若一个类实现了 Comparable 接口，就意味着“该类支持排序”，为此重写 compareTo() 方法以定制排序方式。compareTo() 方法的用法是“当前对象的属性 . compareTo (比较对象的属性)”，若当前对象的值<比较对象的值，返回一个负整数；若当前对象的值=比较对象的值，返回 0；若当前对象的值>比较对象的值，返回一个正整数。然后调用 Collections.sort(ArrayList 对象) 进行排序。

2) 设置 Comparator 对象比较器接口

若需要定制某个类对象的排序次序，而该类本身不支持排序（即没有实现 Comparable 排序接口），可以建立一个“比较器”来进行排序。这个“比较器”只需要实现 Comparator 接口即可。其格式如下：

1
Collections.sort(ArrayList 对象, new Comparator<元素类> {
2
    @Override
3
    public int compare(元素类 o1, 元素类 o2) {
4
        return o1.比较属性().compareTo(o2.比较属性());
5
    }
6
});

其中，compare(o1, o2) 方法的用法是根据第一个参数小于、等于或大于第二个参数分别返回负整数、零或正整数。

3) 调用 ArrayList 类的 sort() 方法

在 Java 8 中增加了使用 Comparator 的 comparing() 进行排序，按照 ArrayList 类对象中元素类的排序属性进行递增排序的格式如下：

ArrayList 类对象.sort(Comparator.comparing(元素类::排序属性));

按照 ArrayList 类对象中元素类的排序属性进行递减排序的格式如下：

ArrayList 类对象.sort(Comparator.comparing(元素类::排序属性).reversed());

如果是按多个成员变量值排序，还可以增加 thenComparing() 等，例如 ArrayList 类对象 myarrlist 中的元素为 User 类对象，User 类有 3 个成员变量 F1、F2 和 F3，对应的属性分别为 getF1()、getF2() 和 getF3()，则以下语句依次按 F1、F2 和 F3 递增排序：

1
myarrlist.sort(comparing(User::getF1)
2
                .thenComparing(User::getF2)
3
                .thenComparing(User::getF3));

2.3.1 线性表的链式存储结构——链表#

线性表的链式存储结构称为链表。在链表中每个结点不仅包含有元素本身的信息（称之为数据成员），而且包含有元素之间逻辑关系的信息，即一个结点中包含有后继结点的地址信息或者前驱结点的地址信息，称为指针成员，这样可以通过一个结点的指针成员方便地找到后继结点或者前驱结点。

如果每个结点只设置一个指向其后继结点的指针成员，这样的链表称为线性单向链表，简称单链表；如果每个结点中设置两个指针成员，分别用于指向其前驱结点和后继结点，这样的链表称为线性双向链表，简称双链表。无前驱结点或者后继结点的相应指针成员用常量 null 表示。

在单链表中，当访问过一个结点后，只能接着访问它的后继结点，而无法访问它的前驱结点。在双链表中，当访问过一个结点后，既可以依次向后访问后继结点，也可以依次向前访问前驱结点。

为了便于在链表中插入和删除结点，通常链表带有一个头结点，并通过头结点指针唯一地标识该链表，因为从头指针所指的头结点出发，沿着结点的链可以访问到链表中的每个结点。图 2.14(a) 是带头结点的单链表 head，图 2.14(b) 是带头结点的双链表 dhead，分别称为 head 单链表和 dhead 双链表。

通常将 p 指向的结点称为 p 结点或者结点 p，头结点为 head 的链表称为 head 链表，头结点中不存放任何数据元素(空表是仅包含头结点的链表)，存放序号为 0 的元素的结点称为开始结点或者首结点,存放终端元素的结点称为终端结点或者尾结点。一般链表的长度不计头结点，仅仅指其中数据结点的个数。

2.3.2 单链表#

在单链表中，假定每个结点为 LinkNode<E> 泛型类对象，它包括存储元素的数据成员，这里用 data 表示，并假设其数据类型为 E，还包括存储后继结点的指针成员，这里用 next 表示。LinkNode<E> 泛型类的定义如下：

1
class LinkNode<E>          //单链表结点泛型类
2
{
3
    E data;
4
    LinkNode<E> next;
5
    public LinkNode()      //构造方法
6
    {
7
        next = null;
8
    }
9
    public LinkNode(E d)   //重载构造方法
10
    {
11
        data = d;
12
        next = null;
13
    }
14
}

为了使算法设计简单、清晰，上述 LinkNode<E> 泛型类中的 data 和 next 成员默认为 public 权限，如果设计为 private 权限，则需要增加相应的存取方法。

设计单链表泛型类 LinkedListClass<E>，其中 head 为单链表的头结点，构造方法用于创建这个头结点，并且置 head 结点的 next 为空，所以满足 head.next == null 条件的单链表为一个空单链表：

1
public class LinkedListClass<E>     //单链表泛型类
2
{
3
    LinkNode<E> head;               //存放头结点
4
    public LinkedListClass()         //构造方法
5
    {
6
        head = new LinkNode<E>();    //创建头结点
7
        head.next = null;            //头结点的 next 成员置为 null
8
    }
9
    //基本运算算法
10
}

1. 插入和删除结点操作

在单链表中，插入和删除结点是最常用的操作，它是建立单链表和相关基本运算算法的基础。

1) 插入结点操作

插入运算是将结点 s 插入单链表中 p 结点的后面。如图 2.16(a) 所示，为了插入结点 s，需要修改结点 p 中的指针成员，令其指向结点 s，而结点 s 中的指针成员应指向 p 结点的后继结点，从而实现 3 个结点之间逻辑关系的变化，其过程如图 2.16 所示。

上述指针修改用 Java 语句描述如下：

s.next = p.next; p.next = s;

注意： 这两个语句的顺序不能颠倒，如果先执行 p.next = s 语句，会找不到指向值为 b 的结点，再执行 s.next = p.next 语句，相当于执行 s.next = s，这样插入操作错误。

2. 整体建立单链表

所谓整体建立单链表就是一次性创建单链表的多个结点，这里是通过一个含有 n 个元素的 a 数组来建立单链表。建立单链表的常用方法有以下两种。

1) 用头插法建表

该方法从一个空表开始，依次读取数组 a 中的元素，生成新结点 s，将读取的数据存放到新结点的数据成员中，然后将新结点 s 插入当前链表的表头上，如图 2.18 所示。重复这一过程，直到 a 数组的所有元素读完为止。

采用头插法建表的算法如下：

1
public void CreateListF(E[] a)     //头插法：由数组 a 整体建立单链表
2
{
3
    LinkNode<E> s;
4
    for (int i = 0; i < a.length; i++)
5
    {
6
        s = new LinkNode<E>(a[i]);   //新建存放 a[i] 元素的结点 s
7
        s.next = head.next;          //将 s 结点插入开始结点之前、头结点之后
8
        head.next = s;
9
    }
10
}

本算法的时间复杂度为 O(n)，其中 n 为 a 数组中元素的个数。

若数组 a 中包含 4 个元素 ‘a’、‘b’、‘c’ 和 ‘d’，调用 CreateListF(a) 建立的单链表如图 2.19 所示。从中看到，用头插法建立的单链表中数据结点的次序与 a 数组中的次序正好相反。

2) 用尾插法建表

用头插法建立链表虽然算法简单，但生成的链表中结点的次序和原数组中元素的顺序相反。若希望两者次序一致，可采用尾插法建立。该方法是将新结点 s 插入当前链表的表尾上，为此需要增加一个尾指针 t，使其始终指向当前链表的尾结点，如图 2.20 所示。

采用尾插法建表的算法如下：

1
public void CreateListR(E[] a)     //尾插法：由数组 a 整体建立单链表
2
{
3
    LinkNode<E> s, t;
4
    t = head;                      //t 始终指向尾结点，开始时指向头结点
5
    for(int i = 0; i < a.length; i++)
6
    {
7
        s = new LinkNode<E>(a[i]); //新建存放 a[i] 元素的结点 s
8
        t.next = s;                //将 s 结点插入 t 结点之后
9
        t = s;
10
    }
11
    t.next = null;                 //将尾结点的 next 成员置为 null
12
}

本算法的时间复杂度为 O(n)，其中 n 为 a 数组中元素的个数。

若数组 a 中包含 4 个元素 ‘a’、‘b’、‘c’ 和 ‘d’，调用 CreateListR(a) 建立的单链表如图 2.21 所示。从中可以看到，用尾插法建立的单链表中数据结点的次序与 a 数组中的次序正好相同。

2.3.3 单链表的应用算法设计示例#

1. 基于单链表基本操作的算法设计

在这类算法设计中主要包括单链表结点的查找、插入和删除等基本操作。

【例 2.10】 有一个长度大于 2 的整数单链表 L，设计一个算法查找 L 的中间位置的元素。例如，L = (1, 2, 3)，返回元素为 2；L = (1, 2, 3, 4)，返回元素为 2。

快慢指针法： 设置快指针 fast 和慢指针 slow，首先均指向首结点，当 fast 结点后面至少存在两个结点时，让慢指针 slow 每次后移一个结点，让快指针 fast 每次后移两个结点。否则 slow 指向的结点就是满足题目要求的结点。对应的算法如下：

1
public static int Middle2(LinkedListClass<Integer> L)
2
{
3
    LinkNode<Integer> slow = L.head.next;
4
    LinkNode<Integer> fast = L.head.next;     // 均指向首结点
5
    while(fast.next != null && fast.next.next != null) // 找中间位置的 p 结点
6
    {
7
        slow = slow.next;                     // 慢指针每次后移一个结点
8
        fast = fast.next.next;                // 快指针每次后移两个结点
9
    }
10
    return slow.data;
11
}

2.3.4 双链表#

对于双链表，采用类似于单链表的结点类型定义，双链表中每个结点的泛型类 DLinkNode<E> 定义如下：

1
class DLinkNode<E>          //双链表结点泛型类
2
{
3
    E data;                 //结点元素值
4
    DLinkNode<E> prior;     //前驱结点指针
5
    DLinkNode<E> next;      //后继结点指针
6
    public DLinkNode()      //构造方法
7
    {
8
        prior = null;
9
        next = null;
10
    }
11
    public DLinkNode(E d)   //重载构造方法
12
    {
13
        data = d;
14
        prior = null;
15
        next = null;
16
    }
17
}

双链表泛型类 DLinkListClass<E> 包含双链表的基本运算方法，其中 dhead 成员为双链表的头结点：

1
public class DLinkListClass<E>     //双链表泛型类
2
{
3
    DLinkNode<E> dhead;            //存放头结点
4
    public DLinkListClass()         //构造方法
5
    {
6
        dhead = new DLinkNode<E>(); //创建头结点
7
        dhead.prior = null;
8
        dhead.next = null;
9
    }
10
    //线性表的基本运算算法
11
}

1. 插入和删除结点操作

在双链表中插入和删除结点是最基本的操作，这也是双链表算法设计的基础。

1) 插入结点操作

假设在双链表中的 p 结点之后插入一个 s 结点，插入过程如图 2.27 所示，共涉及 4 个指针成员的变化。其操作语句描述如下：

1
s.next = p.next;
2
p.next.prior = s;
3
s.prior = p;
4
p.next = s;

说明： 在双链表中的 p 结点之后插入 s 结点时，p 结点是直接给定的，而 p 结点的后继结点是间接找到的，一般先做间接找到结点的相关操作，后做直接给定结点的相关操作，例如 p.next = s 总是放在前两个语句之后执行。

2) 删除结点操作

假设删除双链表中 p 结点的后继结点，删除过程如图 2.28 所示，共涉及两个指针成员的变化。其操作语句描述如下：

1
p.next.prior = p.prior;
2
p.prior.next = p.next;

2.3.5 双链表的应用算法设计示例#

2.3.6 循环链表#

循环链表是另一种形式的链式存储结构，分为循环单链表和循环双链表两种形式，它们分别是从单链表和双链表变化而来的。

1. 循环单链表

带头结点 head 的循环单链表中尾结点的 next 指针成员不再是空，而是指向头结点，从而整个链表形成一个首尾相接的环。

循环单链表的特点是从表中任一结点出发都可找到其他结点，与单链表相比，无须增加存储空间，仅对链接方式稍作修改，即可使得表处理更加方便、灵活。在默认情况下，循环单链表也是通过头结点 head 标识的。

循环单链表中的结点类型与非循环单链表中的结点类型相同，仍为 LinkNode<E>，循环单链表泛型类 CLinkListClass<E> 定义如下：

1
public class CLinkListClass<E>     //循环单链表泛型类
2
{
3
    LinkNode<E> head;               //存放头结点
4
    public CLinkListClass()          //构造方法
5
    {
6
        head = new LinkNode<E>();    //创建头结点
7
        head.next = head;            //置为空的循环单链表
8
    }
9
    //线性表的基本运算算法
10
}

循环单链表的插入和删除结点操作与非循环单链表的相同，所以两者的许多基本运算算法是相似的，主要区别如下：

(1) 初始只有头结点 head，在循环单链表的构造方法中需要通过 head.next = head 语句置为空表。

(2) 循环单链表中涉及查找操作时需要修改表尾判断的条件，例如用 p 遍历时，尾结点满足的条件是 p.next == head 而不是 p.next == null。

2. 循环双链表

循环双链表尾结点的 next 指针成员指向头结点，头结点的 prior 指针成员指向尾结点。其特点是整个链表形成两个环，由此从表中任意一个结点出发均可找到其他结点，最突出的优点是通过头结点在 O(1) 时间内找到尾结点。在默认情况下，循环双链表也是通过头结点 dhead 标识的。

循环双链表中的结点类型与非循环双链表中的结点类型相同，仍为 DLinkNode<E>，循环双链表泛型类 CDLinkListClass<E> 定义如下：

1
public class CDLinkListClass<E>     //循环双链表泛型类
2
{
3
    DLinkNode<E> dhead;              //存放头结点
4
    public CDLinkListClass()          //构造方法
5
    {
6
        dhead = new DLinkNode<E>();   //创建头结点
7
        dhead.prior = dhead;          //构成空的循环双链表
8
        dhead.next = dhead;
9
    }
10
    //线性表的基本运算算法
11
}

循环双链表的插入和删除结点操作与非循环双链表的相同，所以两者的许多基本运算算法是相似的，主要区别如下：

(1) 初始只有头结点 dhead，在循环双链表的构造方法中需要通过 dhead.prior = dhead 和 dhead.next = dhead 两个语句置为空表。

(2) 循环双链表中涉及查找操作时需要修改表尾判断的条件，例如用 p 遍历时，尾结点满足的条件是 p.next == head 而不是 p.next == null。

2.3.7 链表容器——LinkedList#

在 Java 中 List 接口还有另外一个重要的实现类 — LinkedList类，它采用循环双链表存储对象序列，可以看成是链式存储结构的表在 Java 语言中的实现。类 LinkedList 的使用方法与类 ArrayList 几乎相同，这里不详述。

3.1 栈的定义#

抽象起来，栈是一种只能在一端进行插入或删除操作的线性表。在表中允许进行插入、删除操作的一端称为栈顶。栈顶的当前位置是动态的，由一个称为栈顶指针的位置指示器来指示。表的另一端称为栈底。当栈中没有数据元素时称为空栈。栈的插入操作通常称为进栈或入栈，栈的删除操作通常称为退栈或出栈。

说明： 对于线性表，可以在中间和两端的任何地方插入和删除元素，而栈只能在同一端插入和删除元素。

栈的主要特点是“后进先出”，即后进栈的元素先出栈。每次进栈的元素都放在原当前栈顶元素之前成为新的栈顶元素，每次出栈的元素都是原当前栈顶元素。栈也称为后进先出表。

抽象数据类型栈的定义如下：

1
ADT Stack
2
{
3
    数据对象：
4
        D = {aᵢ | 0 ≤ i ≤ n-1, n ≥ 0, 元素 aᵢ 为 E 类型}
5
    数据关系：
6
        R = {r}
7
        r = {<aᵢ, aᵢ₊₁> | aᵢ, aᵢ₊₁ ∈ D, i = 0, ..., n-2}
8
    基本运算：
9
        boolean empty(): 判断栈是否为空，若栈空返回真，否则返回假。
10
        void push(E e): 进栈操作，将元素 e 插入栈中作为栈顶元素。
11
        E pop(): 出栈操作，返回栈顶元素。
12
        E peek(): 取栈顶操作，返回当前的栈顶元素。
13
}

3.1.2 栈的顺序存储结构及其基本运算算法的实现#

由于栈中元素的逻辑关系与线性表的相同，所以可以借鉴线性表的两种存储结构来存储栈。

当采用顺序存储时，分配一块连续的存储空间，用 data<E> 数组来存放栈中元素，并用一个整型变量 top（栈顶指针）指向当前的栈顶，以反映栈中元素的变化。采用顺序存储的栈称为顺序栈。

capacity 为 data 数组的容量，由于将 data[0] 端作为栈底，所以 top + 1 恰好表示栈中实际元素的个数。

图 3.4 是一个栈的动态示意图，图 3.4(a) 表示一个空栈，top = -1；图 3.4(b) 表示元素 a 进栈以后的状态；图 3.4(c) 表示元素 b、c、d 进栈以后的状态；图 3.4(d) 表示出栈元素 d 以后的状态。

从中看到，初始时置栈顶指针 top = -1。顺序栈的四要素如下：

(1) 栈空的条件为 top == -1。 (2) 栈满（栈上溢出）的条件为 top == capacity - 1，这里采用动态扩展容量的方式，即栈满时将 data 数组的容量扩大两倍。 (3) 元素 e 进栈操作是先将栈顶指针 top 增 1，然后将元素 e 放在栈顶指针处。 (4) 出栈操作是先将栈顶指针 top 处的元素取出，然后将栈顶指针 top 减 1。

说明： 在进栈操作中，栈中元素始终是向一端伸展的。在采用 data 数组存放栈元素时，既可以将 data[0] 端作为栈底，也可以将 data[capacity-1] 端作为栈底，但不能将 data 数组的中间位置作为栈底，这里的顺序栈设计采用前一种方式。

顺序栈泛型类 SqStackClass<E> 设计如下：

1
public class SqStackClass<E>     //顺序栈泛型类
2
{
3
    final int initcapacity = 10; //顺序栈的初始容量(常量)
4

5
    private int capacity;         //存放顺序栈的容量
6
    private E[] data;             //存放顺序栈中的元素
7
    private int top;              //存放栈顶指针
8

9
    public SqStackClass()          //构造方法，实现 data 和 top 的初始化
10
    {
11
        data = (E[]) new Object[initcapacity]; //强制转换为 E 类型数组
12
        capacity = initcapacity;
13
        top = -1;
14
    }
15

16
    private void updatecapacity(int newcapacity) //改变顺序栈的容量为 newcapacity
17
    {
18
        E[] newdata = (E[]) new Object[newcapacity];
19
        for(int i = 0; i < top; i++)            //复制原来的元素
20
            newdata[i] = data[i];
21
        capacity = newcapacity;                  //设置新容量
22
        data = newdata;                          //仍由 data 标识数组
23
    }
24
    //栈的基本运算算法
25
}

栈的部分基本运算算法如下：

1) 出栈：pop()

元素出栈只能从栈顶出，不能从栈底或中间位置出。

在出栈中，当栈空时抛出异常，否则先将栈顶元素赋给 e，然后将栈顶指针 top 减 1，若栈容量大于初始容量并且实际元素个数仅为当前容量的 1/4，则当前容量减半，最后返回 e。

对应的算法如下：

1
public E pop()                 //出栈操作
2
{
3
    if(empty())
4
        throw new IllegalArgumentException("栈空");
5
    E e = (E)data[top];
6
    top--;
7
    if(capacity > initcapacity && top + 1 == capacity / 4) //满足要求则容量减半
8
        updatecapacity(capacity / 2);
9
    return e;
10
}

2) 取栈顶元素：peek()

在栈不为空的条件下将栈顶元素赋给 e，不移动栈顶指针。对应的算法如下：

1
public E peek()                //取栈顶元素操作
2
{
3
    if(empty())
4
        throw new IllegalArgumentException("栈空");
5
    return (E)data[top];
6
}

从以上看出，栈的各种基本运算算法的时间复杂度均为 O(1)。

3.1.3 顺序栈的应用算法设计示例#

【例 3.1】 有 1～n 的 n 个元素，通过一个栈可以产生多种出栈序列，设计一个算法判断序列 b 是否为一个合法的出栈序列，并给出操作过程，要求用相关数据进行测试。

解： 先建立一个整型顺序栈 st，将进栈序列 1～n 存放到数组 a 中，判断 a 序列通过一个栈算是否得到出栈序列 b

令 i, j 分别遍历 a, b 数组（初始值均为 0），反复执行以下操作，直到 a 或者 b 数组遍历完为止：

(1) 若栈空，a[i] 进栈，i++。 (2) 若栈不空，如果栈顶元素 ≠ b[j]，将 a[i] 进栈，i++。 (3) 否则出栈一个元素，j++。

上述过程简单地说就是当栈顶元素 = b 序列的当前元素时出栈一次，否则将 a 序列的当前元素进栈。

当该过程结束，再将栈中与 b 序列相同的元素依次出栈。由于 a 序列的每个元素最多进栈一次、出栈一次，而只有出栈时 j 才后移，所以如果 b 序列遍历完 (j == n)，说明 b 序列是合法的出栈序列，返回 true，否则不是合法的出栈序列，返回 false。其中用字符串 op 记录所有的栈操作。

当上述过程返回 true 时输出 op，否则输出提示信息。对应的完整程序如下：

1
import java.util.*;
2
public class Exam3_6
3
{
4
    static String op = "";
5
    static int cnt;
6

7
    public static boolean isSerial(int[] b)    // b: 目标数组
8
    {
9
        int i, j, n = b.length;                // i: index(a); j: index(b); n: length(b)
10
        Integer e;
11
        int[] a = new int[n];
12
        SqStackClass<Integer> st = new SqStackClass<Integer>();
13
        for (i = 0; i < n; i++)
14
            a[i] = i + 1;                      // 将 1～n 放入数组 a 中: a = [1, 2, ..., n]
15
        i = 0; j = 0;
16
        while (i < n && j < n)                 // a 和 b 均没有遍历完
17
        {
18
            if (st.empty() || (st.peek() != b[j])) // 栈空或者栈顶元素不是 b[j]
19
            {
20
                st.push(a[i]);
21
                op += " 元素" + a[i] + "进栈\n";
22
                i++;
23
            }
24
            else                                 //否则出栈
25
            {
26
                e = st.pop();
27
                op += " 元素" + e + "出栈\n";
28
                j++;                            // j 只在成功出栈时才增加
29
            }
30
        }
31
        while (!st.empty() && st.peek() == b[j]) // (处理尾部残留) 使栈中与 b 序列相同的元素出栈
32
        {
33
            e = st.pop();
34
            j++;
35
        }
36
        if (j == n) return true;                 //是出栈序列时返回 true
37
        else return false;                       //不是出栈序列时返回 false
38
    }
39
}

假设 n = 3，b = [2, 1, 3]（合法序列）

• 初始：i=0, j=0, 栈空
• 栈空 → a[0]=1 进栈 → i=1
• 栈顶=1 ≠ b[0]=2 → a[1]=2 进栈 → i=2
• 栈顶=2 == b[0]=2 → 出栈2 → j=1
• 栈顶=1 == b[1]=1 → 出栈1 → j=2
• 栈顶=空 ≠ b[2]=3 → a[2]=3 进栈 → i=3
• 栈顶=3 == b[2]=3 → 出栈3 → j=3

✅ 最终 j == 3 == n → 合法！

上述过程可以进一步简化，同样用 i, j 分别遍历 a, b 数组（初始值均为 0），在 a 数组没有遍历完时：

(1) 将 a[i] 进栈，i++。 (2) 栈不空并且栈顶元素与 b[j] 相同时循环，即出栈元素 e, j++（改为连续判断）。

在上述过程结束后，如果栈空，返回 true，否则返回 false。

对应的简化算法如下：

1
public static boolean isSerial1(int[] b)     //简化的算法
2
{
3
    int i, j, n = b.length;
4
    Integer e;
5
    int[] a = new int[n];
6
    SqStackClass<Integer> st = new SqStackClass<Integer>();
7
    for (i = 0; i < n; i++)
8
        a[i] = i + 1;                        //将 1～n 放入数组 a 中
9
    i = 0; j = 0;
10
    while (i < n)                            //a 没有遍历完
11
    {
12
        st.push(a[i]);
13
        op += " 元素" + a[i] + "进栈\n";
14
        i++;
15
        while (!st.empty() && st.peek() == b[j]) //b[j] 与栈顶匹配的情况
16
        {
17
            e = st.pop();
18
            op += " 元素" + e + "出栈\n";
19
            j++;
20
        }
21
    }
22
    return st.empty();                       //栈空返回 true，否则返回 false
23
}

说明： 上述两个算法中可以不使用 a 数组，直接将 a[i] 的地方用 (i + 1) 代替，但使用 a 数组时稍微修改一下，可以判断任何进栈序列 a 是否可以得到合法的出栈序列 b。

算法步骤拆解（以 b = [2, 1, 3] 为例）

1. 初始状态: i=0, j=0, 栈空。
2. 第1轮外循环:
   • a[0]=1 进栈 → 栈: [1]
   • i=1
   • 内层循环：栈顶=1 ≠ b[0]=2 → 跳过。
3. 第2轮外循环:
   • a[1]=2 进栈 → 栈: [1, 2]
   • i=2
   • 内层循环：栈顶=2 == b[0]=2 → 出栈2 → j=1
     • 再次检查：栈顶=1 == b[1]=1 → 出栈1 → j=2
     • 再次检查：栈空 → 退出内层循环。
4. 第3轮外循环:
   • a[2]=3 进栈 → 栈: [3]
   • i=3
   • 内层循环：栈顶=3 == b[2]=3 → 出栈3 → j=3
5. 结束:
   • i=3 不再小于 n，退出外层循环。
   • 最终返回 st.empty() → true。

3.1.4 栈的链式存储结构及其基本运算算法的实现#

采用链式存储的栈称为链栈，这里采用单链表实现。链栈的优点是不需要考虑栈满溢出的情况。用带头结点的单链表 head 表示的链栈如图 3.11 所示，首结点是栈顶结点，尾结点是栈底结点，栈中元素自栈顶到栈底依次是 a₀, a₁, ..., aₙ₋₁。

从该链栈的存储结构看到，初始时只含有一个头结点 head 并置 head.next 为 null。链栈的四要素如下：

(1) 栈空的条件为 head.next == null。 (2) 由于只有在内存溢出才会出现栈满，通常不考虑这种情况。 (3) 元素 e 进栈操作是将包含该元素的结点 s 插入作为首结点。 (4) 出栈操作返回首结点值并且删除该结点。

和单链表一样，链栈中每个结点的类型 LinkNode<E> 定义如下：

1
class LinkNode<E>          //链栈结点泛型类
2
{
3
    E data;
4
    LinkNode<E> next;
5
    public LinkNode()      //构造方法
6
    {
7
        next = null;
8
    }
9
    public LinkNode(E d)   //重载构造方法
10
    {
11
        data = d;
12
        next = null;
13
    }
14
}

链栈类模板 LinkStackClass<E> 的设计如下：

1
public class LinkStackClass<E>     //链栈泛型类
2
{
3
    LinkNode<E> head;               //存放头结点
4
    public LinkStackClass()          //构造方法
5
    {
6
        head = new LinkNode<E>();    //创建头结点
7
        head.next = null;            //设置为空栈
8
    }
9
    //栈的基本运算算法
10
}

在链栈中实现栈的部分基本运算的算法如下。

1) 进栈：push(e)

新建包含数据元素 e 的结点 p，将 p 结点插入头结点之后。对应的算法如下：

1
public void push(E e)             //元素 e 进栈
2
{
3
    LinkNode<E> s = new LinkNode<E>(e); //新建结点 s
4
    s.next = head.next;           //将结点 s 插入表头
5
    head.next = s;
6
}

2) 出栈：pop()

在链栈空时抛出异常，否则将首结点的数据域赋给 e，然后将其删除。对应的算法如下：

1
public E pop()                    //出栈操作
2
{
3
    if (empty())
4
        throw new IllegalArgumentException("栈空");
5
    E e = (E)head.next.data;      //取首结点值
6
    head.next = head.next.next;   //删除原首结点
7
    return e;
8
}

3) 取栈顶元素：peek()

在链栈空时抛出异常，否则将首结点的数据域赋给 e，但不删除该结点。对应的算法如下：

1
public E peek()                   //取栈顶元素操作
2
{
3
    if (empty())
4
        throw new IllegalArgumentException("栈空");
5
    E e = (E)head.next.data;      //取首结点值
6
    return e;
7
}

3.1.5 链栈的应用算法设计举例#

3.1.6 Java 中的栈容器——Stack#

Java 语言中提供了栈容器 Stack<E>，它是从 Vector<E> 继承的，除了继承的许多方法外，作为栈的主要方法如下。

(1) boolean empty()：判断栈是否为空。 (2) int size()：返回栈中元素的个数。 (3) E push(E item)：把对象压入栈顶，即进栈操作。 (4) E pop()：移除栈顶对象，并作为此函数的值返回该对象，即出栈操作。 (5) E peek()：查看栈顶对象，但不从栈中移除它，即返回栈顶元素操作。 (6) int search(Object o)：返回元素 o 在栈中的位置，该位置从栈顶开始往下算，栈顶为 1。 (7) boolean contains(Object o)：如果栈中包含指定的元素 o，返回 true，否则返回 false。

3.1.7 栈的综合应用#

1. 用栈简单求解表达式求值问题

   用栈实现四则运算（即表达式求值）的核心思想是使用两个栈：

   • 操作数栈（Operand Stack）：存放数字；
   • 运算符栈（Operator Stack）：存放 + - * / ( ) 等运算符。

   整个过程基于中缀表达式转后缀（逆波兰）表达式的思想，或直接边扫描边计算。以下是简要步骤（以中缀表达式直接求值为例）：

   基本步骤（Dijkstra 双栈算法）

   1. 初始化两个栈：numStack（数字）、opStack（运算符）。
   2. 从左到右扫描表达式的每个字符：
      • 如果是数字 → 直接入 numStack。
      • 如果是 ’(’ → 入 opStack。
      • 如果是 ’)’ → 不断弹出 opStack 的运算符并计算，直到遇到 ’(’。
      • 如果是运算符（+ - * /）：
        • 比较其与 opStack 栈顶运算符的优先级；
        • 如果当前运算符优先级 ≤ 栈顶运算符，则先弹出栈顶运算符，从 numStack 弹出两个数进行计算，结果再入 numStack；
        • 重复此过程，直到栈顶运算符优先级更低或遇到 ’(‘，然后将当前运算符入栈。
   3. 扫描结束后，将 opStack 中剩余运算符依次弹出并计算。
   4. 最终结果在 numStack 的栈顶。

   关键点

   • 运算符优先级：/ > + -；括号具有最高局部优先级。
   • 处理多位数：需完整读取连续数字（如 “123”）。
   • 括号处理：( 入栈，) 触发计算直到 (。

   举例：计算 3 + 5 * 2

   步骤	当前字符	numStack	opStack	说明
   1	3	[3]	[]	数字入栈
   2	+	[3]	[+]	运算符入栈
   3	5	[3,5]	[+]	数字入栈
   4	*	[3,5]	[+, *]	* 优先级 > +，入栈
   5	2	[3,5,2]	[+, *]	数字入栈
   结束	—	[3,10]	[+]	先算 5*2=10
   	—	[13]	[]	再算 3+10=13

   ✅ 结果：13

3.2.1 队列的定义#

队列（简称为队）是一种操作受限的线性表，其限制为仅允许在表的一端进行插入，而在表的另一端进行删除。通常把进行插入的一端称为队尾（rear），把进行删除的一端称为队头或队首（front）。向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素；从队列中删除元素称为出队或离队，元素出队后，其直接后继元素就成为队首元素。

由于队列的插入和删除操作分别是在表的一端进行的，每个元素必然按照进入的次序出队，所以又把队列称为先进先出表。

抽象数据类型队列的定义如下：

1
ADT Queue
2
{
3
    数据对象：
4
        D = {aᵢ | 0 ≤ i ≤ n-1, n ≥ 0, aᵢ 为 E 类型}
5
    数据关系：
6
        R = {r}
7
        r = {<aᵢ, aᵢ₊₁> | aᵢ, aᵢ₊₁ ∈ D, i = 0, ..., n-2}
8
    基本运算：
9
        boolean empty(): 判断队列是否为空，若队列为空，返回真，否则返回假。
10
        void push(E e): 进队，将元素 e 进队作为队尾元素。
11
        E pop(): 出队，从队头出队一个元素。
12
        E peek(): 取队头，返回队头元素值而不出队。
13
}

【例】 若元素进队的顺序为 1234，能否得到 3142 的出队序列？

解： 进队顺序为 1234，则出队顺序只能是 1234（先进先出），所以不能得到 3142 的出队序列。

3.2.2 队列的顺序存储结构及其基本运算算法的实现#

1. 非循环队列

初始时置 front 和 rear 均为 -1 (front == rear)。非循环队列的四要素如下：

(1) 队空的条件为 front == rear，图 3.20(a) 和 (d) 满足该条件。 (2) 队满（队上溢出）的条件为 rear == MaxSize - 1（因为每个元素进队都让 rear 增 1，当 rear 到达最大下标时不能再增加），图 3.20(d) 满足该条件。 (3) 元素 e 进队的操作是先将队尾指针 rear 增 1，然后将元素 e 放在该位置（进队的元素总是在尾部插入的）。 (4) 出队操作是先将队头指针 front 增 1，然后取出该位置的元素（出队的元素总是从头部出来的）。

说明： 为什么让 front 指向队列中当前队头元素的前一个位置呢？因为在 front 增 1 后，该位置的元素已经出队（被删除了）。

非循环队列的泛型类 SqQueueClass<E> 定义如下：

1
class SqQueueClass<E>           //非循环队列的泛型类
2
{
3
    final int MaxSize = 100;    //假设容量为 100
4
    private E[] data;           //存放队列中的元素
5
    private int front, rear;     //队头、队尾指针
6

7
    public SqQueueClass()        //构造方法
8
    {
9
        data = (E[]) new Object[MaxSize];
10
        front = -1;
11
        rear = -1;
12
    }
13
    //队列的基本运算算法
14
}

在上述非循环队列中，元素进队时队尾指针 rear 增1，元素出队时队头指针 front 增1，当进队 MaxSize 个元素后，满足设置的队满条件，即 rear == MaxSize-1 成立，此时即使出队若干元素，队满条件仍然成立(实际上队列中有空位置)，这种队列中有空位置但仍然满足队满条件的上溢出称为假溢出。也就是说，非循环队列存在假溢出现象。

1. 循环队列

   为了克服非循环队列的假溢出，充分使用数组中的存储空间，可以把 data 数组的前端和后端连接起来，形成一个循环数组，即把存储队列元素的表从逻辑上看成一个环，称为循环队列（也称为环形队列）。

   循环队列首尾相连，当队尾指针 rear = MaxSize - 1 时再前进一个位置就应该到达 0 位置，这可以利用数学上的求余运算 (%) 实现。

   (1) 队首指针循环进 1：front = (front + 1) % MaxSize (2) 队尾指针循环进 1：rear = (rear + 1) % MaxSize

   循环队列的队头指针和队尾指针初始化时都置 0，即 front = rear = 0。在进队元素和出队元素时，队头和队尾指针都循环前进一步。

   那么循环队列的队满和队空的判断条件是什么呢？若设置队空条件是 rear == front，如果进队元素的速度快于出队元素的速度，队尾指针很快就赶上了队头指针，此时可以看出循环队列在队满时也满足 rear == front，所以这种设置无法区分队空和队满。

   实际上循环队列的结构与非循环队列相同，也需要通过 front 和 rear 标识队列状态，一般是采用它们的相对值（即 |front - rear|）实现的。若 data 数组的容量为 m，则队列的状态有 m+1 种，分别是队空、队中有 1 个元素、队中有 2 个元素、……、队中有 m 个元素（队满）。front 和 rear 的取值范围均为 0 ~ m-1，这样 |front - rear| 只有 m 个值，显然 m+1 种状态不能直接用 |front - rear| 区分，因为必定有两种状态不能区分。为此让队列中最多只有 m-1 个元素，这样队列恰好只有 m 种状态，就可以通过 front 和 rear 的相对值区分所有状态了。

   在规定队列中最多只有 m-1 个元素时，设置队空条件仍然是 rear == front。当队列有 m-1 个元素时一定满足 (rear + 1) % MaxSize == front。

   这样循环队列在初始时置 front = rear = 0，其四要素如下：

   (1) 队空条件为 rear == front。 (2) 队满条件为 (rear + 1) % MaxSize == front（相当于试探进队一次，若 rear 达到 front，则认为队满了）。 (3) 元素 e 进队时，rear = (rear + 1) % MaxSize，将元素 e 放置在该位置。 (4) 元素出队时，front = (front + 1) % MaxSize，取出该位置的元素。

   图 3.23 说明了循环队列的几种状态，这里假设 MaxSize 等于 5。图 3.23(a) 为空队，此时 front = rear = 0；图 3.23(b) 中有 3 个元素，当进队元素 d 后队中有 4 个元素，此时满足队满的条件。

   循环队列的泛型类 CSqQueueClass<E> 定义如下：

   1
   class CSqQueueClass<E>           //循环队列的泛型类
   2
   {
   3
       final int MaxSize = 100;     //假设容量为 100
   4
       private E[] data;            //存放队列中的元素
   5
       private int front, rear;      //队头、队尾指针
   6
   
   7
       public CSqQueueClass()         //构造方法
   8
       {
   9
           data = (E[]) new Object[MaxSize];
   10
           front = 0;
   11
           rear = 0;
   12
       }
   13
       //队列的基本运算算法
   14
   }
   

   在这样的循环队列中，实现队列的基本运算算法如下。

   1) 进队：push(e)

   在队列不满时，先将队尾指针 rear 循环增 1，然后将元素 e 放到该位置处，否则抛出异常。对应的算法如下：

   1
   public void push(E e)           //元素 e 进队
   2
   {
   3
       if ((rear + 1) % MaxSize == front) //队满
   4
           throw new IllegalArgumentException("队满");
   5
       rear = (rear + 1) % MaxSize;
   6
       data[rear] = e;
   7
   }
   

   2) 出队：pop()

   在队列不为空的条件下，将队头指针 front 循环增 1，并返回该位置的元素值，否则抛出异常。对应的算法如下：

   1
   public E pop()                  //出队元素
   2
   {
   3
       if (empty())                //队空
   4
           throw new IllegalArgumentException("队空");
   5
       front = (front + 1) % MaxSize;
   6
       return (E)data[front];
   7
   }
   

3.2.3 循环队列的应用算法设计示例#

3.2.4 队列的链式存储结构及其基本运算算法的实现#

队列的链式存储结构也是通过由结点构成的单链表实现的，此时只允许在单链表的表首进行删除操作和在单链表的表尾进行插入操作，这里的单链表是不带头结点的，需要使用两个指针（即队首指针 front 和队尾指针 rear）来标识，front 指向队首结点，rear 指向队尾结点。用于存储队列的单链表简称为链队。

链队中存放元素的结点类型 LinkNode<E> 定义如下：

1
class LinkNode<E>          //链队结点泛型类
2
{
3
    E data;
4
    LinkNode<E> next;
5
    public LinkNode()      //构造方法
6
    {
7
        next = null;
8
    }
9
    public LinkNode(E d)   //重载构造方法
10
    {
11
        data = d;
12
        next = null;
13
    }
14
}

设计链队泛型类 LinkQueueClass<E> 如下：

1
public class LinkQueueClass<E>     //链队泛型类
2
{
3
    LinkNode<E> front;              //首结点指针
4
    LinkNode<E> rear;               //尾结点指针
5

6
    public LinkQueueClass()          //构造方法
7
    {
8
        front = null;
9
        rear = null;
10
    }
11
    //队列的基本运算算法
12
}

图 3.25 说明了一个链队的动态变化过程。图 3.25(a) 是链队的初始状态，图 3.25(b) 是在链队中进队 3 个元素后的状态，图 3.25(c) 是从链队中出队两个元素后的状态。

从图 3.25 可以看到，初始时置 front = rear = null。链队的四要素如下：

(1) 队空的条件为 front = rear = null，用户不妨仅以 front == null 作为队空条件。 (2) 由于只有在内存溢出时才出现队满，通常不考虑这样的情况。 (3) 元素 e 进队的操作是在单链表尾部插入存放 e 的 s 结点，并让队尾指针指向它。 (4) 出队操作是取出队首结点的 data 值，并将其从链队中删除。

对应队列的基本运算算法如下：

1) 进队：push(e)

创建存放 e 的结点 s。若原队列为空，则将 front 和 rear 指向 s 结点，否则将 s 结点链到单链表的末尾，并让 rear 指向它。对应的算法如下：

1
public void push(E e)           //元素 e 进队
2
{
3
    LinkNode<E> s = new LinkNode<E>(e); //新建结点 s
4
    if(empty())                 //原链队为空
5
        front = rear = s;
6
    else                        //原链队不空
7
    {
8
        rear.next = s;          //将 s 结点链接到 rear 结点的后面
9
        rear = s;
10
    }
11
}

2) 出队：pop()

若原队为空，抛出异常；若队中只有一个结点（此时 front 和 rear 都指向该结点），取首结点的 data 值赋给 e，并删除之，即置 front = rear = null；否则说明有多个结点，取首结点的 data 值赋给 e，并删除之。最后返回 e。对应的算法如下：

1
public E pop()                  //出队操作
2
{
3
    E e;
4
    if(empty())                 //原链队不空
5
        throw new IllegalArgumentException("队空");
6
    if(front == rear)           //原链队只有一个结点
7
    {
8
        e = (E)front.data;      //取首结点值
9
        front = rear = null;    //置为空
10
    }
11
    else                        //原链队有多个结点
12
    {
13
        e = (E)front.data;      //取首结点值
14
        front = front.next;     //front 指向下一个结点
15
    }
16
    return e;
17
}

3.2.5 链队的应用算法设计示例#

3.2.6 Java 中的队列接口——Queue#

在 Java 语言中提供了队列接口 Queue<E>，提供了队列的修改运算，但不同于 Stack<E>，由于它是接口，所以在创建时需要指定元素类型，例如 LinkedList<E>。Queue<E> 接口的主要方法如下。

(1) boolean isEmpty()：返回队列是否为空。 (2) int size()：队列中元素的个数。 (3) boolean add(E e)：将元素 e 进队（如果立即可行且不会违反容量限制），在成功时返回 true，如果当前没有可用的空间，则抛出异常。 (4) boolean offer(E e)：将元素 e 进队（如果立即可行且不会违反容量限制），当使用有容量限制的队列时，此方法通常要优于 add(e)，后者可能无法插入元素，而只是抛出一个异常。 (5) E peek()：取队头元素，如果队列为空，则返回 null。 (6) E element()：取队头元素，它对 peek() 方法进行简单封装，如果队头元素存在，则取出但并不删除，如果不存在则抛出异常。 (7) E poll()：出队，如果队列为空，则返回 null。 (8) E remove()：出队，直接删除队头的元素。

在 Queue<E> 的使用中，主要操作是进队方法 offer()、出队方法 poll()、取队头元素方法 peek()，它们的时间复杂度均为 O(1)。

3.2.7 队列的综合应用#

*3.2.8 双端队列#

双端队列是在队列的基础上扩展而来的，其示意图如图 3.30 所示。双端队列与队列一样，元素的逻辑关系也是线性关系，但队列只能在一端进队，在另外一端出队，而双端队列可以在两端进行进队和出队操作，因此双端队列的使用更加灵活。

在 Java 中提供了双端队列接口 Deque<E>，它继承自 Queue<E>。Deque<E> 接口的主要方法如下。

(1) boolean offer(E e)：将元素 e 插入双端队列的尾部（与队列进队操作相同）。如果成功，返回 true，如果当前没有可用的空间，则返回 false。 (2) boolean offerFirst(E e)：将元素 e 插入双端队列的开头。如果成功，返回 true，如果当前没有可用的空间，则返回 false。 (3) boolean offerLast(E e)：将元素 e 插入双端队列的尾部（与队列进队操作相同）。如果成功，返回 true，如果当前没有可用的空间，则返回 false。与 offer(E e) 相同。 (4) E poll()：从双端队列中出队队头元素（与队列出队操作相同）。如果双端队列为空，则返回 null。 (5) E pollFirst()：从双端队列中出队队头元素（与队列出队操作相同）。如果双端队列为空，则返回 null。与 poll() 相同。 (6) E pollLast()：从双端队列中出队队尾元素。如果双端队列为空，则返回 null。 (7) E peek()：取双端队列的队头元素（与队列取队头元素操作相同）。如果双端队列为空，则返回 null。 (8) E peekFirst()：取双端队列的队头元素（与队列取队头元素操作相同）。如果双端队列为空，则返回 null。用 peek() 相同。 (9) E peekLast()：取双端队列的队尾元素。如果双端队列为空，则返回 null。

从中可以看出，如果规定 Deque<E> 只在一端进队，另外一端出队，即只使用 offer(E e)/offerLast(E e)、poll()/pollFirst()、peek()/peekFirst()（后端进，前端出），或者 offerLast(E e)、pollFirst()、peekFirst()（前端进，后端出），此时 Deque<E> 相当于队列。

如果规定 Deque<E> 只在同端进队和出队，即只使用 offerFirst(E e)、pollFirst()、peekFirst()（前端进，前端出），或者 offerLast(E e)、pollLast()、peekLast()（后端进，后端出），此时 Deque<E> 相当于栈。

4.1.1 什么是串#

串是由零个或多个字符组成的有限序列，记作 str = a₁a₂…aₙ (n ≥ 0)，其中 str 是串名，用双引号括起来的字符序列为串值，引号是界限符，aᵢ (1 ≤ i ≤ n) 是一个任意字符（字母、数字或其他字符），它称为串的元素，是构成串的基本单位，串中所包含的字符个数 n 称为串的长度，当 n = 0 时称为空串。

将串值括起来的双引号本身不属于串，它的作用是避免串与常数或标识符混淆。例如 A = "123" 是数字字符串，长度为 3，它不同于常整数 123。通常将仅由一个或多个空格组成的串称为空白串。注意空串和空白串不同，例如 " "（含一个空格）和 ""（不含任何字符）分别表示长度为 1 的空白串和长度为零的空串。

一个串中任意连续的字符组成的子序列称为该串的子串，例如 "a"、"ab"、"abc" 和 "abcd" 等都是 "abcde" 的子串。包含子串的串相应地称为主串。通常称字符在序列中的序号为该字符在串中的位置，例如字符元素 aᵢ (1 ≤ i ≤ n) 的序号为 i。子串在主串中的位置则以子串的第一个字符首次出现在主串中的位置来表示。例如，设有两个字符串 s 和 t：

1
s = "This is a string."
2
t = "is"

则它们的长度分别为 17 和 2，t 是 s 的子串，s 为主串。t 在 s 中出现了两次，其中首次出现所对应的主串位置是 3，因此称 t 在 s 中的序号（或位置）为 3。

若两个串的长度相等且对应字符都相等，则称两个串相等。当两个串不相等时，可按“词典顺序”区分大小。

4.1.2 串的抽象数据类型#

抽象数据类型串的定义如下：

1
ADT String
2
{
3
    数据对象：
4
        D = {aᵢ | 0 ≤ i ≤ n-1, n ≥ 0, aᵢ 为 char 类型}
5
    数据关系：
6
        R = {r}
7
        r = {<aᵢ, aᵢ₊₁> | aᵢ, aᵢ₊₁ ∈ D, i = 0, ..., n-2}
8
    基本运算：
9
        void StrAssign(cstr): 由字符串常量 cstr 创建一个串，即生成其值等于 cstr 的串。
10
        char geti(int i): 返回序号为 i 的字符。
11
        void seti(int i, char x): 设置序号为 i 的字符为 x。
12
        String StrCopy(): 串复制，返回由当前串复制产生的一个串。
13
        int size(): 求串长，返回当前串中字符的个数。
14
        String Concat(t): 串连接，返回一个当前串和串 t 连接后的结果。
15
        String SubStr(i, j): 求子串，返回当前串中从第 i 个字符开始的 j 个连续字符组成的子串。
16
        String InsStr(i, t): 串插入，返回串 t 插入当前串的第 i 个位置后的子串。
17
        String DelStr(i, j): 串删除，返回当前串中删去从第 i 个字符开始的 j 个字符后的结果。
18
        String RepStr(i, j, t): 串替换，返回用串 t 替换当前串中从第 i 个字符开始的 j 个字符后的结果。
19
        String toString(): 将串转换为字符串。
20
}

4.2.1 串的顺序存储结构——字符串#

设计顺序串类 SqStringClass 如下：

1
public class SqStringClass     //顺序串类
2
{
3
    final int MaxSize = 100;   //假设容量为 100
4
    char[] data;               //存放串中的字符
5
    int size;                  //串中字符的个数
6

7
    public SqStringClass()      //构造方法
8
    {
9
        data = new char[MaxSize];
10
        size = 0;
11
    }
12
    //串的基本运算算法
13
}

4.2.2 串的链式存储结构——链串#

链串的组织形式与一般的链表类似，主要区别在于链串中的一个结点可以存储多个字符。通常将链串中的每个结点所存储的字符个数称为结点大小。图 4.2 和图 4.3 分别表示了同一个串“ABCDEFGHIJKLMN”的结点大小为 4（存储密度大）和 1（存储密度小）的链式存储结构。

当结点大小大于 1（例如结点大小或等于 4）时，链串的最后一个结点的各个数据域不一定总能全被字符占满，此时应在这些未占用的数据域里补上不属于字符集的特殊符号（例如 '#' 字符），以示区别（参见图 4.2 中的最后一个结点）。

在设计链串时，结点大小越大，则存储密度越大。当链串的结点大小大于 1 时，一些操作（例如插入、删除、替换等）有所不便，可能引起大量字符移动，因此它适合在串基本保持静态使用方式时采用。为简便起见，这里规定链串的结点大小均为 1。

链串的结点类型 LinkNode 的定义如下：

1
class LinkNode             //链串结点类型
2
{
3
    char data;             //存放一个字符
4
    LinkNode next;          //指向下一个结点的指针
5

6
    public LinkNode()       //构造方法
7
    {
8
        next = null;
9
    }
10

11
    public LinkNode(char ch) //重载构造方法
12
    {
13
        data = ch;
14
        next = null;
15
    }
16
}

一个链串用一个头结点 head 来唯一标识，设计链串类 LinkStringClass 如下：

1
public class LinkStringClass     //链串类
2
{
3
    LinkNode head;               //链串中字符的个数
4
    int size;                    //构造方法
5

6
    public LinkStringClass()      //建立头结点
7
    {
8
        head = new LinkNode();
9
        size = 0;
10
    }
11
    //串的基本运算算法
12
}

4.3.1 String#

在 Java 中提供了 String 字符串类（位于 java.lang 命名空间中），所有字符串字面值（例如 "abc"）都作为此类的实例实现。

String 类包括的方法可用于检查序列的单个字符、比较字符串、搜索字符串、提取子串、创建字符串副本并将所有字符全部转换为大写或小写等。另外，Java 语言还提供对字符串串联符号（"+"）以及将其他对象转换为字符串的特殊支持。

String 类的主要方法如下。

(1) char charAt(int index)：返回指定索引处的 char 值。 (2) int compareTo(String anotherString)：按字典顺序比较两个字符串。 (3) int compareToIgnoreCase(String str)：按字典顺序比较两个字符串，不考虑大小写。 (4) String concat(String str)：将指定字符串连接到此字符串的结尾。 (5) boolean endsWith(String suffix)：测试此字符串是否以指定的后缀结束。 (6) boolean equals(Object anObject)：将此字符串与指定的对象比较。 (7) boolean equalsIgnoreCase(String anotherString)：将此 String 与另一个 String 比较，不考虑大小写。 (8) static String format(String format, Object... args)：使用指定的格式字符串和参数返回一个格式化字符串。 (9) int indexOf(int ch)：返回指定字符在此字符串中第一次出现处的索引。 (10) int indexOf(int ch, int fromIndex)：返回在此字符串中第一次出现指定字符处的索引，从指定的索引开始搜索。 (11) int indexOf(String str)：返回指定子字符串在此字符串中第一次出现处的索引。 (12) int indexOf(String str, int fromIndex)：返回指定子字符串在此字符串中第一次出现处的索引，从指定的索引开始。 (13) boolean isEmpty()：当且仅当 length() 为 0 时返回 true。 (14) int lastIndexOf(int ch)：返回指定字符在此字符串中最后一次出现处的索引。 (15) int lastIndexOf(int ch, int fromIndex)：返回指定字符在此字符串中最后一次出现处的索引，从指定的索引处开始进行反向搜索。 (16) int lastIndexOf(String str)：返回指定子字符串在此字符串中最右边出现处的索引。 (17) int lastIndexOf(String str, int fromIndex)：返回指定子字符串在此字符串中最后一次出现处的索引，从指定的索引开始反向搜索。 (18) int length()：返回此字符串的长度。 (19) String replace(char oldChar, char newChar)：返回一个新的字符串，它是通过用 newChar 替换此字符串中出现的所有 oldChar 得到的。 (20) String replaceAll(String regex, String replacement)：使用给定的 replacement 替换此字符串所有匹配给定的正则表达式的子字符串。 (21) String replaceFirst(String regex, String replacement)：使用给定的 replacement 替换此字符串匹配给定的正则表达式的第一个子字符串。 (22) String[] split(String regex)：根据给定正则表达式的匹配拆分此字符串。 (23) String[] split(String regex, int limit)：根据匹配给定的正则表达式来拆分此字符串。 (24) boolean startsWith(String prefix)：测试此字符串是否以指定的前缀开始。 (25) boolean startsWith(String prefix, int toffset)：测试此字符串从指定索引开始的子字符串是否以指定前缀开始。 (26) String substring(int beginIndex)：返回一个新的字符串，它是此字符串的一个子字符串。 (27) String substring(int beginIndex, int endIndex)：返回一个新字符串，它是此字符串的一个子字符串。 (28) char[] toCharArray()：将此字符串转换为一个新的字符数组。 (29) String toLowerCase()：使用默认语言环境的规则将此 String 中的所有字符都转换为小写。 (30) String toUpperCase()：使用默认语言环境的规则将此 String 中的所有字符都转换为大写。

读者需要注意字符串比较中 "==" 操作符和 equals() 方法的区别。"==" 可以用于基本数据类型的比较，当用于引用对象比较时是判断引用是否指向堆内存的同一块地址；而 equals() 方法的作用是用于判断两个变量是否为同一个对象的引用，即堆中的内容是否相同，返回值为布尔类型。

4.3.2 StringBuffer#

String 字符串是常量，其值在创建之后不能更改，为此 Java 中提供了 StringBuffer 字符串缓冲区支持可变的字符串。StringBuffer 每次都对对象本身进行操作，而不是生成新的对象，所以在字符串内容不断改变的情况下建议使用 StringBuffer。

StringBuffer 类的主要方法如下。

(1) StringBuffer append(String str)：将指定的字符串添加到此字符序列的末尾。 (2) char charAt(int index)：返回此序列中指定索引处的 char 值。 (3) StringBuffer delete(int start, int end)：移除此序列的子字符串中的字符。 (4) StringBuffer deleteCharAt(int index)：移除此序列指定位置的 char。 (5) StringBuffer insert(int offset, String str)：将字符串插入此字符序列中。 (6) StringBuffer replace(int start, int end, String str)：使用给定 String 中的字符替换此序列的子字符串中的字符。 (7) StringBuffer reverse()：将此字符序列用其反转形式取代。 (8) String substring(int start)：返回一个新的 String，它包含此字符序列当前所包含的字符子序列。 (9) String substring(int start, int end)：返回一个新的 String，它包含此序列当前所包含的字符子序列。

例如有以下程序及其执行结果：

1
import java.lang.*;
2
public class tmp
3
{
4
    public static void main(String[] args)
5
    {
6
        String s1 = "abc";
7
        String s2 = s1;
8
        s1 += "123";
9
        System.out.println(s1 == s2);           //false
10
        System.out.println("s1: " + s1);         //s1: abc123
11
        System.out.println("s2: " + s2);         //s2: abc
12
        StringBuffer s3 = new StringBuffer("abc");
13

14
        StringBuffer s4 = s3;
15
        s3.append("123");
16
        System.out.println(s3 == s4);            //返回 true
17
        System.out.println("s3: " + s3);          //s3: abc123
18
        System.out.println("s4: " + s4);          //s4: abc123
19
    }
20
}