各种数据结构的具体实现

Queue(队列)

Queue实际上是一个支持泛型的接口
Queue 在 java 中已经有了具体实现

Queue<Integer> queue = new LinkedList<>(); // 链表实现
Queue<Integer> queue1 = new PriorityQueue<>(); // 优先队列实现

以下是基本操作：

Summary of Queue methods // 方法总结
Throws exception Returns special value
Insert  add(e)      offer(e)
Remove  remove()    poll()
Examine element()   peek()

1. add(E e) / offer（E e）的区别

boolean add(E e) boolean offer(E e) — 入队
二者的区别只有：对于存在容量限制的队列，offer 和 add 存在不同。add 会抛出异常， 但是 offer 会返回 false

2. E remove() / E poll() 的区别

E remove() / E poll() 删除头部元素 — 出队
Returns: the head of this queue
二者区别：
对于 remove( ) 会 throw NoSuchElementException – if this queue is empty
对于 poll（）会 返回 Null

3. E element() / E peek();

E element() / E peek() — 返回栈顶元素
Returns: the head of this queue
对于 element（）会 throw NoSuchElementException – if this queue is empty
对于 peek() 会返回 null

PriorityQueue（优先队列）

队列中不能存在null

• 源码中的注释：

基于优先级堆的无限制优先级队列。优先队列的元素根据其自然顺序或在队列构建时提供的比较器进行排序。

An unbounded priority queue based on a priority heap.
The elements of the priority queue are ordered according to their natural ordering, 
or by a Comparator provided at queue construction time, 
depending on which constructor is used

类的定义 ：public class PriorityQueue extends AbstractQueue
private static final int DEFAULT_INITIAL_CAPACITY = 11; 初始定义capacity 为 11
同时内部实现了 siftDown 以及 heapify ，siftUp方法等主要方法；
内部存在 grow 方法来改变队列大小

Deque(双端队列)

Deque 实际上是一个继承自 Queue 的接口，需要实现接口内部方法后才能使用
Java也实现了一个Deque
Deque queue2 = new ArrayDeque<>(); 使用 Array 实现

主要方法：

addLast(E e) / addFirst(E e) ——- 将元素添加，若元素为null，抛出 NullPointerException
offerLast(E e) / offerFirst(E e)
removeFirst() / removeLast() —- 删除元素
pollFirst() / pollLast() —— 删除元素
getFirst() / getLast() —— 获取元素
peekFirst() / peekLast() —— 获取元素
而其他的一些队列的基本方法直接可以用上面进行实现，offer实际上是通过add实现，以此类推

Stack（栈）后入先出

Stack<Integer> stack = new Stack<>(); // 实现一个栈

public class Stack extends Vector 实现Vector接口 // 使用Array实现
具体方法：

// 将元素压入栈中，然后返回压入元素
E push(E item){
    addElement(item);
  return item
}

// 将栈顶元素弹出，若为空则 throw EmptyStackException 
E pop(){
    E obj;
  int len = size();
  obj = peek();
  removeElementAt(len-1); // 删除最后的元素
  return obj;
}

// 查看栈顶元素,但是不删除
E peek(){
    int len = size();
  if(len == 0)
      throw new EmptyStackException();
  return elementAt(len-1);
}

// 查看栈中是否存在元素,返回其索引
int search(Object o){
    int i = lastIndexOf(o); // 查找数组中最后出现的索引，在栈中就是第一个出现的位置。
  if(i >= 0){
          return size() - i;
  }
  return -1;
}