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 异常