从数据结构角度来看:
栈 和 队列 都是一种特殊的线性结构,只是对 插入 / 删除 元素的方式做了限制
- 栈:先进后出(push / pop / peek 的时间复杂度都是 O(1))
- 队列:先进先出(add / remove / element 的时间复杂度都是 O(1))
栈 和 队列 继承关系图:(方法)
栈 其实是 一种特殊的 队列
1、队列:
队列:先进先出(FIFO)
有两个接口:
- Queue:队列
- Deque:双向队列
(1)Queue:队列
常见方法:
返回类型 |
方法 |
解释 |
boolean |
add(E e) |
将指定元素插入到队列中;若违反容量限制,则抛出异常 |
E |
element() |
检索,但不删除,这个队列的头 |
E |
remove() |
检索,并删除,此队列的头 |
boolean |
offer(E e) |
将指定的元素插入到此队列中 |
E |
peek() |
检索,但不删除,此队列的头;如果此队列为空,则返回 null |
E |
poll() |
检索,并删除,此队列的头;如果此队列为空,则返回 null |
上面三种方法 和 下面三种方法的作用基本上一致的,只是遇到错误时行为不同,上面三种是抛出异常,而下面三种是返回 null
(2)Deque:双向队列
Deque:双向队列的特殊方法:
因为 Deque 继承了 Queue,所以 Queue 中的方法,Deque中也有,那么默认情况下,会选择哪种方法 ?
2、栈:
栈 :先进后出(FILO)
结构相当于 把队列给竖了过来
- 进去的顺序 : ABCDE
- 出来的顺序 : EDCBA
1、常用方法:实现 Deqeue 接口(其实就是 Deque 方法的变形)
peek : 查看栈顶元素
2、Java 早期还有一个专门的栈类 : Stack
返回类型 |
方法 |
解释 |
boolean |
empty() |
判断 栈 是否为空 |
E |
push(E) |
在栈顶添加元素 |
E |
peek() |
查看栈顶元素,但不删除 |
E |
pop() |
删除栈顶元素,并返回该元素 |
int |
search(Object o) |
找到 o 对象 第一次 出现的位置 |