数组、链表、栈、队列、哈希、树、图等数据结构基础
数组
数组具有随机访问的特点，是内存中一块连续的存储区域，适用于读取大于写入的情况。
- 查找复杂度：准确讲是随机访问的复杂度，是O(1)。
- 插入复杂度：因为插入需要移动元素，与问题规模n成正比，为O(n)
- 删除复杂度：也需要移动元素，为O(n)
链表
内存中不连续，适用于写入大于读取的场景
- 查找复杂度：需要从头节点进行遍历，O(n)
- 删除复杂度：删除步骤复杂度为O(1)，但删除前的查找复杂度为O(n)
- 插入复杂度：插入步骤复杂度为O(1)，但插入前的查找复杂度为O(n)
栈
栈属于逻辑结构，既可以由数组实现，也可以由链表实现，符合先入后出（FILO），栈顶（top）/栈底（bottom）/入栈(push)/出栈(pop)，栈的入栈与出栈复杂度都为O(1)。
队列
队列属于逻辑结构，既可以用链表实现，也可以用数组实现，符合先入先出（FIFO），队首（front）/队尾(rear)/出队(deQueue)/入队(enQueue)，队列的入队复杂度和出队复杂度都是O(1)。
注意
- 当队列以数组实现时，队列的队尾（与栈的栈顶不同，栈顶指向的时当前最后一个入栈的元素位置）指向的是下一个入队列的元素位置，因此队列的最大容量是数组长度-1
- 元素出队时，队首移动，但队尾不移动；元素入队时，队尾移动，但队首不移动
基于以上特点，数组实现的队列，多次入队出队后，队首左侧的元素空间都会被浪费。
解决方法：使用循环数组来实现队列，可以最大化利用空间：当队尾移动至数组最后一位时，下一次元素入队时，若队首左侧有空位，则队尾移动至数组索引0的位置。
队列（基于循环数组实现）的核心公式
- 判断队列满的条件：(rear + 1)% capacity = front
- 遍历按序输出队列元素时的判断条件：for(int i = front ; i != rear ; i = (i+1) % capacity)
