【学习笔记】栈、队列、双端队列、优先队列

1. Stack 栈

先进后出（FILO），或者叫后进先出(LIFO)

操作	复杂度
添加	O(1)
删除	O(1)
查询	O(n)

P.S: 因为元素是无序的，查询的时候几乎每个元素都要访问一次，所以查询的时间复杂度是 O(n)的

2. Queue 队列

先进先出（FIFO) ， 后进后出（LILO)

操作	复杂度
添加	O(1)
删除	O(1)
查询	O(n)

3. Deque 双端队列

官方文档
deque 是 Double-End Queue 的简写
“头和尾都可以进行元素的出和入”

操作	复杂度
添加	O(1)
删除	O(1)
查询	O(n)

4. Priority Queue 优先队列

在 Python 里面调用是 heapq
这里可能是因为 python 的优先队列是 heap实现的
官方文档

from collections import heapq 

操作	复杂度
插入	O(1)
取出	O(log(n))

P.S:对于优先队列来说，虽然时间复杂度变高了，但是优先队列的顺序不再是先入先出/后入后出了