跳表查询的时间复杂度分析
n/2、n/4、n/8、第k级索引节点的个数就是n/(2^k)
假设索引有h级，最高级的索引有2个节点。n/(2^h) = 2,从而求得h = log2(n) - 1
跳表:
原始链表大小为n，每2个结点抽1个，每层索引的节点数： n/2，n/4，n/8，...，8，4，2 原始链表大小为n，每3个结点抽1个，每层索引的节点数： n/3，n/9，n/27，...，9，3，1 空间复杂度是O(n)
跳表查询的时间复杂度分析 第k级索引 第k - 1 级索引
索引的高度：logn，每层索引遍历的节点个数：3 在跳表中查询任意数据的时间复杂度就是O(logn)
解决问题 升级维度 空间换时间
LRU最近最少使用 基于多链表来实现的。
可以通过HashMap + 双向链表实现。 HashMap保证通过key访问数据的时间为O(1)， 双向链表则按照访问时间的顺序一次穿过每个数据。 之所以选择双向链表而不是单链表，是为了可以从中间任意节点修改链表结构，而不必从头结点开始遍历。
Stack 先进后出 添加删除数据时间复杂度是O(1) 查询数据时间复杂度是O(n) 1 boolean empty() 测试堆栈是否为空。 2 Object peek( ) 查看堆栈顶部的对象，但不从堆栈中移除它。 3 Object pop( ) 移除堆栈顶部的对象，并作为此函数的值返回该对象。 4 Object push(Object element) 把项压入堆栈顶部。 5 int search(Object element) 返回对象在堆栈中的位置，以 1 为基数。
Queue 先进先出 添加删除数据时间复杂度是O(1) 查询数据时间复杂度是O(n) offer，add 区别： 一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，多出的项就会被拒绝。 这时新的 offer 方法就可以起作用了。它不是对调用 add() 方法抛出一个 unchecked 异常，而只是得到由 offer() 返回的 false。 poll，remove 区别： remove() 和 poll() 方法都是从队列中删除第一个元素。remove() 的行为与 Collection 接口的版本相似， 但是新的 poll() 方法在用空集合调用时不是抛出异常，只是返回 null。因此新的方法更适合容易出现异常条件的情况。 peek，element区别： element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似，在队列为空时， element() 抛出一个异常，而 peek() 返回 null。
Deque 两端可以进出的Queue. Deque - double ended queue 添加删除数据时间复杂度是O(1) 查询数据时间复杂度是O(n) boolean add(E e) 将指定元素插入此双端队列所表示的队列（换句话说，此双端队列的尾部），如果可以直接这样做而不违反容量限制的话；如果成功，则返回 true，如果当前没有可用空间，则抛出 IllegalStateException。 void addFirst(E e) 将指定元素插入此双端队列的开头（如果可以直接这样做而不违反容量限制）。 void addLast(E e) 将指定元素插入此双端队列的末尾（如果可以直接这样做而不违反容量限制）。 boolean contains(Object o) 如果此双端队列包含指定元素，则返回 true。 Iterator descendingIterator() 返回以逆向顺序在此双端队列的元素上进行迭代的迭代器。 E element() 获取，但不移除此双端队列所表示的队列的头部（换句话说，此双端队列的第一个元素）。 E getFirst() 获取，但不移除此双端队列的第一个元素。 E getLast() 获取，但不移除此双端队列的最后一个元素。 Iterator iterator() 返回以恰当顺序在此双端队列的元素上进行迭代的迭代器。 boolean offer(E e) 将指定元素插入此双端队列所表示的队列（换句话说，此双端队列的尾部），如果可以直接这样做而不违反容量限制的话；如果成功，则返回 true，如果当前没有可用的空间，则返回 false。 boolean offerFirst(E e) 在不违反容量限制的情况下，将指定的元素插入此双端队列的开头。 boolean offerLast(E e) 在不违反容量限制的情况下，将指定的元素插入此双端队列的末尾。 E peek() 获取，但不移除此双端队列所表示的队列的头部（换句话说，此双端队列的第一个元素）；如果此双端队列为空，则返回 null。 E peekFirst() 获取，但不移除此双端队列的第一个元素；如果此双端队列为空，则返回 null。 E peekLast() 获取，但不移除此双端队列的最后一个元素；如果此双端队列为空，则返回 null。 E poll() 获取并移除此双端队列所表示的队列的头部（换句话说，此双端队列的第一个元素）；如果此双端队列为空，则返回 null。 E pollFirst() 获取并移除此双端队列的第一个元素；如果此双端队列为空，则返回 null。 E pollLast() 获取并移除此双端队列的最后一个元素；如果此双端队列为空，则返回 null。 E pop() 从此双端队列所表示的堆栈中弹出一个元素。 void push(E e) 将一个元素推入此双端队列所表示的堆栈（换句话说，此双端队列的头部），如果可以直接这样做而不违反容量限制的话；如果成功，则返回 true，如果当前没有可用空间，则抛出 IllegalStateException。 E remove() 获取并移除此双端队列所表示的队列的头部（换句话说，此双端队列的第一个元素）。 boolean remove(Object o) 从此双端队列中移除第一次出现的指定元素。 E removeFirst() 获取并移除此双端队列第一个元素。 boolean removeFirstOccurrence(Object o) 从此双端队列移除第一次出现的指定元素。 E removeLast() 获取并移除此双端队列的最后一个元素。 boolean removeLastOccurrence(Object o) 从此双端队列移除最后一次出现的指定元素。 int size() 返回此双端队列的元素数。
Priority Queue 优先队列 添加数据时间复杂度是O(1) 删除数据时间复杂度是O(logn),按照元素的优先级取出。 底层具体的数据结构较为多样和复杂 ：heap (二叉树堆/斐波那契堆)、bst(二叉搜索树/红黑树/AVL)、treap