python内置高级数据结构

写作目的

在编程过程，特别是线上编程的过程中，总会需要用到很多高级的数据结构，但是python中的一些高级数据结构并没有那么的“明显”，这里梳理一下。

栈

栈在python中比较好实现，直接用List数据结构就可以代替。add方法用append代替，有内置的pop()方法，时间复杂度O(1),至于peek()方法可以直接用索引-1代替。

myStack=[]
myStack.append(1)
myStack.append(2)
myStack.append(3)
myStack
Out[8]: [1, 2, 3]
myStack.pop()
Out[9]: 3

队列

一般的队列可能大部分人都跟我的使用差不多，还是用list来实现，get()方法用pop(0)代替。但是我以前的文章中应该已经说过，pop(0)的时间复杂度比较的高。 这里可以引用python自己的队列结构。

import queue 
myQueue=queue.Queue()
myQueue.put(2)
myQueue.put(3)
myQueue.put(1)
myQueue.put(5)
myQueue.get()
Out[16]: 2
myQueue.get()
Out[17]: 3

没有去深究get()的实现方法，但是这个内置，至少很香，应该比用list维护要香。

优先队列

不但可以从小到大排序，还可以取出优先的前k个树（越小越优先），而且算法复杂度是logn级别的，其实自己也可以用二叉堆进行实现，但是调用现成的，而且是内置的，肯定更舒服。

import queue
#优先队列
priQue=queue.PriorityQueue()
priQue.put([3,"赵"])
print(priQue.queue)
priQue.put([2,"钱"])
print(priQue.queue)
priQue.put([1,"孙"])
print(priQue.queue)
priQue.put([7,"李"])
print(priQue.queue)
priQue.put([5,"周"])
print(priQue.queue)
##取数据
# print(priQue.get())
# print(priQue.get())
# print(priQue.get())
# print(priQue.get())
print(priQue.get())

双端队列

左右都可追加，左右都可弹出，collection是一个不错的包，改天好好研究下。

import collections
   ...: dque=collections.deque()
   ...: dque.append(2)
   ...: dque.append(3)
   ...: dque.append(4)
   ...: dque.append(5)
   ...: dque.append(6)
   ...: dque.appendleft(7)
   ...: print(dque.popleft())
   ...: print(dque.pop())
7
6

小顶堆

堆就是个完全二叉树，跟优先队列是一样的，不同的是这里每次都可以窥探到二叉堆的顶元素

import heapq#堆结构，初始化为小顶堆
   ...: heap=[3,4,1,52,3]
   ...: heapq.heapify(heap)
print(heap)
[1, 3, 3, 52, 4]
heapq.heappush(heap,4)
print(heap)
[1, 3, 3, 52, 4, 4]
heapq.heappush(heap,2)
print(heap)
[1, 3, 2, 52, 4, 4, 3]
heapq.heappop(heap)
Out[52]: 1
print(heap)
[2, 3, 3, 52, 4, 4]