栈 队列 双端队列 优先队列 基础知识
• Stack:先入后出 first in last out 简写FILO 添加删除 O(1) 查询 O(n)
• 栈是无序的，如果想要加速可以加一个哈希表
• Queue: 先进先出first in first out简写 FIFO 添加删除 O(1) 查询 O(n)
• Double-End-Queue: Deque 双端队列，头和尾都可以进出
Java 的Stack 类 extends Vector,但是在工程中 如果要使用Stack，直接使用Deque类即可，效率更高
Deque<Integer> stack = new ArrayDeque<Integer>();
Java 的 interface Queue类 extends Collection
优先队列（Priority Queue）
• 插入操作是 O(1)
• 取出操作是 O(logN) 按照元素的优先级取出,底层的数据结构是较多样和复杂，可以是heap堆
• 可能是二叉树堆/Fibonacci堆 或其他堆
• 可能是bst binary search tree 二叉搜索树/平衡二叉树（如红黑树）AVL（二叉查找树）来实现
• treap 树堆 二叉搜索树的一种
网友评论