标签：return int 常见几种 Override array 数据结构 public size

常见的数据结构：数组、链表、队列、栈、、堆、二叉树、B树、哈希表、图

数组

因为数组内的元素是连续存储的，所以数组中元素的地址，可以通过其索引计算出来。根据索引查找元素，时间复杂度是 \(O(1)\)。

动态数组

动态数组具体代码实现

import java.util.Arrays;
import java.util.Iterator;
import java.util.function.Consumer;
import java.util.stream.IntStream;

public class DynamicArray implements Iterable<Integer> {
    private int capacity;
    private int size;
    private int[] array;


    public DynamicArray(int capacity){
        this.capacity = capacity;
    }


    /**
     * 向最后位置 [size] 添加元素
     *
     * @param element 待添加元素
     */
    public void addLast(int element){
        add(size, element);
    }

    /**
     * 向 [0 .. size] 位置添加元素
     *
     * @param index   索引位置
     * @param element 待添加元素
     */
    public void add(int index, int element){
        checkAndGrow();
        checkIndex(index);
        if(index <size ){
            System.arraycopy(array, index, array, index+1, size - index);
        }
        array[index] = element;
        size++;
    }

    /**
     * 从 [0 .. size) 范围删除元素
     *
     * @param index 索引位置
     * @return 被删除元素
     */
    public int remove(int index){
        checkIndex(index);
        int removed = array[index];
        if(index < size -1){
            System.arraycopy(array, index+1, array, index, size - index -1);
        }
        size--;
        return removed;
    }

    /**
     * 查询元素
     *
     * @param index 索引位置, 在 [0..size) 区间内
     * @return 该索引位置的元素
     */
    public int get(int index){
        checkIndex(index);
        return array[index];
    }

    /**
     * 遍历方法1
     *
     * @param consumer 遍历要执行的操作, 入参: 每个元素
     */
    public void foreach(Consumer<Integer> consumer){
        for (int i = 0; i < size; i++) {
            consumer.accept(array[i]);
        }
    }

    /**
     * 遍历方法2 - 迭代器遍历
     */
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>(){
            int index = 0;
            @Override
            public boolean hasNext() { // 有没有下一个元素
                return index < size;
            }

            @Override
            public Integer next() { // 返回当前元素,并移动到下一个元素
                return array[index++];
            }
        };
    }


    /**
     * 遍历方法3 - stream 遍历
     *
     * @return stream 流
     */
    public IntStream stream(){
        return IntStream.of(Arrays.copyOfRange(array, 0, size));
    }

    /**
     * 检查是否需要扩容
     * */
    private void checkAndGrow(){
        if(size == 0){
            array = new int[capacity];
        }

        if(size == capacity){
            capacity += capacity >> 1;
            int[] newArray = new int[capacity];
            System.arraycopy(array, 0, newArray, 0, size);
            array = newArray;
        }
    }


    /**
    * 检查索引是否合法
    */
    private void checkIndex(int index){
        if(index<0 || index>size){
            throw new ArrayIndexOutOfBoundsException();
        }
    }
}

链表

单向链表、双向链表、环形链表、跳表

队列

双端队列、优先队列、阻塞队列、单调队列

链表实现队列

单向环形带哨兵链表方式来实现队列

链表实现队列

import java.util.Iterator;

public class LinkedListQueue<E> implements Queue<E>, Iterable<E>{

    private static class Node<E>{
        E value;
        Node<E> next;

        public Node(E value, Node<E> next){
            this.value = value;
            this.next = next;
        }
    }

    private final Node<E> head = new Node<>(null, null); //哨兵
    private Node<E> tail = head; //尾指针，指向最后一个节点
    private int size = 0;
    private int capacity = Integer.MAX_VALUE;

    {
        tail.next = head; // 环形队列，最后一个节点指向哨兵节点。
    }

    public LinkedListQueue(){
    }

    public LinkedListQueue(int capacity){
        this.capacity = capacity;
    }

    @Override
    public boolean offer(E value) {
        if(isFull()){
            return false;
        }
        Node<E> added = new Node<>(value, head);
        tail.next = added;
        tail = added;
        size++;
        return true;
    }

    @Override
    public E poll() {
        if(isEmpty()){
            return null;
        }
        Node<E> removed = head.next;
        head.next = removed.next;
        if(removed == tail){
            //如果删除的是尾节点，即队列只有一个节点时，尾指针指向head，此时队列为空
            tail = head;
        }
        size--;
        return removed.value;
    }

    @Override
    public E peek() {
        return head.next.value;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == capacity;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node<E> curr = head.next;
            @Override
            public boolean hasNext() {
                return curr != head;
            }

            @Override
            public E next() {
                E value = curr.value;
                curr = curr.next;
                return value    ;
            }
        };
    }
}

数组实现队列

环形数组实现队列

环形数组实现

import java.util.Iterator;

public class ArrayQueue<E>  implements Queue<E>, Iterable<E>{

    private int head = 0; //头指针，指向第一个元素
    private int tail = 0; //尾指针，指向下一个新添元素的位置，即最后一个元素的后一位
    private int length; //环形数组长度，比指定容量大1，空一个位置
    private E[] array;

    public ArrayQueue(int capacity){
        length = capacity + 1; // 最后一个位置不存储元素，以便区别队列满时和队列空时
        array = (E[]) new Object[capacity];
    }

    @Override
    public boolean offer(E value) {
        if(isFull()){
            return false;
        }
        array[tail] = value;
        tail = (tail + 1) % length;
        return true;
    }

    @Override
    public E poll() {
        if(isEmpty()){
            return null;
        }
        E value = array[head];
        head = (head + 1) % length;
        return value;
    }

    @Override
    public E peek() {
        if(isEmpty()){
            return null;
        }
        return array[head];
    }

    @Override
    public boolean isEmpty() {
        return head == tail;
    }

    @Override
    public boolean isFull() {
        return (tail + 1) % length == head;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>(){
            int p = head;
            @Override
            public boolean hasNext() {
                return p != tail;
            }

            @Override
            public E next() {
                E value = array[p];
                p = (p + 1) % length;
                return value;
            }
        };
    }
}

可维护一个变量size来判断队列空或满。或者head和tail指针不断增加，需要用到索引再对容量取模，为了取模运算快，可使容量为2次幂，tips：对二次幂取模m等价于&(m-1)。

双端队列

环形双向链表实现双端队列

链表实现双端队列

import java.util.Iterator;

/**
 * 基于环形双向链表的双端队列
 * @param <E> 元素类型
 */
public class LinkedListDeque<E> implements Deque<E>, Iterable<E> {

    private static class Node<E>{
        Node<E> prev;
        E value;
        Node<E> next;

        public Node(Node<E> prev, E value, Node<E> next){
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    private Node<E> sentinel = new Node<>(null, null,null); //头尾哨兵

    private int size = 0;

    private int capacity = Integer.MAX_VALUE;

    public LinkedListDeque(){
        sentinel.next = sentinel;
        sentinel.prev = sentinel;
    }

    public LinkedListDeque(int capacity){
        this();
        this.capacity = capacity;
    }


    @Override
    public boolean offerFirst(E value) {
        if(isFull()){
            return false;
        }
        Node<E> added = new Node<E>(sentinel, value, sentinel.next);
        sentinel.next.prev = added;
        sentinel.next = added;
        size++;
        return true;
    }

    @Override
    public boolean offerLast(E value) {
        if(isFull()){
            return false;
        }
        Node<E> added = new Node<E>(sentinel.prev, value, sentinel);
        sentinel.prev.next = added;
        sentinel.prev = added;
        size++;
        return true;
    }

    @Override
    public E pollFirst() {
        if(isEmpty()){
            return null;
        }
        Node<E> removed = sentinel.next;
        sentinel.next = removed.next;
        removed.next.prev = sentinel;
        size--;
        removed.next = null;
        removed.prev = null; //有利于垃圾回收
        return removed.value;
    }

    @Override
    public E pollLast() {
        if(isEmpty()){
            return null;
        }
        Node<E> removed = sentinel.prev;
        removed.prev.next = sentinel;
        sentinel.prev = removed.prev;
        size--;
        removed.next = null;
        removed.prev = null; //有利于垃圾回收
        return removed.value;
    }

    @Override
    public E peekFirst() {
        return isEmpty()?null:sentinel.next.value;
    }

    @Override
    public E peekLast() {
        return isEmpty()?null:sentinel.prev.value;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == capacity;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<>() {
            Node<E> curr = sentinel.next;
            @Override
            public boolean hasNext() {
                return curr != sentinel;
            }

            @Override
            public E next() {
                E value = curr.value;
                curr = curr.next;
                return value;
            }
        };
    }
}

循环数组实现双端队列

数组实现双端队列

import java.util.Iterator;

/**
 * 基于循环数组实现, 特点
 * <ul>
 *     <li>tail 停下来的位置不存储, 会浪费一个位置</li>
 * </ul>
 * @param <E>
 */
public class ArrayDeque<E> implements Deque<E>, Iterable<E> {

    private int head = 0;
    private int size = 0;
    private final E[] array;
    private final int capacity;

    public ArrayDeque(int capacity){
        this.capacity = capacity;
        array = (E[]) new Object[capacity];
    }

    @Override
    public boolean offerFirst(E value) {
        if(isFull()){
            return false;
        }
        head = (head-1+capacity)%capacity;
        array[head] = value;
        size++;
        return true;
    }

    @Override
    public boolean offerLast(E value) {
        if(isFull()){
            return false;
        }
        array[(head+size)%capacity] = value;
        size++;
        return true;
    }

    @Override
    public E pollFirst() {
        if(isEmpty()){
            return null;
        }
        E value = array[head];
        array[head] = null; //垃圾回收
        head = (head+1)%capacity;
        size--;
        return value;
    }

    @Override
    public E pollLast() {
        if(isEmpty()){
            return null;
        }
        int last = (head + size - 1) % capacity;
        E value = array[last];
        array[last] = null;
        size--;
        return value;
    }

    @Override
    public E peekFirst() {
        return isEmpty()?null:array[head];
    }

    @Override
    public E peekLast() {
        return isEmpty()?null:array[(head+size-1)%capacity];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<>(){
            int index = head;
            @Override
            public boolean hasNext() {
                return index != (index+size)%capacity;
            }

            @Override
            public E next() {
                E value = array[index];
                index = (index+1)%capacity;
                return value;
            }
        };
    }
}

优先级队列

定义优先级接口

public interface Priority {

    /**
     * 返回元素优先级，越大优先级越高
     * */
    int priority();
}

无序数组实现优先级队列

/**
 * 无序数组实现
 * 1. 入队保持顺序
 * 2. 出队前找到优先级最高的出队，相当于一次选择排序，并将元素往前移*/
public class PriorityQueue1<E extends Priority> implements Queue<E>{

    private final Priority[] array;
    private int size = 0;
    public PriorityQueue1(int capacity){
        array = new Priority[capacity];
    }

    @Override
    public boolean offer(E value) {
        if(isFull()){
            return false;
        }
        array[size++] = value;
        return true;
    }

    private int selectMax(){
        int max = 0;
        for(int i=1; i<size; i++){
            if(array[i].priority() > array[max].priority()){
                max = i;
            }
        }
        return max;
    }

    private void remove(int index){
        if(index < size-1){
            System.arraycopy(array, index+1, array, index, size - index - 1);
        }
        array[--size] = null;
    }
    @Override
    public E poll() {
        if(isEmpty()){
            return null;
        }
        int max = selectMax();
        E value = (E) array[max];
        remove(max);
        return value;
    }

    @Override
    public E peek() {
        if(isEmpty()){
            return null;
        }
        return (E) array[selectMax()];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }

}

有序数组实现优先级队列

/**
 * 有序数组实现优先级队列
 * 有序地插入元素，最后一个元素出队*/
public class PriorityQueue2<E extends Priority> implements Queue<E>{

    private Priority[] array;
    private int size = 0;

    public PriorityQueue2(int capacity){
        array = new Priority[capacity];
    }

    @Override
    public boolean offer(E value) {
        if(isFull()){
            return false;
        }
        int index = size-1;
        while(index >=0 && value.priority() < array[index].priority()){
            array[index + 1] = array[index];
            index--;
        }
        array[++index] = value;
        size++;
        return true;
    }

    @Override
    public E poll() {
        if(isEmpty()){
            return null;
        }
        E value = (E) array[--size];
        array[--size] = null;
        return value;
    }

    @Override
    public E peek() {
        if(isEmpty()){
            return null;
        }
        return (E) array[size - 1];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }
}

堆实现优先级队列

堆通常用完全二叉树实现，完全二叉树又可以用数组表示，从索引0开始，节点\(i\)的父节点为\(floor((i-1/)2)\)。节点\(i\)的左子节点为\(2i+1\)，右子节点为\(2i+2\)。

堆实现优先队列

/**
 * 利用大顶堆实现优先级队列*/
public class PriorityQueue3<E extends Priority> implements Queue<E>{

    private Priority[] array;
    private int size;

    public PriorityQueue3(int capacity){
        array = new Priority[capacity];
    }

    /**
     * 下潜，从索引index下潜到合适位置*/
    private void down(int index, int size){
        int max = index;
        if(2*index + 1 < size &&
                array[2*index + 1].priority() > array[index].priority()){
            max = 2*index + 1;
        }
        if(2*index + 2 < size &&
                array[2*index + 2].priority() > array[index].priority()){
            max = 2*index + 2;
        }
        if(max != index){
            swap(max, index);
            down(max, size);
        }
    }
    /**
     * 上浮，从索引index上浮到合适位置*/
    private void up(int index){
        int parent = (index - 1)/2;
        if(parent >= 0 && array[index].priority() > array[parent].priority()){
            swap(parent, index);
            up(parent);
        }
    }
    private void swap(int i, int j){
        Priority temp =  array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    @Override
    public boolean offer(E value) {
        if(isFull()){
            return false;
        }
        array[size++] = value;
        up(size-1);
        return true;
    }

    @Override
    public E poll() {
        if(isEmpty()){
            return null;
        }
        E value = (E) array[0];
        swap(0, --size);
        down(0,size);
        array[size] = null;
        return value;
    }

    @Override
    public E peek() {
        if(isEmpty()){
            return null;
        }
        return (E) array[0];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }
}

阻塞队列

单锁实现
ReentrantLock 配合条件变量来实现

ReentrantLock lock = new ReentrantLock();
Condition tailWaits = lock.newCondition(); // 条件变量
int size = 0;

public void offer(String e) {
    lock.lockInterruptibly();
    try {
        while (isFull()) {//使用while避免虚假唤醒
            tailWaits.await();	// 当队列满时, 当前线程进入 tailWaits 等待
        }
        array[tail] = e;
        tail++;
        
        size++;
    } finally {
        lock.unlock();
    }
}

private boolean isFull() {
    return size == array.length;
}

条件变量底层也是个队列，用来存储这些需要等待的线程，当队列满了，就会将 offer 线程加入条件队列，并暂时释放锁
将来我们的队列如果不满了（由 poll 线程那边得知）可以调用 tailWaits.signal() 来唤醒 tailWaits 中首个等待的线程，被唤醒的线程会再次争抢锁，从上次 await 处继续向下运行

/**
 * 单锁实现
 * @param <E> 元素类型
 */
public class BlockingQueue1<E> implements BlockingQueue<E> {
    private final E[] array;
    private int head = 0;
    private int tail = 0;
    private int size = 0; // 元素个数

    @SuppressWarnings("all")
    public BlockingQueue1(int capacity) {
        array = (E[]) new Object[capacity];
    }

    ReentrantLock lock = new ReentrantLock();
    Condition tailWaits = lock.newCondition();
    Condition headWaits = lock.newCondition();

    @Override
    public void offer(E e) throws InterruptedException {
        lock.lockInterruptibly();
        try {
            while (isFull()) {
                tailWaits.await();
            }
            array[tail] = e;
            if (++tail == array.length) {
                tail = 0;
            }
            size++;
            headWaits.signal();
        } finally {
            lock.unlock();
        }
    }

    @Override
    public void offer(E e, long timeout) throws InterruptedException {
        lock.lockInterruptibly();
        try {
            long t = TimeUnit.MILLISECONDS.toNanos(timeout);
            while (isFull()) {
                if (t <= 0) {
                    return;
                }
                t = tailWaits.awaitNanos(t);//方法返回剩余时间
            }
            array[tail] = e;
            if (++tail == array.length) {
                tail = 0;
            }
            size++;
            headWaits.signal();
        } finally {
            lock.unlock();
        }
    }

    @Override
    public E poll() throws InterruptedException {
        lock.lockInterruptibly();
        try {
            while (isEmpty()) {
                headWaits.await();
            }
            E e = array[head];
            array[head] = null; // help GC
            if (++head == array.length) {
                head = 0;
            }
            size--;
            tailWaits.signal();
            return e;
        } finally {
            lock.unlock();
        }
    }

    private boolean isEmpty() {
        return size == 0;
    }

    private boolean isFull() {
        return size == array.length;
    }
}

双锁实现
单锁的缺点在于：

生产和消费几乎是不冲突的，唯一冲突的是生产者和消费者它们有可能同时修改 size
冲突的主要是生产者之间：多个 offer 线程修改 tail
冲突的还有消费者之间：多个 poll 线程修改 head

如果希望进一步提高性能，可以用两把锁

一把锁保护 tail
另一把锁保护 head

ReentrantLock headLock = new ReentrantLock();  // 保护 head 的锁
Condition headWaits = headLock.newCondition(); // 队列空时，需要等待的线程集合

ReentrantLock tailLock = new ReentrantLock();  // 保护 tail 的锁
Condition tailWaits = tailLock.newCondition(); // 队列满时，需要等待的线程集合

size 并不受 tailLock 保护，tailLock 与 headLock 是两把不同的锁，并不能实现互斥的效果。因此，size 需要用下面的代码保证原子性

AtomicInteger size = new AtomicInteger(0);	   // 保护 size 的原子变量

size.getAndIncrement(); // 自增
size.getAndDecrement(); // 自减

难点：如何通知 headWaits 和 tailWaits 中等待的线程

条件变量的 await()， signal() 等方法需要先获得与之关联的锁，不能使用headLock锁来唤醒tailwaits中的线程。

解决办法：先获取相关锁，在唤醒对应的线程。为了避免嵌套而产生死锁，两段加锁改为平级。

性能还可以进一步提升

代码调整后 offer 并没有同时获取 tailLock 和 headLock 两把锁，因此两次加锁之间会有空隙，这个空隙内可能有其它的 offer 线程添加了更多的元素，那么这些线程都要执行 signal()，通知 poll 线程队列非空吗？
- 每次调用 signal() 都需要这些 offer 线程先获得 headLock 锁，成本较高，要想法减少 offer 线程获得 headLock 锁的次数
- 可以加一个条件：当 offer 增加前队列为空，即从 0 变化到不空，才由此 offer 线程来通知 headWaits，其它情况不归它管
队列从 0 变化到不空，会唤醒一个等待的 poll 线程，这个线程被唤醒后，肯定能拿到 headLock 锁，因此它具备了唤醒 headWaits 上其它 poll 线程的先决条件。如果检查出此时有其它 offer 线程新增了元素（不空，但不是从0变化而来），那么不妨由此 poll 线程来唤醒其它 poll 线程

这个技巧被称之为级联通知（cascading notifies），类似的原因

在 poll 时队列从满变化到不满，才由此 poll 线程来唤醒一个等待的 offer 线程，目的也是为了减少 poll 线程对 tailLock 上锁次数，剩下等待的 offer 线程由这个 offer 线程间接唤醒

最终双锁实现代码

public class BlockingQueue2<E> implements BlockingQueue<E> {

    private final E[] array;
    private int head = 0;
    private int tail = 0;
    private final AtomicInteger size = new AtomicInteger(0);
    ReentrantLock headLock = new ReentrantLock();
    Condition headWaits = headLock.newCondition();
    ReentrantLock tailLock = new ReentrantLock();
    Condition tailWaits = tailLock.newCondition();

    public BlockingQueue2(int capacity) {
        this.array = (E[]) new Object[capacity];
    }

    @Override
    public void offer(E e) throws InterruptedException {
        int c;
        tailLock.lockInterruptibly();
        try {
            while (isFull()) {
                tailWaits.await();
            }
            array[tail] = e;
            if (++tail == array.length) {
                tail = 0;
            }            
            c = size.getAndIncrement();
            // a. 队列不满, 但不是从满->不满, 由此offer线程唤醒其它offer线程
            if (c + 1 < array.length) {
                tailWaits.signal();
            }
        } finally {
            tailLock.unlock();
        }
        // b. 从0->不空, 由此offer线程唤醒等待的poll线程
        if (c == 0) {
            headLock.lock();
            try {
                headWaits.signal();
            } finally {
                headLock.unlock();
            }
        }
    }

    @Override
    public E poll() throws InterruptedException {
        E e;
        int c;
        headLock.lockInterruptibly();
        try {
            while (isEmpty()) {
                headWaits.await(); 
            }
            e = array[head]; 
            if (++head == array.length) {
                head = 0;
            }
            c = size.getAndDecrement();
            // b. 队列不空, 但不是从0变化到不空，由此poll线程通知其它poll线程
            if (c > 1) {
                headWaits.signal();
            }
        } finally {
            headLock.unlock();
        }
        // a. 从满->不满, 由此poll线程唤醒等待的offer线程
        if (c == array.length) {
            tailLock.lock();
            try {
                tailWaits.signal();
            } finally {
                tailLock.unlock();
            }
        }
        return e;
    }

    private boolean isEmpty() {
        return size.get() == 0;
    }

    private boolean isFull() {
        return size.get() == array.length;
    }

}

栈

单调栈、最小栈

链表实现栈

单向带头哨兵链表实现栈

链表实现

import java.util.Iterator;

/**
 * 链表实现栈*/
public class LinkedListStack<E> implements Stack<E>, Iterable<E>{

    private static class Node<E>{
        E value;
        Node<E> next;

        public Node(E value, Node<E> next){
            this.value = value;
            this.next = next;
        }
    }

    private final Node<E> sentinel = new Node<>(null, null); //哨兵节点
    private  int size = 0;
    private final int capacity;

    public LinkedListStack(int capacity){
        this.capacity = capacity;
    }

    @Override
    public boolean push(E value) {
        if(isFull()){
            return false;
        }
        size++;
        sentinel.next = new Node<>(value, sentinel.next);
        return true;
    }

    @Override
    public E pop() {
        if(isEmpty()){
            return null;
        }
        Node<E> head = sentinel.next;
        sentinel.next = head.next;
        size--;
        return head.value;
    }

    @Override
    public E peek() {
        if(isEmpty()){
            return null;
        }
        return sentinel.next.value;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == capacity;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<>(){
            Node<E> curr = sentinel.next;
            @Override
            public boolean hasNext() {
                return curr != null;
            }

            @Override
            public E next() {
                E value = curr.value;
                curr = curr.next;
                return value;
            }
        };
    }
}

数组实现栈

import java.util.Iterator;

public class ArrayStack<E> implements Stack<E>, Iterable<E>{

    private int top = 0;
    private E[] array;

    public ArrayStack(int capacity){
        array = (E[]) new Object[capacity];
    }

    @Override
    public boolean push(E value) {
        if(isFull()){
            return false;
        }
        array[top++] = value;
        return true;
    }

    @Override
    public E pop() {
        if(isEmpty()){
            return null;
        }
        return array[--top];
    }

    @Override
    public E peek() {
        if(isEmpty()){
            return null;
        }
        return array[top - 1];
    }

    @Override
    public boolean isEmpty() {
        return top == 0;
    }

    @Override
    public boolean isFull() {
        return top == array.length;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int index = top - 1;
            @Override
            public boolean hasNext() {
                return index != -1;
            }

            @Override
            public E next() {
                E value = array[index];
                index--;
                return value;
            }
        };
    }
}

堆

堆的主要方法：下潜、上浮、建堆、交换。
下潜(down)： 将 parent 索引处的元素下潜: 与两个孩子较大者交换, 直至没孩子或孩子没它大

private void down(int parent) {
        int left = parent * 2 + 1;
        int right = left + 1;
        int max = parent;
        if (left < size && array[left] > array[max]) {
            max = left;
        }
        if (right < size && array[right] > array[max]) {
            max = right;
        }
        if (max != parent) { // 找到了更大的孩子
            swap(max, parent);
            down(max);
        }
    }

上浮(up)：将 offered 元素上浮: 直至 offered 小于父元素或到堆顶，index为offered的索引

private void up(int offered, int index) {
        int child = index;
        while (child > 0) {
            int parent = (child - 1) / 2;
            if (offered > array[parent]) {
                array[child] = array[parent];
            } else {
                break;
            }
            child = parent;
        }
        array[child] = offered;
    }

建堆(heapify)：1. 找到最后一个非叶子节点。2. 从后向前，对每个节点执行下潜

private void heapify() {
        // 如何找到最后这个非叶子节点  size / 2 - 1
        for (int i = size / 2 - 1; i >= 0; i--) {
            down(i);
        }
    }

交换(swap)：交换两个索引处的元素

    private void swap(int i, int j) {
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

最大堆代码实现



public class MaxHeap {
    private int[] array;
    private int size;

    public MaxHeap(int capacity){
        array = new int[capacity];
    }

    /**
     * 接收array数组，建堆*/
    public MaxHeap(int[] array) {
        this.array = array;
        this.size = array.length;
        heapify();
    }

    private void heapify(){
        for(int i = size/2 -1; i>=0; --i){
            down(i);
        }
    }

   /**
    * 获取堆顶元素
    *
    * @return 堆顶元素
    */
    public int peek(){
        if(isEmpty()){
            return -1;
        }
        return array[0];
    }

    /**
     * 删除堆顶元素
     *
     * @return 堆顶元素
     */
    public int poll(){
        if(isEmpty()){
            return -1;
        }
        int value = array[--size];
        swap(0, size);
        down(0);
        return value;
    }

    /**
     * 删除指定索引处元素
     * 先上浮到堆顶，再删除
     * @param index 索引
     * @return 被删除元素
     */
    public int poll(int index){
        if(isEmpty()){
            return -1;
        }
        if(index<-1 || index>=size){
            throw new IllegalArgumentException("超出索引范围");
        }
        int value = array[index];
        up(Integer.MAX_VALUE, index);
        poll();
        return value;
    }


    /**
     * 替换堆顶元素
     *
     * @param replaced 新元素
     */
    public void replace(int replaced){
        array[0] = replaced;
        down(0);
    }

    /**
     * 堆的尾部添加元素
     *
     * @param offered 新元素
     * @return 是否添加成功
     */
    public boolean offer(int offered){
        if(isFull()){
            return false;
        }
        up(offered, size);
        size++;
        return true;
    }

    // 将 index 索引处的元素下潜: 与两个孩子较大者交换, 直至没孩子或孩子没它大
    private void down(int index){
        int left = 2 * index + 1;
        int right = left + 1;
        int max = index;
        if(left < size && array[left] > array[max]){
            max = left;
        }
        if(right < size && array[right] > array[max]){
            max = right;
        }
        if(max != index){
            swap(max, index);
            down(max);
        }
    }

    // 将 index 索引处元素上浮: 直至 元素 小于父元素或到堆顶
    private void up(int offered, int index){
        int child = index;
        while(child > 0){
            int parent = (child - 1) >>> 1;
            if(offered > array[parent]){
                array[child] = array[parent];
            }else{
                break;
            }
            child = parent;
        }
        array[child] = offered;
    }

    private void swap(int i, int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    public boolean isEmpty(){
        return size == 0;
    }

    public boolean isFull(){
        return size == array.length;
    }
}

二叉树

二叉搜索树、AVL数、红黑树
广度优先遍历：

初始化，将根节点加入队列
循环处理队列中每个节点，直至队列为空
每次循环内处理节点后，将它的孩子节点（即下一层的节点，从左孩子到右孩子）加入队列

前序遍历迭代实现

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new LinkedList<>();
        TreeNode curr = root;
        while(!stack.empty() || curr != null){
            while(curr != null){
                list.add(curr.val); //处理当前中间节点，前序遍历为中左右
                stack.push(curr);//将当前中间节点压栈，
                curr = curr.left;//将左子节点压栈
            }
            TreeNode node = stack.pop();//弹出中间节点
            curr = node.right; //将右子节点压栈
        }
        return list;
    }
}
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val, TreeNode left, TreeNode right){
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

中序遍历

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new LinkedList<>();
        TreeNode curr = root;
        while(!stack.empty() || curr != null){
            while(curr != null){              
                stack.push(curr);//将当前中间节点压栈，
                curr = curr.left;//将左子节点压栈
            }
            TreeNode node = stack.pop();//弹出中间节点
            list.add(node.val); //左边节点处理完，处理当前中间节点，中序遍历为左中右
            curr = node.right; //将右子节点压栈
        }
        return list;
    }
}

后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new LinkedList<>();
        TreeNode curr = root;
        TreeNode prev = null;
        while(!stack.empty() || curr != null){
            while(curr != null){
                stack.push(curr);//将当前中间节点压栈，
                curr = curr.left;//将左子节点压栈
            }
            TreeNode node = stack.peek();//通过中间节点访问右边
            if(node.right == null || node.right == prev){//没有右孩子，或者右边已经处理过
                //弹出并处理中间节点，后序遍历为左右中
                list.add(stack.pop().val);
                prev = node; //最新处理完的节点
            }else{
                curr = node.right; //将右子节点压栈
            }

        }
        return list;
    }
}

统一写法

LinkedList<TreeNode> stack = new LinkedList<>();

TreeNode curr = root; // 代表当前节点
TreeNode pop = null; // 最近一次弹栈的元素
while (curr != null || !stack.isEmpty()) {
    if (curr != null) {
        colorPrintln("前: " + curr.val, 31);
        stack.push(curr); // 压入栈，为了记住回来的路
        curr = curr.left;
    } else {
        TreeNode peek = stack.peek();
        // 右子树可以不处理, 对中序来说, 要在右子树处理之前打印
        if (peek.right == null) {
            colorPrintln("中: " + peek.val, 36);
            pop = stack.pop();
            colorPrintln("后: " + pop.val, 34);
        }
        // 右子树处理完成, 对中序来说, 无需打印
        else if (peek.right == pop) {
            pop = stack.pop();
            colorPrintln("后: " + pop.val, 34);
        }
        // 右子树待处理, 对中序来说, 要在右子树处理之前打印
        else {
            colorPrintln("中: " + peek.val, 36);
            curr = peek.right;
        }
    }
}

public static void colorPrintln(String origin, int color) {
    System.out.printf("\033[%dm%s\033[0m%n", color, origin);
}

B树

B+树

哈希表

布隆过滤器、一致性哈希

哈希冲突的解决办法

开放寻址法：我们在遇到哈希冲突时，去寻找一个新的空闲的哈希地址。

线性探测法：哈希值加一取模寻找空闲地址。

平方探测法：哈希值加减\(i^2\)取模向两边寻找。

再哈希法：使用多个哈希函数。

链地址法：将所有哈希地址相同的记录都链接在同一链表中。

公共溢出区：将哈希表分为基本表和溢出表，将发生冲突的都存放在溢出表中。

图

标签：return,int,常见,几种,Override,array,数据结构,public,size
From： https://www.cnblogs.com/hudad/p/18262335

【数据结构】常见的几种数据结构

数组

动态数组

链表

队列

链表实现队列

数组实现队列

双端队列

优先级队列

阻塞队列

栈

链表实现栈

数组实现栈

堆

二叉树

B树

哈希表

图

相关文章

赞助商

阅读排行