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:
-
高性能的 container 库: https://docs.python.org/2/library/collections.html
复杂度分析：
image.png
网友评论