Question

堆，栈，队列，单项链表，双向链表

Answer 1

一、栈：乒乓球盒子，先进后出

使用场景：在编译器的语法检查中，一个过程就是检查各种括号是否匹配，比如 ([]) ，这就是匹配的，而 {[}] 就不匹配了。可以用栈来实现括号匹配。

二、队列：排队取餐，先进先出

使用场景：当多个任务分配给打印机时，为了防止冲突，创建一个队列，把任务入队，按先入先出的原则处理任务。

三、堆：是用数组来存储的 完全二叉树 的结构（完全二叉树就是除了最底层，其它层都必须填满，最后一层可以从左到右填满）

堆分为两种：最大堆和最小堆，两者的差别在于节点的排序方式。

在最大堆中，父节点的值比每一个子节点的值都要大。在最小堆中，父节点的值比每一个子节点的值都要小。这就是所谓的“堆属性”，并且这个属性对堆中的每一个节点都成立。

使用场景：给定一个数组，其中的元素都是无序杂乱的，我们怎么对它进行堆排序呢？

四、链表：单向链表和双向链表，每一个节点都由数据+指针组成。链表的头结点不存储数据，但头节点指针指向第一个真正有数据的节点

链表优点：
插入删除速度快
内存利用率高，不会浪费内存
大小没有固定，拓展很灵活。

链表缺点：
不能随机查找，必须从第一个开始遍历，查找效率低

数组的优点：
随机访问性强，查找速度快

数组的缺点：
插入和删除效率低
可能浪费内存
内存空间要求高，必须有足够的连续内存空间。
数组大小固定，不能动态拓展