常用数据结构算法及其示例-基础数据结构

发表于 | 分类于 | | 浏览 次
字数统计: 5.9k | 阅读时长 ≈ 21

记录一些笔记，将自己看到听到的有关数据结构与算法的内容都记录下来。这是关于基础数据结构的部分，包括数组、链表、栈、队列。

数组

数组是最基本的数据结构了，数组(Array)的定义是：数组是一种线性表数据结构，它用一组连续的内存空间存放一组具有相同类型数据。

这里有三个关键点，线性表，连续的内存空间 和 相同类型。

线性表的数据结构除了数组还有：队列， 栈， 链表；与之对应的非线性表的数据结构有：数， 图。

连续存储空间和相同数据类型这个特定决定了数组的本质，使其具有了“随机访问”的特性，但是也让其在某些操作(比如插入、删除元素)方面非常低效，是把双刃剑吧，具体要根据使用场景来决定是否使用数组。

数组的随机访问是通过数组基址和数组下标实现的，基址加上下标与数据宽度的乘积就是要访问数据的地址，寻址公式：

1
a[i]_address = base_address + i * data_type_size

data_type_size就是数据的宽度，也就是每个元素占用内存的大小，常用数据类型占用内存大小如下所示：

type byte ch bit
char 1 字节 8
short 2 字 16
int 4 双字 32
long 8 四字 64
char * 4(32bit) 8(64bit) 双字, 四字 32,64
float 4 双字 32
double 8 四字 64

可以用一个图表示数组内存分布：

1

数组查找的时间复杂度是O(1)这种说法是不准确的，应该说是数组按下标随机访问的时间复杂度是O(1)。

数组插入和删除真的比较低效吗？

看情况，如果数组本来是有序的，要在数组中插入一个元素并保证插入后的数组还是有序的，那么这时的插入操作就是低效的；

如果数组本来就是无序的，只是用来保存数据的，这时插入数据时就可以不用搬移大量数据了只需要将第k位数据搬移到数组最后，然后将元素插入到第k位即可。

数组的删除也可以先标记要删除的位置，当数组不够使用时再将标记过的元素删除，这样避免了多次删除造成的多次数据搬移操作，降低性能损耗。JVM的垃圾回收也是使用的这个思想。

注意的问题

  1. 数组越界问题

    先看一段代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    int main(int argc, char* argv[]){
        int i = 0;
        int arr[3] = {0};
        for(; i<=3; i++){
            arr[i] = 0;
            printf("hello world\n");
        }
        return 0;
    }

    这段代码的执行结果是循环打印hello world，而不是打印三次hello world。因为数组越界了，a3正好是变量i的存储位置，所以就一直循环了。

    c语言没做数组越界判定，Java有做，编译的时候会直接报错。

  2. 容器能否完全代替数组？

    当然不能，容器有一个弊端就是不能存储基本类型的数据，都是封装后的数据。

    当然这层封装也有好处，对于数组的插入删除操作在容器内都有对应实现，而且容器支持动态扩容。

    什么时候用数组，什么时候用容器呢？

    • 比如Java ArrayList无法存储基本类型，如int， long，需要封装成对应的Integer，Long类才能存储，但是Autoboxing,Unboxing对性能有一定损耗，在关注性能的时候可以使用数组，不怎么关注性能的时候使用容器。

    • 如果数据量大小已知，并且对数据的操作非常简单，可以选择使用数组。

    • 需要使用到多维数组时，直接使用数组会更加直观，如Object[][] Array;但是容器的话需要这样定义：ArrayList array。

      业务开发直接使用容器就行了，省时省力。对性能要求比较高的场景使用数组，比如网络框架，性能要做到极致。

  3. 数组为什么从0开始编号？

    • 一般数组的下表我们是作为偏移量处理的，在计算第k个元素的地址时直接使用a[k]_address = base_address + k * type_size就可以计算得到了，如果从1开始编号，那么计算公式就变成了a[k]_address = base_address + (k-1)*type_size`，计算级需要多一次减法计算，对于数组这种经常使用的数据结构，会对性能造成损耗。

    • 历史原因，C语言作者就是这样做的，你能怎么样。

链表

这里没有特殊说明链表指的都是单向无循环链表。

  • 链表的插入和删除不需要数据搬移，只需要考虑相邻节点的指针改变即可，对应时间复杂度为O(1)。

  • 链表随机访问性能没有数组好，需要从链表头一个一个往下查找，所以时间复杂度是O(n)。

  • 双向链表支持O(1)时间复杂度的情况下找到前驱节点，这就使双向链表在某些情况下插入、删除等操作比单链表简单、高效。比如将新的节点插入到某个节点之前。

  • Java的LinkedHashMap这个容器就使用了双向链表这种数据结构。

注意事项

  • 链表与指针关系密切，有些语言没有指针，取而代之的引用，都是一个意思，都是表示用于存储内容的内存地址。

    将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址指向了这个变量，通过指针就能找到这个变量。

  • 警惕内存泄漏和指针丢失，链表操作要注意顺序，了解当前改变的节点指向。

  • 使用哨兵简化难度。对于插入头节点和删除尾节点的操作需要特殊处理，这时为了简化难度，可以使用一个哨兵节点作为头节点，里面不存储数据，只有一个指向第一个存储数据的节点即可，这样不管时插入还是删除都不用特殊处理。

    哨兵简化编程的技巧在插入排序、归并排序、动态规划中都有使用。

  • 重点留意边界条件，在写任何代码时都要多想想可能会遇到哪些边界情况或者异常情况，遇到后怎么处理。

    • 链表为空时代码能工作吗？

    • 链表只包含一个节点时能工作吗？

    • 链表只包含两个节点时能工作吗？

    • 代码在处理头节点和尾节点时能工作吗？

    • 。。。

  • 画图辅助思考，很好的方法，我一直在用。

  • 多谢多练，没捷径。

链表与数组的比较

时间复杂度 数组 链表
插入删除 O(n) O(1)
随机访问 O(1) O(n)

  • 数组简单易用，是连续存储空间，利用cpu的缓存机制可以预读数组中的数据，访问效率更高。链表相反，数据不是连续存储，不能预读。

  • 数组缺点是大小固定，出现不够用的情况时需要重新开辟数组空间并复制原有数组数据到新数组，费力耗时。链表不存在这个问题，理论上剩余内存空间有多大就可以创建多大的链表。

  • Java的ArrayList容器支持动态扩容的原理就是数组空间不够用时就再申请一个更大的空间（默认是原数组大小的1.5倍），将原有数据拷贝到新数组中，所以Java动态扩容再数据量很大的情况下会很耗时。比如一个1G大小的ArrayList要存满后再加入数据就会申请一个1.5G大小的存储空间，并把原来1G的数据拷贝到新申请的空间上，恐怖不。

  • 如果代码对内存要求严格，就用数组，因为链表需要额外空间存储指向下一个节点的指针，所以占用空间更多。而且对链表进行频繁插入删除操作会产生很多内存碎片，对于Java语言来说会导致频繁GC。

问题

  1. 如何使用链表实现最近最少使用策略LRU（Least Recently Used）？

    思路如下：维护一个有序单链表L，将最近访问的节点依次添加到链表中。当有新的节点被访问时，就先从头遍历链表L，如果数据已经存在于链表L中，就将包含这个数据的节点从原来的位置删除，并添加到链表L的头部；如果数据不在链表L中，就将创建包含该数据的节点插入到链表L的头部，不过插入前要判断一下缓存是否已满（因为缓存一般是指定大小的，不肯能把整个剩余内存空间都划分成缓存），如果缓存已满，就删除尾节点后再将新建节点插入L头部；如果缓存未满，直接插入头部即可。

    分析一下时间复杂度，不管缓存是否已满，都需要从头开始遍历链表L，因此时间复杂度是O(n)。

  2. 如何判断一个字符串是否是回文？

    1. 使用快慢指针定位中间节点，快指针每次遍历两个节点，慢指针每次便利一个节点，当快指针到达链表尾时，慢指针所在的位置就是链表中间节点的位置。这里分中间节点是奇数还是偶数节点的问题，需要分开处理。

    2. 从中间节点开始对后半部分逆序，

    3. 前半部分和后半部分比较，判断是否相等，相等就是回文，不相等就不是回文

    4. 最后再将后半部分逆序复原

      时间复杂度因为使用慢指针进行了便利，所以是O(n)，空间复杂度因为开辟了快慢指针(只有固定几个)，所以是O(1).

  3. 如何判断链表中是否存在环？如果存在怎么求环的长度和入口节点

    还是使用快慢指针， 如果两个指针能相遇，就存在环，而且相遇节点必在环内。

    先找到环内节点，根据这个节点找出环的长度n。

    再使用两个指针，先让一个指针移动n个位置，然后两个指针一起移动，两个指针相等的节点就是环的入口。

栈

为什么有了数组，还需要栈？从功能上来看，数组或链表确实可以替代栈，但是数组或链表比较灵活，暴露了太多操作接口，容易出错。

当数据集合只涉及在一端插入和删除元素，并且满足后进先出、先进后出的特性时，应该首选栈这种数据结构。

如何实现一个栈

使用数组和链表都可以，用数组实现的栈我们叫做顺序栈，使用链表实现的我们叫做链式栈。

顺序栈的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 基于数组实现的顺序栈
public class ArrayStack {
  private String[] items;  // 数组
  private int count;       // 栈中元素个数
  private int n;           // 栈的大小

  // 初始化数组，申请一个大小为 n 的数组空间
  public ArrayStack(int n) {
    this.items = new String[n];
    this.n = n;
    this.count = 0;
  }

  // 入栈操作
  public boolean push(String item) {
    // 数组空间不够了，直接返回 false，入栈失败。
    if (count == n) return false;
    // 将 item 放到下标为 count 的位置，并且 count 加一
    items[count] = item;
    ++count;
    return true;
  }
  
  // 出栈操作
  public String pop() {
    // 栈为空，则直接返回 null
    if (count == 0) return null;
    // 返回下标为 count-1 的数组元素，并且栈中元素个数 count 减一
    String tmp = items[count-1];
    --count;
    return tmp;
  }
}

支持动态扩容的顺序栈

上面基于数组实现的顺序栈是大小固定的，当栈满后该怎么办呢？总不能直接让程序崩溃吧，这就涉及到动态扩容的内容了。

栈的动态扩容跟数组动态扩容一样，因为顺序栈就是基于数组的嘛，栈满后，申请一个更大的数组，将原来的数据拷贝到新数组中后，再插入新元素。

这里插入操作时间复杂度分析会稍稍复杂一点，因为要考虑扩容的情况，出栈操作时间复杂度还是O(1)，这很简单。入栈操作时，如果空间不够，就要动态扩容，假设扩容为原数组的两倍大小，如果当前栈大小是K，并且已满，那么就需要做K个数据的搬移操作。但是这种情况毕竟是少数，大多数情况下的时间复杂度还是O(1)，所以均摊时间复杂度就是O(1)。

栈在函数中的应用

最常见的就是函数调用，线程运行过程中会占用一块独立内存空间，这块内存空间就是按栈这种数据结构组织的，用于存放函数调用时的临时变量，每进入一个函数，就会将临时变量作为一个栈帧入栈，当调用完成后，将对应栈帧出栈。

比如这样一段程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main() {
   int a = 1; 
   int ret = 0;
   int res = 0;
   ret = add(3, 5);
   res = a + ret;
   printf("%d", res);
   reuturn 0;
}

int add(int x, int y) {
   int sum = 0;
   sum = x + y;
   return sum;
}

对应的入栈情况就是下面这样：

2

栈在表达式求值中的应用

如四则运算，要计算12+25*4-10/2的值，就可以将数字和运算符号分别存放在两个栈中，从做向右遍历表达式，遇到数组就直接压入数字栈，入到运算符就与栈顶运算符比较，如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比栈顶运算符优先级低或者相同，就从数字栈顶去除两个操作数，进行计算，然后再压入数字栈；继续比较。

3

栈在括号匹配中的应用

1
2
3
4
比如`{{[()]}`是合法的，`{([]}`这种就是不合法的.
我们可以使用栈来从左到右依次扫描字符串，扫到左括号时就入栈，扫到右括号时就从栈顶取出一个左括号.
如果能够匹配，比如`(`跟`)`匹配，`[`跟`]`匹配，`{`跟`}`匹配，就继续扫描剩下的字符串.
如果扫描过程中出现不能匹配的情况，或者栈内没有数据，就是非法格式字符串。

所有括号扫描完后，如果栈为空，表示字符串合法，否则，字符串非法，有未匹配的左括号。

问题

  1. 为什么要用炸来保存函数临时变量，用其他数据结构行不行？

    为什么使用栈来保存函数临时变量呢？因为栈的特性和函数调用的特性啊，函数调用时相当于跳转到函数所在的内存地址开始执行指令，此时使用栈的话就比较方便，从函数所在地址开始分配一段栈空间，调用过程中的局部变量和函数参数都在这个栈内，调用完成后复位栈顶即可。用数组不能说不行，就是没栈方便。

  2. JVM内存管理中也有“堆栈”的概念，栈内存用来存储局部变量和方法调用，堆内存用来存储java对象，那么jvm中的栈与数据结构的栈是一回事吗？如果不是，那jvm为什么要叫做栈呢？

    内存中的栈与数据结构中的栈不一样，内存中的栈就是真实的物理内存，数据结构中的栈指的是抽象的数据存储结构。

    内存空间分三部分：代码区、静态数据区和动态数据区，动态数据区又分栈和堆。

    代码区存储方法体的二进制代码；静态数据区存储全局变量、静态常量、常量，常量包括final修饰的常量和String常量，系统自动分配和回收。栈存放运行时方法的形参、局部变量、返回值，由系统分配和回收；堆存放用户分配的内存空间，c中由用户自行管理，java中由用户申请，JVM释放。

队列

队列的特性先进先出，而且只能在一端进行插入，另一端进行删除操作。跟栈一样，都是一种操作受限的线性表数据结构。

队列根据实现方式的不同可以分为顺序队列和链式队列，使用数组实现的叫顺序队列，使用链表实现的叫链式队列。

队列的实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 用数组实现的队列
public class ArrayQueue {
  // 数组：items，数组大小：n
  private String[] items;
  private int n = 0;
  // head 表示队头下标，tail 表示队尾下标
  private int head = 0;
  private int tail = 0;

  // 申请一个大小为 capacity 的数组
  public ArrayQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

   // 入队操作，将 item 放入队尾
  public boolean enqueue(String item) {
    // tail == n 表示队列末尾没有空间了
    if (tail == n) {
      // tail ==n && head==0，表示整个队列都占满了
      if (head == 0) return false;
      // 数据搬移
      for (int i = head; i < tail; ++i) {
        items[i-head] = items[i];
      }
      // 搬移完之后重新更新 head 和 tail
      tail -= head;
      head = 0;
    }
    
    items[tail] = item;
    ++tail;
    return true;
  }

  // 出队
  public String dequeue() {
    // 如果 head == tail 表示队列为空
    if (head == tail) return null;
    // 为了让其他语言的同学看的更加明确，把 -- 操作放到单独一行来写了
    String ret = items[head];
    ++head;
    return ret;
  }
}

这里需要注意入队操作，当队尾指针指向数组最后一个元素时，再进行数据入队操作时需要现将队列数据进行搬移，将head放到数组第一个元素所在位置，tail放到数组tail-head的位置。

4

使用链表实现的链式队列：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class QueueBasedOnLinkedList {

  // 队列的队首和队尾
  private Node head = null;
  private Node tail = null;

  // 入队
  public void enqueue(String value) {
    if (tail == null) {
      Node newNode = new Node(value, null);
      head = newNode;
      tail = newNode;
    } else {
      tail.next = new Node(value, null);
      tail = tail.next;
    }
  }

  // 出队
  public String dequeue() {
    if (head == null) return null;

    String value = head.data;
    head = head.next;
    if (head == null) {
      tail = null;
    }
    return value;
  }

  public void printAll() {
    Node p = head;
    while (p != null) {
      System.out.print(p.data + " ");
      p = p.next;
    }
    System.out.println();
  }

  private static class Node {
    private String data;
    private Node next;

    public Node(String data, Node next) {
      this.data = data;
      this.next = next;
    }

    public String getData() {
      return data;
    }
  }
}

链式队列入队和出队没有限制，直接进行指针的移动即可。

循环队列

循环队列设计比较巧妙，是将队列尾与队列头逻辑连接的一种数据结构。

写出循环队列的关键是判断出队满和队空的条件，队空的条件很好判断，head==tail时队列就是空的；队列满的条件稍微复杂一点，这里把队列最后一个位置留出来不用，当(tail+1)%length==head时，队列就是满的，length是队列的长度。

5

循环队列实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class CircularQueue {
  // 数组：items，数组大小：n
  private String[] items;
  private int n = 0;
  // head表示队头下标，tail表示队尾下标
  private int head = 0;
  private int tail = 0;

  // 申请一个大小为capacity的数组
  public CircularQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

  // 入队
  public boolean enqueue(String item) {
    // 队列满了
    if ((tail + 1) % n == head) return false;
    items[tail] = item;
    tail = (tail + 1) % n;
    return true;
  }

  // 出队
  public String dequeue() {
    // 如果head == tail 表示队列为空
    if (head == tail) return null;
    String ret = items[head];
    head = (head + 1) % n;
    return ret;
  }

  public void printAll() {
    if (0 == n) return;
    for (int i = head; i % n != tail; ++i) {
      System.out.print(items[i] + " ");
    }
    System.out.println();
  }
}

阻塞队列与并发队列

实际使用中，有一个阻塞队列，就是在队列的基础上增加了阻塞操作，在队空的时候读操作被阻塞，直到有队列有新数据存入，然后返回；在队列满时，插入操作阻塞，直到队列有空闲位置后再插入数据，然后返回。

这其实就是生产者消费者模型，而且阻塞队列很肯定不是一个生产者或者消费者，当有多个消费者时，多个线程会并发对队列读，这时就会有线程安全问题，那么如何实现一个线程安全的队列呢？

线程安全的队列也叫并发队列，最简单的方法是在入队和出队操作上加锁，但是锁的粒度比较大导致并发度比较低，同一时刻仅允许一个入队或者出队操作。实际中，基于数组的循环队列可以利用CAS原子操作，实现高效并发队列。这也是循环队列比链式队列应用更加广泛的原因。

问题

  1. 线程池没有空闲线程时，新的任务请求线程资源时，线程池该怎么处理，各种处理策略是怎么实现的？

    一般有两种处理策略，阻塞和非阻塞。阻塞就是直接拒绝任务请求，非阻塞就是排队，新来的请求都放入到一个队列中，等线程池有空闲线程时再从等待队列中拿出请求处理。

    队列一般使用基于数组的循环队列，因为链式队列没有大小限制，来多少请求就加多少，如果请求过多，就会导致排队等待时间过长，影响用户体验。使用循环队列可以设置队列大小，队列满后新的请求就不再处理，直接拒绝连接，这比较适合对响应时间敏感的系统。至于队列的大小根据实际业务需要和服务器资源进行配置。

    队列可以应用到大部分资源有限的场景，比如数据库连接池。没有空闲资源时就排队，通过队列这种数据结构实现排队请求的机制。

  2. 除了线程池用到排队请求，还有那些场景用到了排队？

    分布式系统中消息队列，也是一种队列结构。

  3. 关于无锁并发队列，有什么好的实现方法？

    可以使用CAS实现无锁队列，每次入队前，获取tail的位置，入队时检查tail是否发生了变化，如果没有就正常入队，否则入队失败，出队是同样的原地，出队前检查head的位置，出队时比较head的位置是否发生了变化，如果没有就正常出队，否则出队失败。