栈、队列、双端队列、优先队列
2020-03-08 本文已影响0人
云莉6
Stack(栈)
-
First in - Last out(先进后出)
-
Last in - First out (后进先出)
-
添加、删除皆为 O(1)
![](https://img.haomeiwen.com/i4457287/604ea4ee4a1fedab.png)
Queue(队列)
-
First in - First out(先进先出)
-
Last in - Last out(后进后出)
-
添加、删除皆为 O(1)
![](https://img.haomeiwen.com/i4457287/6492fc130d25e34f.png)
Deque: Double-End Queue(双端队列)
-
两端可以进出的 Queue
-
添加、删除皆为 O(1) 操作
![](https://img.haomeiwen.com/i4457287/e6a472bdb0a3f8b8.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
复杂度分析:
![](https://img.haomeiwen.com/i4457287/87248c9937571166.png)