栈与队列理论基础
代码随想录
stack:栈 后进先出
queue: 队列 先进先出
使用
Deque
【Java】Java双端队列Deque使用详解
菜鸟教程 Java Deque 接口
Java Deque 手册
Java Deque接口 使用方法(栈、队列、双端队列)
初始化
1 |
|
Why is ArrayDeque better than LinkedList
Deque接口可以实现 栈、队列、双端队列 的功能,虽然功能很丰富,但是使用时一定要格外小心。
接口的实现类
实现了这个接口的类有两个:ArrayDeque
、LinkedList
。ArrayDeque
不支持 null
,出现null
将会抛出异常
例如:@throws NullPointerException if the specified element is null and this deque does not permit null elements
使用情景:
频繁的插入、删除操作 或 未知的初始数量:LinkedList
频繁的随机访问操作:ArrayDeque
下表总结了上述 12 种方法:
第一个元素 (头部) | 最后一个元素 (尾部) | |||
抛出异常 | 特殊值 | 抛出异常 | 特殊值 | |
插入 | addFirst(e) | offerFirst(e) | addLast(e) | offerLast(e) |
删除 | removeFirst() | pollFirst() | removeLast() | pollLast() |
检查 | getFirst() | peekFirst() | getLast() | peekLast() |
做队列使用
Deque接口扩展(继承)了 Queue 接口。在将双端队列用作队列时,将得到 FIFO(先进先出)行为。将元素添加到双端队列的末尾,从双端队列的开头移除元素。从 Queue 接口继承的方法完全等效于 Deque 方法,如下表所示:
Queue方法 | 等效Deque方法 |
add(e) | addLast(e) |
offer(e) | offerLast(e) |
remove() | removeFirst() |
poll() | pollFirst() |
element() | getFirst() |
peek() | peekFirst() |
做栈使用
双端队列也可用作 LIFO(后进先出)堆栈。应优先使用此接口而不是遗留 Stack 类
。在将双端队列用作堆栈时,元素被推入双端队列的开头并从双端队列开头弹出。堆栈方法完全等效于 Deque 方法,如下表所示:
堆栈方法 | 等效Deque方法 |
push(e) | addFirst(e) |
pop() | removeFirst() |
peek() | peekFirst() |
PriorityQueue
Stack
【java】栈(Stack)的基本使用
菜鸟教程 Java Stack 类
PriorityQueue常用方法
1 |
|
注:Java堆栈
Stack类
已经过时,Java官方推荐使用Deque替代Stack使用。Deque堆栈操作方法:push()、pop()、peek()。
JAVA 栈,为什么要使用Deque,而不推荐使用Stack,Deque中ArrayDeque与LinkedList的区别,Deque方法详解
Queue
【java】队列(Queue)的基本使用
【Java】Java队列Queue使用详解
菜鸟教程 Java 实例 - 队列(Queue)用法
压入元素(添加):add()、offer()
相同:未超出容量,从队尾压入元素,返回压入的那个元素。
区别:在超出容量时,add()方法会对抛出异常,offer()返回false
弹出元素(删除):remove()、poll()
相同:容量大于0的时候,删除并返回队头被删除的那个元素。
区别:在容量为0的时候,remove()会抛出异常,poll()返回false
获取队头元素(不删除):element()、peek()
相同:容量大于0的时候,都返回队头元素。但是不删除。
区别:容量为0的时候,element()会抛出异常,peek()返回null。
抛出异常 | 返回特殊值 | 队列可能阻塞 | |
插入 | add(e) | offer(e) | put(e) |
删除 | remove() | poll() | take() |
检查 | element() | peek() | – |
1 |
|