最近在看极客时间覃超的《算法面试通关 40 讲》，也一起看了一些数据结构，正好在这里进行一下整理。

主要分为数据结构和算法两大章节，每个章节里面都会先结合自己的理解对它的定义进行一下解释，然后会拿出例题来进行实战。

数据结构

数组

链表

队列

先入先出（first in first out FIFO）

习题：用栈实现队列

普通队列

优先队列

堆栈

后入先出(last in first out LIFO)

习题：用队列实现栈

树

链表是一种特殊的树，当每个链表节点的链表变成多个时就变成了树

二叉搜索树（binary search tree BST）

性质：

• 左子树上所有节点的值均小于它的根节点的值
• 右子树上所有节点的值均大于它的根节点的值；
• 左，右子树也分别满足以上性质

AVL,红黑树学习

红黑树

手写红黑树的简单实现

B 树

B+树

MySQL 的 Innodb 中使用的索引就是采用的 B+树的数据结构进行存储的。

题目描述：

你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。
你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。
示例:
输入: 4
输出: false
解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；
因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。

思路：

先考虑一下什么情况会输呢，就是最后的石头被对手拿走，那么只要保证最后剩余1-3块石头我们即可获胜。如何能确保最后一定剩余1-3块呢，就要我们在每一步的时候跟对手拿的块数总和等于4。所以我们这道题就可以判断总块数是不是4的倍数，如果不是我们就可以赢。