栈、队列、双端队列、优先队列

Stack（栈）

• First in - Last out（先进后出）

• Last in - First out （后进先出）

• 添加、删除皆为 O(1)

image.png

Queue（队列）

• First in - First out（先进先出）

• Last in - Last out（后进后出）

• 添加、删除皆为 O(1)

image.png

Deque: Double-End Queue（双端队列）

• 两端可以进出的 Queue

• 添加、删除皆为 O(1) 操作

image.png

Priority Queue（优先队列）

• 插入操作：O(1)

• 取出操作：O(logN) - 按照元素的优先级取出

• 底层具体实现的数据结构较为多样和复杂：heap（堆）、bst（二叉搜索树）、treap（树堆）

• java 中的 PriorityQueue: https://docs.oracle.com/javase/10/docs/api/java/util/PriorityQueue.html**

如何查询接口信息？

• google Java + Deque or Python + Deque 查看官方文档或者源码实现

Java:

• Stack: http://developer.classpath.org/doc/java/util/Stack-source.html

• Queue: https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html

• Priority Queue: http://developer.classpath.org/doc/java/util/PriorityQueue-source.html

Python:

• heapq: https://docs.python.org/2/library/heapq.html

• 高性能的 container 库: https://docs.python.org/2/library/collections.html

复杂度分析：

image.png