数组链表栈队列树图等数据结构的优缺点及应⽤场景
数组、字符串（Array & String）
数组的优点在于：
构建⾮常简单
能在 O(1) 的时间⾥根据数组的下标（index）查询某个元素
⽽数组的缺点在于：
构建时必须分配⼀段连续的空间
查询某个元素是否存在时需要遍历整个数组，耗费 O(n) 的时间（其中，n 是元素的个数）
删除和添加某个元素时，同样需要耗费 O(n) 的时间
链表（LinkedList）
单链表：链表中的每个元素实际上是⼀个单独的对象，⽽所有对象都通过每个元素中的引⽤字段链接在⼀起。
双链表：与单链表不同的是，双链表的每个结点中都含有两个引⽤字段。
由⼀系列节点组成的元素集合，每个节点包含数据域item和下⼀个节点的指针next，通过节点相互连接，最终串联成⼀个链表。
class Node(object):
def__init__(self,item):
self.item = item
< = None
a = [1,2,3]
b = Node(a)
c = Node(4)
< = c
item)
链表的优点如下：
链表能灵活地分配内存空间；
能在 O(1) 时间内删除或者添加元素，前提是该元素的前⼀个元素已知，当然也取决于是单链表还是双链表，在双链表中，如果已知该元素的后⼀个元素，同样可以在 O(1) 时间内删除或者添加该元素。
链表的缺点是：
不像数组能通过下标迅速读取元素，每次都要从链表头开始⼀个⼀个读取；
查询第 k 个元素需要 O(k) 时间。
应⽤场景：如果要解决的问题⾥⾯需要很多快速查询，链表可能并不适合；如果遇到的问题中，数据的元素个数不确定，⽽且需要经常进⾏数据的添加和删除，那么链表会⽐较合适。⽽如果数据元素⼤⼩确定，删除插⼊的操作并不多，那么数组可能更适合。
栈（Stack）
特点：栈的最⼤特点就是后进先出（LIFO）。对于栈中的数据来说，所有操作都是在栈的顶部完成的，只可以查看栈顶部的元素，只能够向栈的顶部压⼊数据，也只能从栈的顶部弹出数据。
实现：利⽤⼀个单链表来实现栈的数据结构。⽽且，因为我们都只针对栈顶元素进⾏操作，所以借⽤单链表的头就能让所有栈的操作在 O(1)的时间内完成。
应⽤场景：在解决某个问题的时候，只要求关⼼最近⼀次的操作，并且在操作完成了之后，需要向前查到更前⼀次的操作.
队列（Queue）
特点：和栈不同，队列的最⼤特点是先进先出（FIFO），就好像按顺序排队⼀样。对于队列的数据来说，我们只允许在队尾查看和添加数据，在队头查看和删除数据。
实现：可以借助双链表来实现队列。双链表的头指针允许在队头查看和删除数据，⽽双链表的尾指针允许我们在队尾查看和添加数据。
应⽤场景：直观来看，当我们需要按照⼀定的顺序来处理数据，⽽该数据的数据量在不断地变化的时候，则需要队列来帮助解题。在算法⾯试题当中，⼴度优先搜索（Breadth-First Search）是运⽤队列最多的地⽅。
双端队列（Deque）
特点：双端队列和普通队列最⼤的不同在于，它允许我们在队列的头尾两端都能在 O(1) 的时间内进⾏数据的查看、添加和删除。
实现：与队列相似，我们可以利⽤⼀个双链表实现双端队列。
应⽤场景：双端队列最常⽤的地⽅就是实现⼀个长度动态变化的窗⼝或者连续区间，⽽动态窗⼝这种数据结构在很多题⽬⾥都有运⽤。
树（Tree）
后端字符串转数组
树的结构⼗分直观，⽽树的很多概念定义都有⼀个相同的特点：递归，也就是说，⼀棵树要满⾜某种性质，往往要求每个节点都必须满⾜。例如，在定义⼀棵⼆叉搜索树时，每个节点也都必须是⼀棵⼆叉搜索树。
正因为树有这样的性质，⼤部分关于树的⾯试题都与递归有关，换句话说，⾯试官希望通过⼀道关于树的问题来考察你对于递归算法掌握的熟练程度。
树的形状
在⾯试中常考的树的形状有：普通⼆叉树、平衡⼆叉树、完全⼆叉树、⼆叉搜索树、四叉树（Quadtree）、多叉树（N-ary Tree）。
对于⼀些特殊的树，例如红⿊树（Red-Black Tree）、⾃平衡⼆叉搜索树（AVL Tree），⼀般在⾯试中不会被问到，除⾮你所涉及的研究领域跟它们相关或者你⼗分感兴趣，否则不需要特别着重准备。
关于树的考题，⽆⾮就是要考查树的遍历以及序列化（serialization)。
树的遍历
1. 前序遍历（Preorder Traversal）
⽅法：先访问根节点，然后访问左⼦树，最后访问右⼦树。在访问左、右⼦树的时候，同样，先访问⼦树的根节点，再访问⼦树根节点的左⼦树和右⼦树，这是⼀个不断递归的过程。
应⽤场景：运⽤最多的场合包括在树⾥进⾏搜索以及创建⼀棵新的树。
2. 中序遍历（Inorder Traversal）
⽅法：先访问左⼦树，然后访问根节点，最后访问右⼦树，在访问左、右⼦树的时候，同样，先访问⼦树的左边，再访问⼦树的根节点，最后再访问⼦树的右边。
应⽤场景：最常见的是⼆叉搜索树，由于⼆叉搜索树的性质就是左孩⼦⼩于根节点，根节点⼩于右孩⼦，对⼆叉搜索树进⾏中序遍历的时候，被访问到的节点⼤⼩是按顺序进⾏的。
3. 后序遍历（Postorder Traversal）
⽅法：先访问左⼦树，然后访问右⼦树，最后访问根节点。
应⽤场景：在对某个节点进⾏分析的时候，需要来⾃左⼦树和右⼦树的信息。收集信息的操作是从树的底部不断地往上进⾏，好⽐你在修剪⼀棵树的叶⼦，修剪的⽅法是从外⾯不断地往根部将叶⼦⼀⽚⽚地修剪掉。
注意：
掌握好这三种遍历的递归写法和⾮递归写法是⾮常重要的，懂得分析各种写法的时间复杂度和空间复杂度同样重要。
树这个数据结构都是最应该花时间学习的，既能证明你对递归有很好的认识，⼜能帮助你学习图论，尤其是⼆叉搜索树（BST）。
#⼆叉树
class BiTreeNode:
def__init__(self,data):
self.data = data
self.lchild = None
a = BiTreeNode('A')
b = BiTreeNode('B')
c = BiTreeNode('C')
d = BiTreeNode('D')
e = BiTreeNode('E')
f = BiTreeNode('F')
g = BiTreeNode('G')
e.lchild = a
c.lchild = b
root = e
#前序遍历
def pre_order(root):
if root:
print(root.data,end = ',')
pre_order(root.lchild)
pre_hild)
#中序遍历
def in_order(root):
if root:
in_order(root.lchild)
print(root.data,end =',')
in_hild)
#后序遍历
def post_order(root):
if root:
in_order(root.lchild)
in_hild)
print(root.data,end = ',')
in_order(root)
优先队列（Priority Queue）
特点
能保证每次取出的元素都是队列中优先级别最⾼的。优先级别可以是⾃定义的，例如，数据的数值越⼤，优先级越⾼；或者数据的数值越⼩，优先级越⾼。优先级别甚⾄可以通过各种复杂的计算得到。
应⽤场景
从⼀堆杂乱⽆章的数据当中按照⼀定的顺序（或者优先级）逐步地筛选出部分乃⾄全部的数据。
优先队列的本质是⼀个⼆叉堆结构。堆在英⽂⾥叫 Binary Heap，它是利⽤⼀个数组结构来实现的完全⼆叉树。换句话说，优先队列的本质是⼀个数组，数组⾥的每个元素既有可能是其他元素的⽗节点，也有可能是其他元素的⼦节点，⽽且，每个⽗节点只能有两个⼦节点，很像⼀棵⼆叉树的结构。
牢记下⾯优先队列有三个重要的性质。
数组⾥的第⼀个元素 array[0] 拥有最⾼的优先级别。
给定⼀个下标 i，那么对于元素 array[i] ⽽⾔：
1. 它的⽗节点所对应的元素下标是 (i-1)/2
2. 它的左孩⼦所对应的元素下标是 2×i + 1
3. 它的右孩⼦所对应的元素下标是 2×i + 2
数组⾥每个元素的优先级别都要⾼于它两个孩⼦的优先级别。
优先队列最基本的操作有两个。
向上筛选（sift up / bubble up）
当有新的数据加⼊到优先队列中，新的数据⾸先被放置在⼆叉堆的底部。
不断进⾏向上筛选的操作，即如果发现该数据的优先级别⽐⽗节点的优先级别还要⾼，那么就和⽗节点的元素相互交换，再接着往上进⾏⽐较，直到⽆法再继续交换为⽌。
向下筛选（sift down / bubble down）
当堆顶的元素被取出时，要更新堆顶的元素来作为下⼀次按照优先级顺序被取出的对象，需要将堆底部的元素放置到堆顶，然后不断地对它执⾏向下筛选的操作。
将该元素和它的两个孩⼦节点对⽐优先级，如果优先级最⾼的是其中⼀个孩⼦，就将该元素和那个孩⼦进⾏交换，然后反复进⾏下去，直到⽆法继续交换为⽌。
图（Graph）
阶（Order）、度：出度（Out-Degree）、⼊度（In-Degree）
树（Tree）、森林（Forest）、环（Loop）
有向图（Directed Graph）、⽆向图（Undirected Graph）、完全有向图、完全⽆向图
连通图（Connected Graph）、连通分量（Connected Component）
存储和表达⽅式：邻接矩阵（Adjacency Matrix）、邻接链表（Adjacency List）
常⽤图⽅法
图的存储和表达⽅式：邻接矩阵（Adjacency Matrix）、邻接链表（Adjacency List）
图的遍历：深度优先、⼴度优先
⼆部图的检测（Bipartite）、树的检测、环的检测：有向图、⽆向图
拓扑排序
联合-查算法（Union-Find）
最短路径：Dijkstra、Bellman-Ford
环的检测、⼆部图的检测、树的检测以及拓扑排序都是基于图的遍历，尤其是深度优先⽅式的遍历。⽽遍历可以在邻接矩阵或者邻接链表上进⾏，所以掌握好图的遍历是重中之重！因为它是所有其他图论算法的基础。
前缀树（Trie）
前缀树被⼴泛地运⽤在字典查当中，也被称为字典树。
举例：给定⼀系列字符串，这些字符串构成了⼀种字典，要求你在这个字典当中出所有以“ABC”开头
的字符串。
如果⽤前缀树头帮助对字典的存储进⾏优化，那么可以把搜索的时间复杂度下降为 O(M)，其中 M 表⽰字典⾥最长的那个单词的字符个数，在很多情况下，字典⾥的单词个数 N 是远远⼤于 M 的。因此，前缀树在这种场合中是⾮常⾼效的。
经典应⽤
⽹站上的搜索框会罗列出以搜索⽂字作为开头的相关搜索信息，这⾥运⽤了前缀树进⾏后端的快速检索。
汉字拼⾳输⼊法的联想输出功能也运⽤了前缀树。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。