Data Structures and Algorithms

Low poly (8 part) by Vladimir Bozrikov

引言

“数据结构和算法”是学习特定算法前的基础，比如时间空间复杂度，如何实现 List、HashMap、Tree、Heap、Graph，还有各类数据结构中的操作，都是必备的基本功。本文涵盖了各类题型中的常见数据结构和算法，让大家事半功倍。

简介

什么是数据结构？什么是算法？

什么是”数据结构和算法“？这可能是第一次接触此内容的新朋友最常有的问题。我先给大家一个比较官方的解释：

数据结构是计算机存储、组织数据的方式。
算法是一系列规定的计算步骤，为了实现特定的计算目的。

你可能更困惑了，那我换种简单的说法吧：

程序 = 数据结构 + 算法

这什么意思？我们都知道，电脑最主要功能是储存数据，计算数据，输出数据，而程序无非就是电脑中一部分数据的集合而已，所以程序也是要控制数据的。那么数据结构就是程序用来储存数据的基本单位，而算法就是为了实现特定目的，一系列操作数据的方式。简单来讲，一个程序把数据存储在特定的数据结构中，并使用特定的算法进行数据的计算。

举例来说，你要在数据库中查找一个特定的数字75，假设这个数据库用数组存储数据，并存好了100个从小打大排好序的数字，那我们可以使用两种方式来找75。第一种方式就是一个一个按顺序找，那就需要找75次才能找到我们的目标。第二种方式就是我们只找一堆数中间的那个数，如果那个数比我们要找的数小，那么我们排除此数之前的所有数，只管那个数之后的数字。如果那个数比我们要找的数大，那么我们知道我们要的数肯定排在它的前面，那就只找它之前的数。所以我们第一次会找到50，50比75小，那我们就只管50~100之间的数，然后再找中间的数75，这下就找到了，可见第二种方法比第一种方法快多了。

在这个例子中，数据库用来存储数据的数组就是数据结构，而搜索的两种方式则是特定的两种搜索算法：暴力搜索和二分搜索。如果这个数据库中数据没有排好序，那么二分查找就不适用了，我们只能使用暴力搜索。可见特定的算法需要通过特定的数据结构来实现，二分搜索基于数组这种数据结构，且其中的数字必须排好序。算法的设计需要结合数据结构和特征才行。

数据结构和算法之间的关系

但数据结构和算法不一定像数组和二分查找这个例子这样是完全分开的单独内容。数组是最简单的数据结构，而很多其他复杂的数据结构往往又集成了很多的算法在其中。

比如一个优先队列数据结构，每次你向其中加入一个新数据的时候，它都会自动帮你排序好，将优先级最高的数据放在第一个。如果我们用这个数据结构来存储数据，并设定数字大的优先级更高，那么我们每次我们想要查找最大的数字，都不需要查找，直接取优先队列第一个数字即可。可见数据结构和算法的关系密不可分，每个数据结构中往往集成了很多的算法，比如这个优先队列中就集合了某种排序算法，我们才能如此快速地拿到最大值。

这些就是数据结构和算法的基本概念：数据结构是程序储存信息的基本单位，数组就是常见的数据结构。而算法则是实现特定任务的计算步骤，比如排序算法和搜索算法的目的顾名思义就是排序和搜索。数据结构和算法之间的关系密不可分，特定算法有时候需要基于特定的数据结构，比如二分查找就要基于排好序的数组。另一方面，数据结构也往往集成了特定的算法，比如优先队列就集成了排序算法在其中。

“数据结构和算法”有那么重要吗？

很多小伙伴就问了，如今各种编程语言都有丰富的第三方代码库，不需要自己实现算法，那我们还需要学习”数据结构和算法“吗？这个问题就等价于，搬砖需不需要学习物理。如果只干搬砖砌墙的活，熟练掌握工具那就够了。但是要想设计建筑的话，还是要打好基础的。“数据结构和算法”也是计算机科学的必修课，不学也不行哈哈。

毫不夸张地说，“数据结构和算法”就是编程的内功，如果能深入掌握这方面的知识，我们就可以设计出计算效率更高的程序，比如Google这一个看起来功能单一的搜索引擎，不仅仅可以搜索相关性极高的内容，其搜索速度也是惊人的，背后的秘密就是各种搜索算法的集合。所以好好学习”数据结构和算法“吧，可能你就能创造出下一个Google哈哈~

课程大纲

为了帮助大家快速入门并掌握最重要的知识点，此教程将会重点讲解数据结构，并结合数据结构一一剖析核心的算法，帮助大家建立起系统性的知识框架。我也会将算法和现实生活问题结合起来，帮助大家更好理解算法，更希望朋友们能将这些内功融会贯通到现实编程中。以下是内容大纲：

时间空间复杂度（Time Complexity, Space Complexity）
排序算法（Sorting）
链表（List）
栈和队列（Stack, Queue)
优先队列和哈希表（Priority Queue, HashTable）
树和图（Tree, Graph）

复杂度分析

算法本质上是一连串的计算步骤。对于同一个问题，我们可以使用不同的算法来获得相同的结果，可是在计算过程中电脑消耗的时间和资源却有很大的区别。那我们如何来比较不同算法之间的优劣性呢？

目前分析算法主要从「时间」和「空间」两个维度来进行分析。时间维度顾名思义就是算法需要消耗的时间，「时间复杂度」是常用的分析单位。空间维度代表算法需要占用的内存空间，我们通常用「空间复杂度」来分析。

所以，分析算法的效率主要从「时间复杂度」和「空间复杂度」来分析。很多时候我们两者不可兼得，有时候要用时间换空间，或者空间换时间。下面我们一起来分别了解「时间复杂度」和「空间复杂度」的计算方式。

时间复杂度

想要从「时间维度」来了解一个算法，最简单的方法就是将算法运行一遍，然后计算花费的时间就可以了。

此方法可行，可是有很多弊端。只计算运行时间特别容易受到运行环境的影响，高性能和低性能的机器上出来的结果相差甚远。而且与测试时使用的数据规模也有很大的关系。

所以我们需要一种复杂度计算方式，不受计算机性能和程序数据的影响，「大O符号表示法」(BigO)就是这种计算方式，既 $T(n) = O(f(n))$，它表示一个算法的渐进时间复杂度。其中 f(n) 表示代码执行次数之和，O表示正比例关系。我们来看一个例子：

for (int i = 1; i <= n; i++) {
    x++;
}

每个算法需要多少的运行时间呢？我们知道这个for loop有n个循环，假设其中 x++ 计算的消耗是一个单位，那么第一次循环是1单位，第二次循环是2单位，所以整个循环语句就要消耗n个单位。可以发现，消耗的单位时间随着循环的次数而变化，循环次数为1，时间为1单位；循环次数为10，时间为10单位；循环次数为n，时间为n单位。所以这个算法的「时间复杂度」可以表示为：$T (n) = O(n)$。

有人可能不同意了，因为严格计算下，int i = 1也要消耗1单位时间，i <= n和i++也都需要1单位时间，所以严格来说总时间是 T(n) = 1 + 3n。但是我们依然会简化为n，因为「大O表示法」用与表示计算的增长变化趋势。

在这个例子中，如果n无限大的时候，$T(n) = 1 + 3n$ 中的常数1就没有意义了，倍数3也影响不大。所以简化为 $T(n) = O(n)$ 就可以了。

我们再来看一个例子：

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        x++;
    }
}

在外层循环中，i 总共需要n层循环，在每一次内层循环中，j 也会循环n次。如果用「大O表示法」来计算，那么两个循环语句的复杂度就是 $O(n^2)$，如果我们将这两个算法合并到一起：

for (int i = 1; i <= n; i++) {
    x++;
}
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        x++;
    }
}

整个算法复杂度就变为 $O(n + n^2)$，在n无限大的情况下，可以简化为 $O(n^2)$。

常用的时间复杂度量级

以下便是常见的时间复杂度量级：

常数阶O(1)
对数阶O(logN)
线性阶O(n)
线性对数阶O(nlogN)
平方阶O(n²)
立方阶O(n³)
K次方阶O(n^k)
指数阶(2^n)
阶乘O(n!)

上面的时间复杂从上到下复杂度越来越大，也意味着执行效率越来越低。以下我们来讲解一些常用的量级：

常数阶O(1)

只要没有循环或递归等复杂逻辑，无论代码执行多少行，代码复杂度都为 $O(1)$，如下：

int x = 0;
int y = 1;
int temp = x;
x = y;
y = temp;

上述代码在执行的时候，所消耗的时间不会随着特定变量的增长而增长，即使有几万行这样的代码，我们都可以用 $O(1)$ 来表示它的时间复杂度。

线性阶O(n)

我们在上述的例子中讲解过 $O(n)$ 的算法：

for (int i = 1; i <= n; i++) {
    x++;
}

在这段代码中，for循环会执行n遍，因此计算消耗的时间是随着n的变化而变化，因此这类代码都可以用 $O(n)$ 来表示其时间复杂度。

对数阶O(logN)

来看以下的例子：

int i = 1;
while(i < n) {
    i = i * 2;
}

在上面的循环中，每次i都会被乘以2，也意味着每次 i 都离 n 更进一步。那需要多少次循环 i 才能等于或大于 n 呢，也就是求解2的x次方等于n，答案x=log2^n。也就是说循环 log2^n次之后，i会大于等于n，这段代码就结束了。所以此代码的复杂度为：$O(\log N)$。

线性对数阶O(nlogN)

线性对数阶 $O(n\log N)$ 很好理解，也就是将复杂度为 $O(\log N)$ 的代码循环n遍：

for(int i = 0; i <= n: i++) {
    int x = 1;
    while(x < n) {
        x = x * 2;
    }
}

因为每次循环的复杂度为 $O(\log N)$，所以 $n * logN = O(n\log N)$

平方阶O(n²)

在之前的例子我们也讲过，$O(n²)$ 就是将循环次数为n的代码再循环n遍：

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        x++;
    }
}

$O(n²)$ 的本质就是 $n * n$，如果我们将内层的循环次数改为m：

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        x++;
    }
}

复杂度就变为 $n * m = O(n * m)$。

关于一些更高的阶级比如 $O(n³)$ 或者 $O(n^k)$，我们可以参考 $O(n²)$ 来理解即可，$O(n³)$ 相当于三层循环，以此类推。

除了「大O表示法」还有其他「平均时间复杂度」、「均摊时间复杂度」、「最坏时间复杂度」、「最好时间复杂度」等等分析指数，但是最常用的依然是「大O表示法」。

空间复杂度

既然「时间复杂度」不是计算程序具体消耗的时间，「空间复杂度」也不是用来计算程序具体占用的空间。随着问题量级的变大，程序需要分配的内存空间也可能会变得更多，而「空间复杂度」反映的则是内存空间增长的趋势。

常用的空间复杂度

比较常用的空间复杂度有：$O(1)$、$O(n)$、$O(n²)$。在下面的例子中，我们用 $S(n)$ 来定义「空间复杂度」。

O(1)空间复杂度

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，此算法空间复杂度为一个常量，可表示为 $O(1)$：

int x = 0;
int y = 0;
x++;
y++;

其中x, y所分配的空间不随着处理数据量变化，因此「空间复杂度」为 $O(1)$

O(n)空间复杂度

以下的代码给长度为 n 的数组赋值：

int[] newArray = new int[n];
for (int i = 0; i < n; i++) {
    newArray[i] = i;
}

在这段代码中，我们创建了一个长度为 n 的数组，然后在循环中为其中的元素赋值。因此，这段代码的「空间复杂度」取决于 newArray 的长度，也就是 n，所以 $S(n) = O(n)$。

以上便是「时间复杂度」和「空间复杂度」的简单介绍啦，简单来说，这两个复杂度反映的是，随着问题量级的增大，时间和空间增长的趋势。学会了复杂度的分析，我们就可以对比算法之间的优劣势啦~

排序算法

搜索是计算机中非常重要的步骤，但是从无序的数据中寻找特定的数字往往很难，我们之前提到的二分查找只能运用在排好序的数组中。所以排序算法是一个很重要的工作，如果我们能够将数值排好序，那么当我们寻找特定数值的时候，能省下不少功夫。

排序算法有很多，每种排序算法各有优缺点：

在这章节中，我们就来学习其中最经典的三种排序方法：插入排序Insertion Sort，快排Quick Sort，归并排序Merge Sort。

插入排序 Insertion Sort

概念

插入排序是一种简单直观的排序算法。在插入排序中，我们从前到后依次处理未排好序的元素，对于每个元素，我们将它与之前排好序的元素进行比较，找到对应的位置后并插入。本质上，对于每一个要被处理的元素，我们只关心它与之前元素的关系，当前元素之后的元素我们下一轮才去处理。

在实现上，每个元素和之前元素比较的过程，是一个从后到前扫描的过程。在扫描时，我们将已排好序的元素先后挪位，为新的元素提供插入位置。这也叫做 in-place 排序，这样我们就不需要额外的内存空间了。

具体步骤

从第二个元素（第一个要被排序的新元素）开始，从后向前扫描之前的元素序列
如果当前扫描的元素大于新元素，将扫描元素移动到下一位
重复步骤2，直到找到一个小于或者等于新元素的位置
将新元素插入到该位置
对于之后的元素重复步骤1~4

伪代码 pseudo code：

function insertion_sort(array[]):
    for (i = 1; i < array.length; i++):
        cur = array[i]
        j = i - 1
        while (j >= 0 && array[j] > cur):
            array[j + 1] = array[j]
            j--
        array[j + 1] = cur

C++实现

void insertionSort(int[] array) {
    for(int i = 1; i < array.length; i++) {
        int cur = array[i];
        int insertionIndex = i - 1;
        while(insertionIndex >= 0 && array[insertionIndex] > cur) {
            array[insertionIndex + 1] = array[insertionIndex];
            insertionIndex--;
        }
        array[insertionIndex + 1] = cur;
    }
}

复杂度分析

时间复杂度：$O(n²)$
空间复杂度：$O(1)$

「时间复杂度」在此算法中就是计算比较的次数，第一个元素我们需要比较1次，第二个元素2次，对于第n个元素，我们需要和之前的元素比较n次，比较总数量也就是 1 + 2 + … + n = n(n + 1) / 2
≈ n^2。因为我们调换位置时采用「原地操作」(in place)，所以不需要额外空间，既空间复杂度为 $O(1)$。

快排 QuickSort

概念

快排是一种分治（Divide and Conquer）算法，在这种算法中，我们把大问题变成小问题，然后将小问题逐个解决，当小问题解决完时，大问题也迎刃而解。

快排的基本概念就是选取一个目标元素，然后将目标元素放到数组中正确的位置。然后根据排好序后的元素，将数组切分为两个子数组，用相同的方法，在没有排好序的范围使用相同的操作。

具体步骤

对于当前的数组，取最后一个元素当做基准数（pivot）
将所有比基准数小的元素排到基准数之前，比基准数大的排在基准数之后
当基准数被放到准确的位置之后，根据基数数的位置将元素切分为前后两个子数组
对子数组采用步骤1~4的递归操作，直到子数组的长度小于等于1为止

伪代码（Pseudo code）

function quickSort(array[], left, right):
    partitionIndex = partition(array, left, right)
    quickSort(array, left, partitionIndex - 1)
    quickSort(array, partitionIndex + 1, right)

function partition(array[], left, right):
    pivot = array[right]
    smallerElementIndex = left
    biggerElementIndex = right - 1
    while(true):
        while(smallerElementIndex < right && array[smallerElementIndex] <= pivot):
            smallerElementIndex++
        while(biggerElementIndex >= left && array[biggerElementIndex] > pivot):
            rightIndex--
        if(smallerElementIndex > biggerElementIndex) break
        swap(array, smallerElementIndex, biggerElementIndex)
    # Now array[smallerElementIndex] is the first element bigger than pivot
    swap(array, smallerElementIndex, right)
    return smallerElementIndex

C++实现

void quickSort(int[] array, int left, int right) {
    if(left >= right) return;
    int partitionIndex = partition(array, left, right);
    quickSort(array, left, partitionIndex - 1);
    quickSort(array, partitionIndex + 1, right);
}

int partition(int[] array, int left, int right) {
    int pivot = array[right];
    int leftIndex = left;
    int rightIndex = right - 1;
    while(true) { 
        while(leftIndex < right & array[leftIndex] <= pivot) {
            leftIndex++;
        }
        while(rightIndex >= left && array[rightIndex] > pivot) {
            rightIndex--;
        }
        if (leftIndex > rightIndex) break;
        swap(array, leftIndex, rightIndex);
    }
    swap(array, leftIndex, right); // swap pivot to the right position
    return leftIndex;
}

void swap(int[] array, int left, int right) {
    int temp = array[left];
    array[left] = array[right];
    array[right] = temp;
}

复杂度分析

时间复杂度：$O(n^2)$，平均时间复杂度：$O(n\log N）$
空间复杂度：$O(n)$，平均空间复杂度：$O(\log N)$

在最坏的情况下，如果元素一开始就是从大到小倒序排列的，那么我们每个元素都需要调换，时间复杂度就是 $O(n^2)$。当正常情况下，我们不会总碰到这样的情况，假设我们每次都找到一个中间的基准数，那么我们需要切分logN次，每层的划分(Partition)是 $O(N)$，平均时间复杂度就是 $O(n\log N)$。空间的复杂度取决于递归的层数，最糟糕的情况我们需要 $O(N)$ 层，一般情况下，我们认为平均时间复杂度是 $O(\log N)$。

归并排序 MergeSort

概念

归并排序也是一种基于归并操作的有效排序算法。在此算法中，我们将一个数组分为两个子数组，通过递归重复将数组切分到只剩下一个元素为止。然后将每个子数组中的元素排序后合并，通过不断合并子数组，最后就会拿到一个排好序的大数组。

归并排序和快排一样，也是一种分而治之算法，简单理解就是将大问题变为小问题，然后把所有小问题都解决掉，大问题就迎刃而解了。其中主要包括两个步骤：

切分步骤：将大问题变为小问题，通过递归解决更小的子问题。
解决步骤：将小问题的结果合并，以此找到大问题的答案。

以数组 [38, 27, 43, 3, 9, 82, 10] 为例，我们通过递归分组，之后原数组被分成长度小于等于2的子数组：

[38, 27], [43, 3], [9, 82], [10]

并将子数组中的元素排序好：

[27, 28], [3, 43], [9, 82], [10]

然后两两合并，归并成排好序的子数组：

[3, 27, 38, 43], [9, 10, 82]

最后将子数组合并为一个排好序的大数组：

[3, 9, 10, 27, 38, 43, 82]

具体步骤

递归切分当前数组
如果当前数组数量小于等于1，无需排序，直接返回结果
否则将当前数组分为两个子数组，递归排序这两个子数组
在子数组排序结束后，将子数组的结果归并成排好序的数组

伪代码 Pseudocode

function mergeSort(array[], start, end):
    if (end - start < 1) return
    mid = (start + end) / 2
    mergeSort(array, start, mid)
    mergeSort(array, mid + 1, end);
    merge(array, start, mid, end)

function merge(array[], start, mid, end):
    helper[] = array.copy()
    leftStart = start, rightStart = mid + 1
    while(leftStart <= mid || rightStart <= end):
        if(helper[leftStart] <= helper[rightStart]):
            array[start++] = helper[leftStart++]
        else:
            array[start++] = helper[rightStart++]
    if(leftStart <= mid): 
        while(leftStart <= mid):
            array[start++] = helper[leftStart++]
    else:
        while(rightStart <= end):
            array[start++] = helper[rightStart++]

C++实现

void mergeSort(int[] array) {
    int[] helper = copy(array);
    mergeSort(array, helper, 0, array.length - 1);
    return array;
}

void mergeSort(int[] array, int[] helper, int left, int right) {
    if(right - left < 1) return;
    int mid = left + (right - left) / 2;
    mergeSort(array, helper, left, mid);
    mergeSort(array, helper, mid + 1, right);
    merge(array, helper, left, mid, right);
}

void merge(int[] array, int[] helper, int left, int mid, int right) {
    for(int i = left; i <= right; i++) {
        helper[i] = array[i];
    }
    int leftStart = left;
    int rightStart = mid + 1;
    for (int i = left; i <= right; i++) { 
        if (leftStart > mid) {   
            array[i] = helper[rightStart++];
        } else if (rightStart > right) {
            array[i] = helper[leftStart++];
        } else if (helper[leftStart] < helper[rightStart]) {
            array[i] = helper[leftStart++];
        } else {
            array[i] = helper[rightStart++];
        }
     }
}

int[] copy(int[] array) {
     int[] newArray = new int[array.length];
     for(int i = 0; i < array.length; i++) { 
         newArray[i] = array[i];
     }
     return newArray;
}

复杂度分析

时间：$O(n\log N)$
空间：$O(N)$

在将大问题切分为小问题的过程中，我们每次都将数组切一半，所以需要logN次才能将数组切到一个元素，所以递归的层级就是logN。在每一层中，我们要对子数组进行归并，我们要扫描所有的元素，所以每一层需要N次扫描。那么，时间复杂度就是层级乘以每层的操作 = $\log N * N$ = $O(N \log N)$。在每一层中，我们需要一个临时的数组来存放原先的数据，然后在这个数组中扫描子数组的元素，并将其排好序放回原来的数组，所以空间复杂度就是 $O(N)$。

实践练习

堆栈和队列

在这一章我们来了解两个很特殊的数据结构：堆栈 (Stack) 和队列 (Queue)。这两个数据结构类似垃圾桶和队伍，栈是先进后出型，队列是先进先出型。

堆栈（Stack）

概念

堆栈是一种常用的数据结构，这种数据结构的存储方式和垃圾桶一样，后面放进去的元素可以先取出来，而最早放入的元素会被压在最下面，最后才能被拿出来。我们也可以把栈的储存方式简单理解为堆盘子，后面加入的盘子会被堆到最上面，最早堆入的盘子在最下面。

所以栈是一种后进先出（Last In First Out）的数据结构，后入的元素先出，先入的元素后出。

堆栈主要支持以下两种操作：

入栈（Push）：将一个元素放入栈，用来加入数据。
出栈（Pop）：将一个元素弹出栈，用来删除数据。

还有以下两种辅助操作：

Peek：查看最顶部的元素。
isEmpty：查看栈是否为空。

数组栈实现

链表有两种实现方式，一种是数组，另一种是链表。数据的实现方式很简单，以下是数组栈的定义：

class Stack {
    static final int CAPACITY = 1000;
    int top;
    int stack[];

    public Stack() {
        top = -1;
        stack = new int[CAPACITY];
    }
}

在数组栈中，我们使用数组来储存数据，其中包含一个 CAPACITY 来限制栈的容量，并使用指针 top 来记录最顶端元素的位置，top 初始化为-1，代表数组栈没有任何元素。以下是 push() 和 pop() 方法的定义：

bool push(int val) {
    if (top >= (CAPACITY - 1)) {
        cout << "Stack Overflow." << endl;
        return false;
    }
    stack[++top] = val;
    return true;
}

int pop() {
    if (top < 0) {
        cout << "Stack Underflow." << endl;
        return 0;
    }
    int element = stack[top--];
    return element;
}

在 push() 中，我们需要检查顶部元素是否达到容量限制，如果是，输出“溢出栈”错误。否则移动 top 指针，加入新的元素。在 pop() 中，也要查看栈是否为空，如果是，那么输出“栈下溢”错误。否则将 top 指针减一。另外还有 peek() 和 isEmpty() 的实现：

int peek() {
    if (top < 0) {
        cout << "Stack Underflow" << endl;
        return 0;
    }
    int element = stack[top];
    return element;
}

bool isEmpty() {
    return top < 0;
}

peek() 也要查看栈是否为空，如果不是，直接返回 top 指向的元素。isEmpty() 只要查看 top 是否小于0即可。

链式栈实现

除了数组栈，我们也可以使用链表来实现栈，以下是链式栈的定义：

class ListStack {

    static class StackNode {
        int val;
        StackNode next;
        StackNode(int val) {
            this.val = val;
        }
    }

    StackNode top;

    public ListStack() {
        top = null;
    }
}

在链式栈中，我们先定义节点 StackNode，节点中包含数值和下一个节点的指针。在链式栈中，我们只需要记录 top 节点，在初始化时定义为 null。以下是 push() 和 pop() 的定义：

void push(int val) {
    StackNode newNode = new StackNode(val);
    if (top == null) {
        top = newNode;
    } else {
        StackNode temp = top;
        top = newNode;
        newNode.next = temp;
    }
    cout << val << " is pushed to stack." << endl;
}

int pop() {
    if (top == null) {
        cout << "Stack is Empty." << endl;
        return Integer.MIN_VALUE;
    }
    int popped = top.val;
    top = top.next;
    return popped;
}

在 push() 中，我们先创建新的节点 newNode，如果栈为空，那么直接将 newNode 赋给 top。如果不为空，就将新元素的下一节点指向当前的 top，并将 newNode 更新为 top 节点。在 pop() 中，也要先检查栈是否为空，不为空的话，记录下 top 的数据作为返回值，并将 top 更新为自己的下一个节点。以下是链式栈 peek() 和 isEmpty() 的定义：

int peek() {
    if (top == null) {
        cout << "Stack is empty." << endl;
        return Integer.MIN_VALUE;
    }
    return top.val;
}

bool isEmpty() {
    return top == null;
}

在栈不为空的情况下，peek() 只需查看 top 的值即可，isEmpty() 也只要查看 top 是否是 null 就可以了。不管是用数组还是链表来实现栈，我们都只要处理头节点 top，所以栈的所有操作都为 O(1)。

队列（Queue）

概念

队列是很好理解的一种数据结构，顾名思义，队列数据结构就和我们平时排队一样，先进入的元素先出，后进入的元素后出。队列的两端都是开的，一段负责插入新元素，另一端负责删除元素。

队列主要支持以下两种操作：

入队（enqueue）：增加一个新的元素
出队（dequeue）：删除一个元素

还支持其他辅助操作：

peek – 查看队列最前端的元素
isFull – 查看队列是否满了
isEmpty – 查看队列是否为空

数组队列实现

队列和堆栈一样，也可以使用两种实现方式，一种是使用数组，叫做顺序队列，另一种是使用链表实现，叫做链式队列。以下我们会先实现一种更常见的数组队列，叫做循环队列，它和基础的顺序队列相比较，更能有效地利用数组空间。以下是循环队列的定义：

class ArrayQueue {
    int front, rear, size;
    int capacity;
    int array[];

    public ArrayQueue(int capacity) {
        this.capacity = capacity;
        front = rear = size = 0;
        array = new int[capacity];
    }
}

在循环队列中，我们需要 capacity 来限制队列的长度，并创建两个指针 front 和 rear，front 用来指向队列的头部，而 rear 指向队列的尾部。队列总是从头部取出元素，从尾部插入新元素，在操作队列时，我们只需要移动 front 和 rear 两个指针即可。我们还需要一个额外的size变量来记录元素的数量， front，rear 和 size 都初始化为0 。

以下是 enqueue() 和 dequeue() 的定义：

void enqueue(int item) {
    if (isFull()) return;
    array[rear] = item;
    rear = (rear + 1) % capacity;
    size++;
    cout << item << " is enqueued." << endl;
}

int dequeue() {
    if (isEmpty()) return Integer.MIN_VALUE;
    int item = array[front];
    front = (front + 1) % capacity;
    size --;
    return item;
}

在新元素入队的时候，我们需要先判断队列是否已满（isFull() 的代码在下一段）。如果未满，那么就把元素插入 rear 的位置，并将 rear 加1，并与 capacity 取模，然后增加 size。在出队的时候，先要检查队列是否为空（isEmpty() 的代码在下一段），记录下删除元素的值后，我们将 front 指针增加1，与 capacity 取模，然后将 size 减少1。以下是辅助操作的定义：

int peek() {
    if (isEmpty()) return Integer.MIN_VALUE;
    return array[front];
}

bool isFull() {
    return size == capacity;
}

bool isEmpty() {
    return size == 0;
}

peek() 只要查看 front 指针指向的值即可，isFull() 要检查 size 是否和容量 capacity 相同，isEmpty() 直接查看 size 是否等于0。

链式队列实现

用链表实现队列也很简单，和数组实现相似，也需要两个指针（front 和 rear）来实现。以下是 ListQueue 和 QueueNode 的定义：

class ListQueue {

    QueueNode front;
    QueueNode rear;

    static class QueueNode {
        int value;
        QueueNode next;
        public QueueNode(int value) {
            this.value = value;
        }
    }
}

在链式队列中，我们需要定义节点 QueueNode，QueueNode 中含有两个值：一个是节点的数值 value，另一个是指向下一个节点的 next 指针。在链式队列 ListQueue 中，我们只需要两个节点 front 和 rear，front 用来指向队列最前端的节点，而 rear 用来指向尾节点。以下是两个重要操作 enqueue() 和deuque() 的实现：

void enqueue(int value) {
    QueueNode newNode = new QueueNode(value);
    if (this.rear == null) { // Queue is empty
        this.front = this.rear = newNode;
        return;
    }
    this.rear.next = newNode;
    this.rear = newNode;
}

int dequeue() {
    if (this.front == null) {
        cout << "The queue is empty." << endl;
        return Integer.MIN_VALUE;
    }
    QueueNode frontNode = this.front;
    this.front = this.front.next;
    if (this.front == null) {
        this.rear = null;
    }
    return frontNode.value;
}

在 enqueue()中，我们先创建一个新的节点，如果队列为空，那么将头节点和尾节点同时指向新节点，结束操作。如果队列不为空，只要尾节点的 next 指针指向新节点，然后将尾节点指向新节点。在 dequeue() 中，如果头节点 front 为空，直接返回默认数值。队列不为空的情况下，记录下 front 的数值作为返回值，并将头节点更新为下一节点。

实践练习

Stack相关：

Queue相关：

优先队列和堆

哈希表

树

树的基本概念

树是一种非常有用的数据结构，数据库的实现大部分都是基于树结构的，比如在一种特殊的树结构“红黑树”中，寻找任意元素的复杂度仅仅只需要 $\log(N)$。树是一种由节点组成的数据结构，但它比链表更加高级，在链表中，一个节点连接着另一个节点，树也是由许多的节点构成的，唯一的区别就是一个树节点可以连接多个树节点，一颗树只有一个根节点，根节点作为起源，由它展开一个树状的数据结构。

在实现树之前，我们来了解一下树的基本定义：

在树中，每个节点都含有自己的数值，以及与之相连的子节点，连接节点的线叫做相连线（edge）。如下图所示，A是根节点（root），也是B和C的父节点（parent node），也就是说B、C都是A的子节点（child node）。同理，B是D和E的父节点，以此类推。要注意H、I、J、F、G都是尾节点（leaf node），因为它们位于树的最底部，没有任何子节点。

一个树由许许多多的子树（sub-tree）构成，每个节点加上它所有的子节点（包括子节点的子节点们）就是一个子树，如上图，D、H、和I就是能构成sub tree，B、D、E、H、I、和J也是一个子树。

树中还有两个重要的名词要记住，一个是节点的高度（height），意味着此节点到尾节点之间相连线的数量，B的高度就是2，因为B到尾节点H之间的edge数量为2。另一个名词就是节点的深度（depth），意味着此节点到根节点的edge数量，D的深度是2，因为D到根节点A之间的edge数量是2。

树的种类

树的种类有很多，其中排序二叉树会是我们的重点，在后面也会学习如何用Java将其实现，至于其他的树类型，大家目前只要大概理解就好：

二叉树（Binary Tree）：每个节点最多含有两个子节点，上面图示中的树就是二叉树。
完全二叉树（Complete Binary Tree）：假设一个二叉树深度（depth）为d（d > 1），除了第d层外，其它各层的节点数量均已达到最大值，且第d层所有节点从左向右紧密排列，这样的二叉树就是完全二叉树。
满二叉树（Full Binary Tee）：在满二叉树中，每个不是尾节点的节点都有两个子节点。
排序二叉树（Binary Search Tree）：在此树中，每个节点的数值比左子树上的每个节点都大，比所有右子树上的节点都小。
平衡二叉树（AVL Tree）：任何节点的两颗子树的高度差不大于1的二叉树。
B树（B-Tree）：B树和平衡二插树一样，只不过它是一种多叉树（一个节点的子节点数量可以超过二）。
红黑树（Red—Black Tree）：是一种自平衡二叉寻找树。

二分查找树（Binary Search Tree）的实现

接下来，我们就来实现二分查找树（Binary Search Tree），也叫做排序二叉树。在这种树中，我们寻找一个特定的数值非常容易，因为二分查找树满足以下的特性：每个节点都比自己左子树上的节点大，并比右子树上的节点小。如果我们想要寻找一个特定的元素，只需要依赖其特性，顺着特定的路径就能找到目标。

在此树中，搜索、插入和删除的复杂度等于树高，往往就是 $O(\log N)$，非常合适用来存储数据。接下来我们就使用Java来实现这个数据结构，首先我们定义好树和节点：

树的遍历 Tree Traversal

前序遍历 Preorder Traversal

中序遍历 Inorder Traversal

后序遍历 Postorder Traversal

实践练习

图

今天我们就来学习“数据结构入门系列”中最后一个数据结构“图”。图是很常用的数据结构，比如计算机网络、社交网络、谷歌地图都需要用到此数据结构，掌握图的知识可以完善我们的数据结构知识体系，也能帮助我们解决算法中更为复杂的问题。

简单来说，图是一种用来表示相连数据的数据结构，类似我们的社交网络，图中有很多的节点，每个节点代表一个数据，每个节点可以和其他节点相连。其中每个节点叫做顶点（vertice），连接顶点之间的线叫做相连线（edge）。下图就是一个用来表示社交网络的图数据结构：

在此图中，我们含有5个顶点和6条相连线，每个顶点包含了人名，而连接线代表相连人名之间是朋友关系。如果我们要更正式地表示图，那么图就可以用一对（V，E）集合来表示，其中V是一堆顶点的集合，而E是一堆相连线的集合，请看下图：

在此图中：V = {a, b, c, d, e}，E = {ab, ac, bd, cd, de}

上面提到的图是无向图，而常见的图有以下三种：

无向图（Undirected Graph）：在无向图中，每个顶点和其他顶点通过相连线连接。
有向图（Directed Graph）：有向图中的相连线是有方向的。
权重图（Weighted Graph）：在权重图中，每条相连线有各自的权重。

下图是有向图：

此图可以用来表示用户之间相互关注的情况，如果Mark指向Alice，则代表Mark关注了Alice。下图是权重图：

此图可以用来表示两个好友之间的亲密程度，数值越高代表越亲密。可见不同的图可以用来表示不同的关系，而有向图是最常见的图，我们接下来就来实现有向图。

有向图的实现（Directed Graph）

有向图的实现有两种，一种是用矩阵（Matrix）的形式来实现，另一种是用链表（List）的形式来实现。

如果我们使用矩阵来实现有向图，来看一个例子：

每行代表相应的顶点，如果M[i][j] = 1，那么就代表顶点 i 连向 j，如果是0，则表达顶点间没有联系。用矩阵的方式来实现图的优势很明显，我们可以很快地判断两个顶点之间是否相连，可是用矩阵实现的空间复杂度很高，我们需要O(V^2)来记录所有的数据，不管顶点之间是否有相连线。为了解决空间复杂度的问题，我们可以使用链表的方式来实现图：

在链表实现中，我们实际上使用了储存链表的数组来表示图，图的左侧用数组来实现，代表我们的所有顶点，而每个顶点含有一个链表，链表上储存了该顶点指向的顶点。

图的遍历（Graph Traversal）

遍历图有两种常见的方式，一种是深度优先搜索（Depth-first Search），另一种是宽度优先搜索（Breadth-first search）。首先我们来学习深度优先搜索：

深度优先搜索（Depth-First Search）

图的深度优先和树的前序遍历（Pre-order Traversal）有点类似。在深度优先遍历中，我们假设初始状态所有顶点都没被访问，然后从每一顶点v出发，先访问该顶点，然后依次从它的各个未被访问的邻接点出发，深度优先遍历图，直到图中所有和v相通的顶点都被访问到。若遍历完后，还有其他顶点没被访问到，则另选一个未被访问的顶点作为起始点，重复上述过程，直到所有顶点都被访问完为止。

下面以“有向图”为例，来对深度优先搜索进行演示：

对于上面的图，我们从顶点A开始搜索：

以下是具体的遍历步骤：

访问A
访问B（在访问A之后，接下来应该访问的是A出发的另一个顶点，既顶点B）
访问C（在访问B之后，接下来访问的是从B出发的另一个顶点，既C，E，F。在此图中，我们按照字母排序顺序访问，因此先访问C。）
访问E（接下来访问与C连接的另一个顶点E。）
访问D（接下来访问从E出发的顶点B和D，因为B已被访问过，所以访问顶点D。）
访问F（接下来回溯“访问A的另一个连接顶点F”）
访问G

因此访问顺序是：A -> B -> C -> E -> D -> F -> G。

广度优先搜索（Breadth-First Search)

广度优先搜索算法也叫做“宽度优先搜索”或“横向优先搜索”，其方法是从图中的某一顶点v出发，在访问了v之后依次访问v的各个没有访问到的邻接点，然后分别从这些邻接点出发依次访问他们的邻接点，使得先被访问的顶点的邻接点先与后被访问顶点的邻接点被访问，直到图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问到的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程是以v为起点，由近至远，依次访问和v有路径相通且路径长度为1，2，…的顶点。

下面以“有向图”为例，对广度优先搜索进行演示：

以下是访问步骤：

访问A
访问B
依次访问C，E，F（在B被访问之后，接下来访问B的邻接点，既C，E，F。）
依次访问D，G（在访问完C，E，F之后，再依次访问他们出发的另一个顶点。还是按照C，E，F的顺序访问，C的已经全部访问过了，那么就只剩下E，E；先访问E的邻接点D，再访问F的邻接点G。

访问顺序是：A -> B -> C -> E -> F -> D -> G。

以上就是图的两种遍历方法：深度优先遍历和广度优先遍历。简单来说，深度优先遍历就是选择一条路径走到头再回来，而广度深度优先就是将最近的邻接点先访问完，再向更远的顶点延伸。