上一篇文章中的4个数据结构相信大家都不陌生，下面简单介绍一下。接下来，我们将详细介绍以下6种数据结构及其各自的使用场景，并会列举更多的例子。5、deque的基本用法Deque是一个双端队列，在链表的基础上优化了链表两端的增删数据操作。基本用法：fromcollectionsimportdequeIn[3]:d=deque([3,2,4,0])In[4]:d.popleft()#取出左边的元素，O(1)时间复杂度Out[4]：3In[5]:d.appendleft(3)#向左添加元素，O(1)时间复杂度In[6]:dOut[6]:deque([3,2,4,0])使用场景：在列表左侧添加和删除元素的时间复杂度是O(n)，所以在Python中模拟队列时不要使用list。相反，使用deque双端队列非常适合频繁操作链表两端的场景。然而增强版的双端队列牺牲了空间复杂度，所以嵌套的双端队列必须谨慎权衡：In[9]:sys.getsizeof(deque())Out[9]:640In[10]:sys.getsizeof(list())Out[10]:72实现原理：CPython实现双端队列使用默认长度为64的数组，每次从左边移除一个元素，leftindex加1，超过64则释放原来的内存块，并且然后重新申请64位数组，使用双端链表块来管理内存块。6、计数器基本用法：计数器是继承自dict的一种数据结构，用于统计元素个数，也称为bag或multiset。基本用法：fromcollectionsimportCounterIn[14]:c=Counter([1,3,2,3,4,2,2])#统计每个元素出现的次数In[17]:cOut[17]:Counter({1:1,3:2,2:3,4:1})#另外，还可以统计最常见的项#比如统计第1个最常见的项，返回元素及其次数的元组在[16]:c.most_common(1)Out[16]:[(2,3)]use场景：基本dict可以解决的问题不要用Counter，但是如果遇到统计元素频率的场景出现了，不要用dict自己实现，果断选择Counter。需要注意的是，Counter统计的元素要求是可哈希的（Hashable），换句话说统计列表出现的次数是不可行的，但是列表可以转换成元组，是不是可以哈希？实现原理：Counter实现基于dict，将元素存储在key上，出现次数为value。7、OrderedDict的基本用法继承自dict，可以保证key取出顺序的数据结构。基本用法：In[25]:fromcollectionsimportOrderedDictIn[26]:od=OrderedDict({'c':3,'a':1,'b':2})In[27]:fork,vinod.items():...:print(k,v)...:c3a1b2使用场景：基本的dict无法保证顺序，key映射为哈萨克斯坦Hash值，而这个值并没有按顺序存储在hash表中。所以如果要保证字典的键是有序的，就需要使用OrderedDict。实现原理：你一定很好奇OrderedDict是如何保证key的顺序的。查看cpython，发现它维护了一个双向链表self.__root，维护了keys的顺序。由于使用了双向链表，细心的读者可能会有疑问：删除键值对如何保证O(1)时间完成？CPython用空间换取时间，内部维护了一个self.__map字典，key为key，value指向一个双向链表节点的链接。这样，在删除键值对时，通过__map在O(1)中找到链接，然后在O(1)中从双向链表__root中移除。8、heapq的基本用法一种基于链表优化的数据结构：堆队列，又称优先队列。堆队列的特点是最小的元素总是在根节点：heap[0]基本用法：importheapqIn[41]:a=[3,1,4,5,2,1]In[42]：heapq.heapify(a)#为a建堆，建堆后完成a的原地排序In[43]:a[0]#a[0]必须是In[44]中的最小元素：aOut[44]:[1,1,3,5,2,4]In[46]:heapq.nlargest(3,a)#a的前3个最大元素Out[46]:[5,4,3]In[47]:heapq.nsmallest(3,a)#a的前三个最小元素Out[47]:[1,1,2]使用场景：如果要统计list中前几个最小（大）的元素，heapq使用起来非常方便，同时它还提供了将多个排序后的小列表合并为一个大列表的功能。基本原理：堆是一棵二叉树，每个父节点的值只会小于或大于所有子节点（值）。原理和堆排序很相似。9.defaultdict的基本用法Defaultdict是一个带有默认工厂的字典。不太了解设计模式的读者可能会对工厂这个词感到困惑。准确的说，工厂的全称是objectfactory。下面体验一下它的基本用法。基本字典键的值没有默认数据类型。如果值为列表，则必须手动创建：words=['book','nice','great','book']d={}fori,wordinenumerate(words):ifwordind:d[word]。append(i)else:d[word]=[i]#显示创建一个列表但是使用defaultdict:fromcollectionsimportdefaultdictd=defaultdict(list)#创建一个字典，其字典值默认为listfori,wordinenumerate(words):d[word]=i省去了一层if逻辑判断，代码更清晰。上面defaultdict(list)这行代码创建了一个默认值为list的字典，还可以构造defaultdict(set)、defaultdict(dict)等，这种模式是一个对象工厂，可以在里面制造各种对象factory:list,set,dict...使用场景：上面已经说的很清楚了，适用于key的值必须指定一个默认值的场景，比如key的值为list,set,dict等实现原理：基本原理是调用工厂函数提供缺失key的值。稍后将详细讨论设计模式的主题。10.ChainMap的基本使用如果你想将多个dict合并为一个大dict，那么ChainMap将是你的选择，它的便利性体现在同步变化上。具体看例子：In[55]:fromcollectionsimportChainMapIn[56]:d1={'a':1,'c':3,'b':2}In[57]:d2={'d':1,'e':5}In[58]:dm=ChainMap(d1,d2)In[59]:dmOut[59]:ChainMap({'a':1,'c':3,'b':2},{'d':1,'e':5})返回ChainMap后的大dict视图，如果修改对应的键值对，原来的小dict也会发生变化：In[86]:dm.maps#返回一个字典listOut[86]:[{'a':2,'c':3,'b':2,'d':10},{'d':1,'e':5}]In[87]:dm.maps[0]['d']=20#修改第一个dict等于'd'的key为20In[88]:dmOut[88]:ChainMap({'a':2,'c':3,'b':2,'d':20},{'d':1,'e':5})In[89]:d1#的key值原来的smalldict变成了20Out[89]:{'a':2,'c':3,'b':2,'d':20}使用场景：具体的使用场景是我们有多个字典或者映射并且想把它们合并成一个映射，可能有读者会说可以用update来合并。这样做的问题是创建了一个新的内存结构。除了浪费空间，还有一个缺点就是我们对新字典的修改不会同步到原来的字典。实现原理：通过map可以看出ChainMap是将多个小dict组合成一个list，其实就是这样实现的。内部维护了一个lis的实例，它的元素是小的字典。综上所述，以上就是Python中常用的10种数据结构。共有4种常用的基本结构和6种根据其优化适应特定场景的结构。我将他们的学习总结为三个步骤。
