重要的栈

python里面最常用的栈实现是依靠列表来实现的
列表可以用pop和append来实现出栈入栈

collections.deque实现了快速的双端队列,双端队列对两端的节点进行操作效率很高,对于删除和插入操作执行性能出色,操作也是相当简单。
LifoQueue为并行计算提供,也就是防止多个进程抢占,一般的情🆒况下没有同步锁的必要的时候尽量使用简单的list或者双端队列。
List 是python内置的简易栈
一般来说双向队列是实现栈的最佳选择

队列的实现

双端队列deque是实现队列的不错选择
Queue.queue能够为并行计算提供具有语义锁的队列实现
.get_nowait()是能够对并行队列施加语义锁的
multiprocessing.Queue共享作业队列,实现进程上的并行

优先队列

优先队列是一个容器数据结构,使用具有全序关系的键,来管理元素,以便访问键值最大或者最小的元素。

  • 列表的使用是实现优先队列很麻烦的操作,除非元素很少,同时在插入元素以及重新排序上面队列的时间复杂度很差。
  • heapq是基于普通列表实现的二叉堆,只提供最小堆实现,也就是增序排列
  • queue.PriorityQueue美丽的优先级队列,内部使用heapq进行实现,时空复杂度不变,但是这个能提供很好的语义锁。但是可能会带来额外の内存开销