数据结构——栈

写在开始

在日常代码中,递归出现的频率都较高,但是递归到了语言处理的时候,其内部实现是什么样的呢?这里介绍的就是和队列一样,出现频率高的一种数据结构——栈。

基本性质

栈和队列相对立,栈里面的元素总是后进先出(LIFO:Last in first out)

栈的基本模型

其最先进的元素位于栈底,最后进的元素位于栈顶。

栈的基本操作

基本参数定义

private Object[] stack;//数据持有数组
private int tail = 0;//用于标记尾部index

1、入栈(压入栈)

@Override
protected E push(E e) {
    if (e == null) {
        return null;
    }
    stack[tail] = e;
    if (++tail == stack.length) {
        doubleCapacity();
    }
    return e;
}

压入的操作比较简单,直接给尾部赋值。

从这儿可以看出数组的尾部即为栈的逻辑栈顶。

2、出栈(弹出栈)

@SuppressWarnings("unchecked")
@Override
protected E pop() {
    if (tail <= 0) {
        return null;
    }
    Object o = stack[--tail];
    stack[tail] = null;
    return (E) o;
}

弹出元素,将尾部指针减一,同时置空之前位置上的元素,促使内存空间在GC的作用下能够更快释放。

3、扩容

private void doubleCapacity() {
    int old = stack.length;
    int newCapacity = old << 1;
    //overflow
    if (newCapacity < 0) {
        throw new IllegalStateException("stack is too big");
    }
    Object[] a = new Object[newCapacity];
    System.arraycopy(stack, 0, a, 0, old);
    stack = a;
}

每次扩容为前一次的两倍,并拷贝数据至扩容之后的数组。

4、移除任意元素

@Override
public boolean remove(E element) {
    for (int i = 0; i < tail; i++) {
        if (stack[i].equals(element)) {
            return delete(i);
        }
    }
    return false;
}

private boolean delete(int i) {
    Object[] stack = this.stack;
    stack[i] = null;
    int size = this.tail;
    int move = size - i - 1;
    if (move > 0) {
        System.arraycopy(stack, i + 1, stack, i, move);
    }
    tail = size - 1;
    return true;
}

每移除一个元素都将会导致其后面的元素一一移动,这带来的额外开销较大,所以和队列一样,不建议频繁的移除任意位置的元素。

递归的实现

递归在虚拟机中通过对栈的调度实现的,在Java当中也就是熟知的栈内存。

这里借用其他文章的一张图,大概标识一下Java运行时的内存分区:

这里写图片描述

在程序运行过程中会开辟一个工作线程,而后当前执行线程中的基本数据类型、方法返回值、局部等信息会存储在虚拟机栈当中。因而执行递归的过程中会不断在虚拟机栈中入栈(压入返回地址),直到抵达最后一层,然后再依次弹出。

所以在执行递归的过程中可能会产生StackOverflowError错误,这就表明,使用递归实现已经将虚拟机给撑爆了(栈已经无法压入新的返回地址)。

这时可以自定义栈存储数据,代替递归。

  • 当前大部分JVM都可以动态扩展,只不过JVM规范也允许固定长度的虚拟机栈;
  • 大部分语言的实现递归方法都是依靠栈,只是栈大小不同。

最后

栈和队列是基本数据结构,也是操作系统或者较多语言常用的数据结构。

数据结构——队列

写在开始

无论是在操作系统还是现实生活中,队列总是一种很有用的数据结构,它是现实中排队模型的结构化。

基本性质

先进先出(FIFO:First in First out)

基本模型

队列元素总是由队尾入队,队首出队。也就保证了先进的先出(不考虑移除元素的情况)

(常见)队列的分类

  1. 顺序队列(ArrayDeque):即上面列举的模型
  2. 循环队列:元素一直在队列中,依靠游标获得元素,游标抵达队尾时再次移向队首。
  3. 优先队列(PriorityQueue):元素在队列内部按照优先级排列,优先级高的先出队。
  4. 阻塞(循环/优先/顺序)队列(BlockingQueue):适用于异步操作的队列模型

下面我们讲解一下使用数组实现顺序队列(除此之外还可以使用链式结构或者栈实现队列),

其中循环队列可以基于顺序队列很容易实现;
优先队列在讲解Java基础Queue的时候已经讲解过,可以使用二叉堆实现;
而阻塞队列因为现在对Java异步不是非常了解,故暂时不做讲解。

队列的基本操作与实现

数据的基本定义

/**
 * Holder all queue data. 
 */
private Object[] queue;
/**
 * The cursor of the head of the queue.
 */
private int head = 0;
/**
 * The cursor of the tail of the queue.
 */
private int tail = 0;

使用head和tail去标记队列的起始位置,可以一定程度上减小每次出队操作需要对数组进行重整的开销。

1、入队(offer)

@Override
public E offer(E e) {
    if (e == null) {
        return null;
    }
    queue[tail] = e;
    if (++tail == queue.length) {
        doubleCapacity();
    }
    return e;
}
入队操作直接将元素放置在队尾,并且将队尾的游标向后移动,如果这时已经到达队尾,那么动态扩容。

2、出队(poll)

@SuppressWarnings("unchecked")
@Override
public E poll() {
    if (tail <= 0) {
        return null;
    }
    Object result = queue[head];
    if (result == null) {
        return null;
    }
    queue[head] = null;
    if (++head == (queue.length >>> 1)) {
        reorganizeQueue();
    }
    return (E) result;
}

private void reorganizeQueue() {
    Object[] q = queue;
    int t = tail;
    int h = head;
    int size = t - h;
    Object[] a = new Object[t];
    System.arraycopy(q, h, a, 0, size);
    queue = a;
    head = 0;
    tail = size;
}

出队的时候直接获取队首的元素,并将队首位置置为null,如果队首的位置已经抵达整个队列容量的一半(此时可能一直在做出队操作),那么重整队列元素,避免下次入队元素的时候进行无效的动态扩容,节约内存空间。

3、扩容

private void doubleCapacity() {
    int old = queue.length;
    int h = head;
    int size = old - h;
    int newCapacity = old << 1;
    //overflow
    if (newCapacity < 0) {
        throw new IllegalStateException("queue is too big");
    }
    Object[] a = new Object[newCapacity];
    System.arraycopy(queue, h, a, 0, size);
    queue = a;
    head = 0;
    tail = size;
}

每次扩容都会对数组进行双倍容量的分配。

4、移除元素

@Override
public boolean remove(E element) {
    for (int i = head; i < tail; i++) {
        Object o = queue[i];
        if (o.equals(element)) {
            return delete(i);
        }
    }
    return false;
}

private boolean delete(int i) {
    if (i == head) {
        poll();
        return true;
    }
    if (i == tail - 1) {
        queue[i] = null;
        tail = i;
        return true;
    }
    //head <= i < tail
    int h = head;
    int t = tail;
    int front = i - h;
    int back = t - i - 1;
    Object[] queue = this.queue;
    queue[i] = null;
    if (front < back) {
        System.arraycopy(queue, h, queue, h + 1, front);
        head = h + 1;
    } else {
        System.arraycopy(queue, i + 1, queue, i, back);
        tail = t - 1;
    }
    return true;
}

每次移除元素通过遍历获得所需要移除的游标i;如果移动的是中间元素,那么势必会在数组中间产生一个空位。所以每次通过remove移除元素都有可能造成对数组的重新分配。因而在使用队列的时候尽量避免频繁移除元素。

Tip:
1、如果使用链表实现队列的话不会存在移除的开销。

2、代码传送门(https://github.com/TangTangG/DataStructure/tree/master/src/queue)

优先队列

基本操作示意

入队

出队

数据结构——(二叉)堆

写在开始

通常在实现优先队列或者解决topN问题的时候,二叉堆这种数据结构都是一个比较好的实现方案。

树/类树

定义

(二叉)堆是一种通常采用数组存储的数据对象。

基本性质

虽然用数组实现,但是

  1. 因为其每个位于i的节点均有两个子节点分别位于2i、2i+1,所以结构上类似于树。
  2. 又因为添加元素的时候总是将树一层填满再填下一层,所以在树的结构上具有完全二叉树的性质,同时也具有类似于AVL树的平衡性。
  3. 又因为我们想要快速找出最小(大)元素,所以,最小(大)的元素应该在根上。也就是,要求任意节点应当小于(大于)其子节点,也就是,每个子树都是最小(大)堆。

1、2反映了堆的结构性;3则反映了其堆序性。

例如:堆中存储的数据如下:(来源于《数据结构与算法分析》)

其对应树是这样的:

堆的基本操作

以下操作均假设有如下结构的最小堆:

insert

将任意元素插入到堆中,我们在堆下一个可用位置创建一个空位(保持堆是完全树的特性)。如果插入元素刚好能够置于空位且不破坏堆序,那么插入完成;否则,我们需要将空位父节点的元素移入空位,这样,空位就朝着根的方向上冒一步。重复该过程,直至找到插入元素合适的位置。

以插入元素14为例,以下是插入的大抵过程:

上述过程,我们称为上滤,每次将待插入元素和其父节点比较,上冒一次(交换空位和父节点),直至找到合适位置。

delete(删除最小/大元素)

Tip:因为例子是最小堆,所以这里讲解移除的是最小元素,最大元素是一样的过程。

移除最小元,即移除根节点。每次移除将最后一个元素(记为Last)也“移除”,并在根节点创建空位。如果Last赋值到根节点刚好满足堆序的性质,那么删除完成;否则,将Last与左右儿子较小,并下潜一层,同时将较小值与空位交换。重复该过程,直至给Last找到合适的位置。

移除根节点13,大抵过程如下图所示:

上述过程,称为下滤,移除根之后创建空位,位置上“移除”掉最后一个元素,每次和左右儿子较小的交换位置,直至找到合适的位置,而后赋值。

小结

  • 无论是上滤还是下滤,首先都保证了对是一颗完全树的特性(通过每次操作最后一个元素)
  • 无论是上滤还是下滤,平均时间复杂度都为O(logN)
  • 上滤是检测是否是最小元的过程,下滤是求解最小元的过程

移除堆中任意位置的元素

讲解堆序的时候提到,堆每个子树也是一个最小(大)堆。所以从逻辑上来说,移除任意位置(记为i)的元素即是移除其某个子树的根节点(最小或者最大元)。所以首先就下滤,如果下滤之后的位置在i的下方,那么删除完成;否则,下滤后的位置就是i,那么就需要策略性将i位置上的元素上滤一次,以保证堆序性。

构建堆

  1. 构建堆可以重复执行(insert)上滤的过程,此时从任意数据源构建堆的最坏时间复杂度也为O(NlogN)。
  2. 构建堆的一般算法如下:
  • 将N个元素元素以任意顺序放入堆(树)中,保持堆的结构特性;
  • 对位于[0,N/2]的元素从N/2开始执行下滤(求得每个子树的最小元),进而保持堆序性。

一颗满二叉树的每层元素是上一层的2倍,所以N/2也就在逻辑上定位到倒数二层。相比于重复N次上滤而言,减少了对最后一层求解最小元的过程。

代码实现

可以参考这里(GitHub_Heap

数据结构——链表

  • 写在开始

本章主要介绍如何使用Java构建一个(单/双向)链表,通过本文,你可以轻松构建一个自己的链表。

  • 基础概念

  • 链表中的节点

通常链表中会包含我们想要保存的数据(data)以及指向下一级或上一级的句柄;

即:

对应代码大抵是酱紫的:

public class Node{
        Object data;//数据
        Node next;//指向下一节点的句柄(对象)
}
  • 链表执行的时间复杂度:
    • 索引: O(n)(线性结构,需要遍历)
    • 搜索: O(n)
    • 插入: O(1)(已知需要插入到什么位置的)
    • 移除: O(1)(已知需要从什么位置移除)
  • 链表基本包含以下基础操作:插入、删除、更新、查询
  • 故,在本章中链表做如下抽象:
public abstract class DataModel<E> {

    /**
     * 插入数据
     */
    public synchronized E insert(E element){
        return element;
    }

    /**
     * 移除某个数据
     */
    public synchronized boolean remove(E element){
        return false;
    }

    /**
     * 或者某个位置链表所存储的数据
     */
    public E childAt(int index){
        return null;
    }

    /**
     * 获取某个数据链表中的位置
     */
    public int indexOf(E element){
        return -1;
    }

    /**
     * 判断是否包含某个元素
     */
    public boolean contain(E element){
        return false;
    }

    /**
     * 设置某个元素的值
     */
    public synchronized E set(int index,E element){
        return element;
    }

    /**
     * 用于遍历的接口
     */
    public interface Consumer<E> {
        void node(int idx, E element);
    }

    /**
     * 对外提供快捷遍历链表的接口
     */
    public void foreach(Consumer<? super E> consumer) {

    }

    /**
     * 数据节点;包含基本的数据对象
     */
    protected static class Node<E>{

        public E element;

        public Node(E element) {
            this.element = element;
        }

        public String toString(){
            return element.toString();
        }
    }
}

 

包含了基础的操作,以及链表节点类Node。

  • 单向链表

    链表中的节点仅指向下一个节点,并且最后一个节点指向空。

  • 创建一个新的对象继承至我们刚刚定义的抽象类:

注:删除的效率理论上如果知道已知需要删除的节点,效率应该为O(1)。

本例中根据元素是需要线性查找,故效率为O(n)

public abstract class OneWay<E> extends DataModel<E> {

    protected OneWayNode last;
    protected OneWayNode first;

    ...

    static class OneWayNode<E> extends Node<E> {

        OneWayNode next;

        OneWayNode(E element, OneWayNode next) {
            super(element);
            this.next = next;
        }
    }
}
  •  添加

添加一个节点,大体可以分为以下两点:

  1. 上一级能够获取到下一级节点(上一级的next指向添加的节点);
  2. 指明添加节点的下一集节点;

代码如下(默认直接作为last的子节点):

   @Override
    public synchronized E insert(E e) {
        if (e == null) {
            return null;
        }
        OneWayNode<E> newNode = new OneWayNode<>(e, null);
        if (first == null) {
            first = newNode;
        }
        if (last != null) {
            last.next = newNode;
        }
        last = newNode;
        return e;
    }
  • 删除

删除,其实就是添加的逆向过程。还是分为两点来说:

  1. 让上一级节点指向自己(被删除节点)的下一级
  2. 移除自己对下一级节点的引用

代码如下:

   @Override
    public synchronized boolean remove(E e) {
        OneWayNode node = first;
        if (node.element.equals(e)) {
            first = first.next;
            return true;
        }
        while (node.next != null) {
            if (node.next.element.equals(e)) {
                if (node.next.equals(last)) {
                    node.next = null;
                    last = node;
                } else {
                    OneWayNode newNext = node.next.next;
                    node.next.next = null;
                    node.next = newNext;
                }
                return true;
            }
            node = node.next;
        }
        return false;
    }
  • 查询

查询有比较多的查询方式,本章中分为以下三种形式:

  1. 通过index查询存储的data
  2. 检查是否存在某个节点
  3. 查询某个元素在链表中的位置

因为链表为线性结构,故时间复杂度和数组一致为O(N)

代码如下:

   @Override
    public boolean contain(E e) {
        return node(e) == null;
    }

    @Override
    public E childAt(int index) {
        OneWayNode node = first;
        for (int i = 0; i <= index && node != null; i++) {
            node = node.next;
        }
        if (node == null) {
            return null;
        }
        return (E) node.element;
    }

    @Override
    public int indexOf(E element) {
        int index = -1;
        if (element == null){
            return index;
        }
        int cursor = -1;
        OneWayNode node = first;
        while (node != null) {
            if (node.element.equals(element)) {
                break;
            } else {
                cursor++;
            }
            node = node.next;
            index++;
        }
        if (index == cursor){
            index = -1;
        }
        return index;
    }

    /**
     * 根据元素获取到对应node
     */
    private OneWayNode node(E e) {
        if (e == null) {
            return null;
        }
        if (first == null) {
            return null;
        }
        OneWayNode nextNode = first.next;
        while (nextNode != null) {
            if (nextNode.element.equals(e)) {
                return nextNode;
            }
            nextNode = nextNode.next;
        }
        return null;
    }
  • 更新

更新可以更新指定位置的元素;也可以根据旧的元素索引,而后用新元素替换。

   @Override
    public E set(int index, E newVal) {
        int cursor = 0;
        OneWayNode node = first;
        while (node != null) {
            if (index == cursor) {
                node.element = newVal;
                return newVal;
            }
            node = node.next;
            cursor++;
        }
        return null;
    }

    public E update(E oldVal, E newVal) {
        OneWayNode node = first;
        while (node != null) {
            if (node.element.equals(oldVal)) {
                node.element = newVal;
                return newVal;
            }
            node = node.next;
        }
        return null;
    }
  • 反转单链表

反转单链表,比较常用的方法就是递归逐级反转。

利用递归,先到达最后的一个节点,然后开始反转。

代码如下:

public synchronized OneWay reverse() {
        OneWayNode oldLast = last;
        last = first;
        reverseNode(first);
        first = oldLast;
        return this;
    }

    private void reverseNode(OneWayNode head) {
        if (head == null || head.next == null) {
            return;
        }
        reverseNode(head.next);//每次传入旧的父节点
        head.next.next = head;
        head.next = null;
    }

单链表在使用过程中,如果想获取某个节点的上一节点,这个时候就比较麻烦了,需要通过递归,告知下一级节点,然后在通过比对,最后输出。

如果是双向链表就不要这样了,因为,它持有上一级节点的句柄。


  • 双向链表

双向,即每个节点持有三个句柄:

  1. 上一级节点的句柄
  2. 下一级节点的句柄
  3. 数据对象

大抵长这样:

同样,我们定义一个类,继承至我们定义的模型:

public class Doubly<E> extends DataModel<E> {

    int size = 0;
    private DoublyNode first;
    private DoublyNode last;

    ...

    static class DoublyNode<E> extends Node<E>{

        DoublyNode prev;
        DoublyNode next;

        public DoublyNode(E element, DoublyNode prev, DoublyNode next) {
            super(element);
            this.prev = prev;
            this.next = next;
        }
    }
}
  • 添加

对双链表的添加比但链表稍微复杂一些:

  1. 告知父节点next应指向插入节点
  2. 告知子节点prev应指向插入节点
  3. 插入节点的prev需指向父节点
  4. 插入节点的next需指向子节点

大抵代码如下:

   /**
     * 默认在最后插入子节点
     */
    @Override
    public synchronized E insert(E element) {
        DoublyNode oldLast = last;
        DoublyNode<E> newNode = new DoublyNode<>(element, oldLast,null);
        last = newNode;
        if (oldLast == null){
            first = newNode;
        } else {
            oldLast.next = newNode;
        }
        size++;
        return element;
    }

    /**
     * 在最前面插入子节点
     */
    public synchronized E insertBefore(E element) {
        DoublyNode oldFirst = first;
        DoublyNode<E> newNode = new DoublyNode<>(element, null, oldFirst);
        first = newNode;
        if (oldFirst == null){
            last = newNode;
        } else {
            oldFirst.prev = newNode;
        }
        size++;
        return element;
    }

    /**
     * 根据index在任意位置插入元素,可指定在之前或者之后
     */
    public synchronized E insertAt(int index,E element,boolean isBefore) {
        if (index < 0){
            return null;
        }
        if (first == null || last == null){
            return insert(element);
        }
        if (index == 0){
            return insertBefore(element);
        } else if (index == size - 1){
            return insert(element);
        }
        DoublyNode axis = nodeAt(index);
        if (axis == null){
            return null;
        }
        if (isBefore){
            DoublyNode prev = axis.prev;
            DoublyNode<E> newNode = new DoublyNode<>(element, prev, axis);
            prev.next = newNode;
            axis.prev = newNode;
        } else {
            DoublyNode next = axis.next;
            DoublyNode<E> newNode = new DoublyNode<>(element, axis, next);
            next.prev = newNode;
            axis.next = newNode;
        }
        size++;
        return element;
    }
  • 删除

删除的过程比较简单,先查询到相关节点,而后直接更改指向

   @Override
    public synchronized boolean remove(E element) {
        DoublyNode<E> node = node(element);
        if (node == null){
            return false;
        }
        DoublyNode prev = node.prev;
        DoublyNode next = node.next;
        if (prev != null){
            prev.next = next;
        } else {
            first = next;
        }

        if (next != null){
            next.prev = prev;
        } else {
            last = prev;
        }
        size--;
        return true;
    }
  • 查询

在定义类的时候我们通过size记录了大小,这样可以在下面通过位置(index)索引的时候节约时间。

先判断位置是位于链表前端还是后端。

具体代码如下:

    private DoublyNode nodeAt(int index) {
        if (index < 0 || index >= size){
            return null;
        }
        if (index < (size >> 1)){//是否在靠前的位置
            DoublyNode<E> node = first;
            for (int i = 0; i <= index; i++) {
                node = node.next;
            }
            return node;
        } else {
            DoublyNode<E> node = last;
            for (int i = size - 1; i >= index ; i++) {
                node = node.prev;
            }
            return node;
        }
    }

    private DoublyNode node(E e) {
        DoublyNode<E> node = first;
        if (e == null){
            for (int i = 0; i < size; i++) {
                if (node.element == null){
                    return node;
                }
                node = node.next;
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (e.equals(node.element)){
                    return node;
                }
                node = node.next;
            }
        }
        return null;
    }

    @Override
    public E childAt(int index) {
        DoublyNode nodeAt = nodeAt(index);
        return nodeAt == null ? null : (E) nodeAt.element;
    }

    @Override
    public int indexOf(E element) {
        DoublyNode<E> node = first;
        if (node == null){
            return -1;
        }
        for (int i = 0; i < size; i++) {
            if (element.equals(node.element)){
                return i;
            }
            node = node.next;
        }
        return -1;
    }
  • 更新

更新和单向链表一致:

    @Override
    public synchronized E set(int index, E element) {
        DoublyNode node = nodeAt(index);
        if (node != null){
            node.element = element;
            return element;
        }
        return null;
    }
  • 总结

链表是数据结构中的入门。

它反应了数据的基本组织方式(如何保存对象、以及指向其他对象的句柄)。

它实际上反应的是两个实体之间的关系。

掌握了链表,再学习其他数据结构(树、图等)会容易很多,因为基本概念一致。

本文的代码可以在这里找到:GitHub_LinkedList