详解四大基础数据结构：数组、链表、队列和栈。

谁借莪１个温暖的怀抱￠ 2024-03-23 15:11 14阅读 0赞

### 序 ###

开新坑了，这次是`数据结构与算法专题`，保证不鸽，此专题将会分为三部分：

1.  **基础数据结构** ：除了本章标题中这些还会有哈希表、树、堆等数据结构。
2.  **排序算法** ：单独介绍一些常用常见算法如，冒泡、选择、插入、归并、快排、堆排序等。
3.  **高级数据结构** ：高级数据结构不是说它更高级，主要是在前文的基础数据结构上的扩展如，B+树（树中N树的一种）、红黑树（业界常用的自平衡树）和一些改进的散列如布谷鸟之类的。

当然上面这些只是我目前的写作计划，可能会加入更多内容，请大家拭目以待吧。

--------------------

本章正式开始之前，先聊聊我对数据结构的看法吧，老生常谈的一句话是：

> 程序 = 数据结构 + 算法。

学习数据结构与算法对我们写程序的人有多么重要我举几个例子，大家就明白了。

首先大家要知道，数据结构和算法这些东西都是为了解决现实问题而生的，比如我们的数据库中有1000w条数据吧，我想瞬间查询到一个我想要的数据，这能做到吗？

如果你没有学过数据结构与算法，对查询这种事第一时间的反应应该是遍历，但是对1000w 的数据量进行遍历将会极慢极慢。

有更好的办法来解决这个问题吗？

有，可以通过`哈希表`数据结构组织这些数据，哈希表能够让我们以O(1) 的时间复杂度快速查询到我们任何想要的数据，无论是1000w还是2000w，都能在瞬间查询到任何我们想查询到的数据，这是这么令人惊叹的效果，中间件`Redis` 和国产数据库新秀`TiDB`中的查询都是通过哈希表做的。

除了哈希表，我们也可以通过树型数据结构来做这件事，比如关系型数据库中常用的`B+索引`，它就是一个树型结构，是一个N树，它能以O(logN) 的速度进行查询，虽然速度上比不上哈希表，但是它支持范围查询，这对数据库很重要，所以数据库一般选它为主键索引。

上面我简单举了两个数据结构的例子，那算法呢？很多时候，算法与数据结构是相辅相成的。

**就比如树吧，它为什么查询快呢？**