栈和队列的基本理论
栈和队列都是一个表,任何实现表的方式都能够实现栈和表
栈和队列的操作都是常数时间操作
栈是先进后出,添加元素也叫做压栈、进栈等,删除元素叫做弹栈、出栈等
队列是后进后出,从队尾添加元素也叫做入队,从队头删除元素也叫做出队
Java中一般优先使用双端队列Deque<E>实现栈
优先队列(堆)使用PriorityQueue<E>实现
Java中栈和队列的常用集合结构图
栈的实现方式
- 使用Stack<E>类实现,一般使用的少
- 使用Deque<E>接口,ArrayDeque<E>或者LinkedList<E>实现,常用的实现方式
队列的实现方式
使用Queue<E>接口,ArrayDeque<E>或者LinkedList<E>实现,一般队列
使用Deque<E>接口,ArrayDeque<E>或者LinkedList<E>实现,双端队列
使用Queue<E>接口,PriorityQueue<E>实现,优先队列(堆)
栈的经典应用场景
1、平衡符号
- 用于检测是否每件事情都能成对出现
- 对应的LeetCode的相关题目:
- 这种两两匹配、成对消除的题目可以优先考虑是否可以使用栈
2、后缀表达式
- 后缀表达式又叫逆波兰表达式,是适用于计算机的一种计算方式
- 之所以称为后缀表达式,是因为使用二叉树遍历的时候使用的是后序遍历,符号位出现再两个子树的后面
- 对应的LeetCode题目:
- 150. 逆波兰表达式求值 力扣
3、用栈模拟递归
- 使用栈模拟递归实现二叉树的前、中、后序遍历
- 对应的LeetCode题目
队列的应用场景
1、单调队列
其实我觉得严格意义上来说优先队列才是真正的单调队列,优先队列在排序后,最后所有的元素都在队列中按照某种排序单调递增或者单调递减
单调队列通俗点说就是保证对头一直是最大值或者是最小值。
保证队头是最大值,后面添加进来的值也要做到单调递减,这样就做到了单调递减队列
保证队头是最小值,后面添加进来的值也要做到单调递增,这样就做到了单调递增队列
这种数据结构是没有的,需要我们自定义类进行实现
所以这种数据结构和算法适合求区间中的最大值或者最小值
它不同于优先队列的是:
优先队列加进去后就进行排序,进入队列之后才知道要待在哪里
单调队列是在加入进去之前就判断,进去之前就谋划前面是不是有比自己大的或者比自己小的
比优先队列更适合在不断变换的区间中进行排序寻找top
对应LeetCode的题目
239.滑动窗口最大值 力扣
2、优先队列
- 优先队列(PriorityQueue<E>集合)的底层原理是堆,堆的底层原理是二叉树,根据排序不同,堆又分队大顶堆和小顶堆
当我们调用offer()方法将一个对象存放到PriorityQueue中时,这个对象会在排序后放入队列。默认的排序方式是对象在队列中的自然排序,但是我们可以通过自己的Comparator来修改排序方式
PriorityQueue默认是最小的值优先级最高,也就是小顶堆
PriorityQueue底层是数组实现 transient Object[] queue
适用于top K 算法
对应LeetCode中的题目:
347.前k个高频元素 力扣