Stack
java中的后入先出的栈结构,继承自Vector因此是一个线程安全的容器

类方法
stack的方法非常简单,只有下面五种方法
- push:调用 Vector的addElement方法,将新元素 obj 插入到 Vector 维护的 elementData[] 数组中
- elementData[elementCount++] = obj;
- pop:调用 Vector的 removeElementAt(len - 1),将 Vector最后的一个弹出
- peek:调用 Vector 的 elementAt(len - 1),返回 Vector 最后一个元素
- empty:return size() == 0;
- search:返回该元素在栈中的索引
- 调用 Vector的 lastIndexOf(o) 查询元素在数组的索引位置,返回 size() - 索引位置
LinkedList
LinkedList是典型的双端队列的实现类, 实现了Deque双端队列的接口,而Deque继承自Queue接口拥有先入先出的功能。

Queue接口
Queue添加元素的实现
- add 调用 LinkedList中的 linkLast 方法将指定元素的添加到链表的尾部
- offer 调用 add 方法
Queue删除元素的实现
- poll 调用 unlinkFirst(f) 将链表的首节点移除
- remove 调用removeFirst 再调用unlinkFirst(f) 将链表的首节点移除
Queue获取队列顶部元素的实现
- peek 返回
final Node<E> f = first;
Deque接口
Deque接口要稍微复杂一些,为了便于理解,我们稍微整理一下方法,淦,这么多看的眼花缭乱,但是细品可以看出一些规律

双端队列既拥有栈的后入先出的特性,又有队列先入先出的特性,因此我们可以将这些方法稍微分类一下,其实很多方法是一样。
- push == linkFirst
- offerFirst == addFirst
- addFirst == linkFirst
- add == linkLast
- offer == linkLast
- addLast == linkLast
- offerLast == addLast
- pop == removeFirst
- remove == removeFirst
- removeFirst == unlinkFirst 空时抛 NoSuchElementException 异常
- poll == unlinkFirst 空时返回null
- pollFirst == unlinkFirst 空时返回null
- peek 返回
final Node<E> f = first;
- peekFirst 返回 first
- getFirst 返回 first 空时抛 NoSuchElementException 异常
- peekLast 返回
final Node<E> l = last;
- getLast 返回 last 空时抛 NoSuchElementException 异常
- pollLast == unlinkLast 空时返回null
- removeLast == unlinkLast 空时抛 NoSuchElementException 异常
字数:1356
发布于 1 年前