MyDeque;源码分析；Hashmap

class MyDeque {
int capacity=0;
int size=0;
Node first;
Node last;
public MyDeque(int k) {
capacity=k;
}

/**
 * Adds an item at the front of Deque. Return true if the operation is successful.
 */
public boolean insertFront(int value) {
    if(size>=capacity){
        return false;
    }else{
        Node<Integer>newNode=new Node<>(null,value,first);
        if(first==null){
            first=newNode;
            last=newNode;
        }else{
            first.pre=newNode;
            newNode.next=first;
            first=newNode;
        }
        size++;
        return true;
    }
}

/**
 * Adds an item at the rear of Deque. Return true if the operation is successful.
 */
public boolean insertLast(int value) {
    if(size>=capacity){
        return false;
    }else{
        Node node=new Node(last,value,null);
        if(last==null){
            last=node;
            first=node;
        }else{
            last.next=node;
            node.pre=last;
            last=node;
        }
        size++;
        return true;
    }
}
/**
 * Deletes an item from the front of Deque. Return true if the operation is successful.
 */
public boolean deleteFront() {
    if(size==0)return false;
    else if(size==1){
        first=null;
        last=null;
        size--;
        return true;
    }
    else{

            first=first.next;
            first.pre=null;
        size--;
        return true;
    }
}

/**
 * Deletes an item from the rear of Deque. Return true if the operation is successful.
 */
public boolean deleteLast() {
    if(size==0)return false;
    else if(size==1){
        last=null;
        first=null;
        size--;
        return true;
    }
    else{

            last=last.pre;
            last.next=null;
        size--;
        return true;
    }
}

/**
 * Get the front item from the deque.
 */
public int getFront() {
    if(first==null)return -1;
    else return first.data;
}

/**
 * Get the last item from the deque.
 */
public int getRear() {
    if(last==null)return -1;
    else return last.data;
}

/**
 * Checks whether the circular deque is empty or not.
 */
public boolean isEmpty() {
    if(size==0)return true;
    else return false;
}

/**
 * Checks whether the circular deque is full or not.
 */
public boolean isFull() {
    if(size==capacity)return true;
    else return false;
}

class Node<E>{
    E data;
    Node<E> pre;
    Node<E> next;
    public Node(Node<E> pre,E e,Node<E> next){
        data=e;
        this.pre=pre;
        this.next=next;
    }
}

}

源码分析：

Queue: interface
boolean add(E e): does not permit null elements
boolean offer(E e):don't permit null e
E element()\peek():don't remove
peek()
remove()
poll()

PriorityQueue:class,based on a priority heap;does't permit null element;not synchronized(instead,use PriorityBlockingQueue)、use Object[]queque
enque:O(log(n))
deque:O(log(n))
remove:O(n)
contains:O(n)
peek\element\size:O(1)
//扩容规则
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}
//添加元素规则
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);
size = i + 1;
if (i == 0)
queue[0] = e;
else
siftUp(i, e);
return true;
}
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
//删除规则
public boolean remove(Object o) {
int i = indexOf(o);
if (i == -1)
return false;
else {
removeAt(i);
return true;
}
}

Deque:interface（double ended queque)
used to be LIFO and FIFO
void :addFirst(E e) addLast(E e)
boolean:offerFirst offerLast
E:removeFirst removeLast：
E poll()：Retrieves and removes the head of the queue represented by this deque or returns if this deque is empty.

E pollFirst()： Retrieves and removes the first element of this deque,

• or returns {@code null} if this deque is empty.

pollLast()：Retrieves and removes the last element of this deque,

• or returns {@code null} if this deque is empty
  HashMap:Hashmap 是基于数组\链表和红黑树实现的哈希表，采用数组作为健值对的容器。数组中存放的是 单链表的头节点，当发生hash碰撞时，采用的是链表方式解决冲突，将发生冲突的元素放到链表上去。当链表上的数量大于 TREEIFY_THRESHOLD = 8 时会转化为红黑树以提高效率。
  putVal: 一个Node<k,v>[] tab数组，一个Node<k,v>p节点；如果p instanceof TreeNode，putTreeVal；其他情况p.next=newNode()
  getNode:first instanceof TreeNode-->first.getTreeNode;e.next!=null,return e;