数据结构.md

数据结构

Stack(栈-LIFO后进先出)

public class Node<E> {
    private E item;
    private Node<E> next;

    public E getItem() {
        return item;
    }

    public void setItem(E item) {
        this.item = item;
    }

    public Node<E> getNext() {
        return next;
    }

    public void setNext(Node<E> next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return ReflectionToStringBuilder.toString(this);
    }
}

public class LinkedStack<E> {
    private Node<E> head = null;

    public LinkedStack() {
    }

    public boolean empty() {
        return head == null;
    }

    public E peek() {
        if (empty()) {
            return null;
        }
        return head.getItem();
    }

    public E pop() {
        if (empty()) {
            return null;
        }

        E item = head.getItem();
        head = head.getNext();
        return item;
    }

    public E push(E item) {
        Node<E> oldNode = head;
        head = new Node<>();
        head.setItem(item);
        head.setNext(oldNode);

        return item;
    }

    @Override
    public String toString() {
        return ReflectionToStringBuilder.toString(this);
    }
}

链表结构

public class LinkedStack<E> {
    private Node<E> head = null;

    public LinkedStack() {
    }

    public boolean empty() {
        return head == null;
    }

    public E peek() {
        if (empty()) {
            return null;
        }
        return head.getItem();
    }

    public E pop() {
        if (empty()) {
            return null;
        }

        E item = head.getItem();
        head = head.getNext();
        return item;
    }

    public E push(E item) {
        Node<E> oldNode = head;
        head = new Node<>();
        head.setItem(item);
        head.setNext(oldNode);

        return item;
    }

    @Override
    public String toString() {
        return ReflectionToStringBuilder.toString(this);
    }
}

数组结构, 没有结数组长度进行变更。每次push要判断一下point和data长度，如果到一定比例（例如：80%）把data 复制到一个新的数组（新数组的长度大于原来，具体值可以参照ArrayList实现）。对pop方法也要做判断，如果数据较少，则缩短数组长度。

public class ArrayStack<E> {
    private Object [] data;
    private int point = 0;

    public ArrayStack(int initialCapacity) {
        data = new Object[initialCapacity];
    }

    public boolean empty() {
        return data == null || data.length == 0;
    }

    public E push(E item) {
        data[point ++] = item;
        return item;
    }

    public E peek() {
        return (E) data[point];
    }

    public E pop() {
        E item = (E) data [point--];
        data[point] = null;
        return item;
    }

    @Override
    public String toString() {
        return ReflectionToStringBuilder.toString(this);
    }
}

Queue（队列-FIFO先进先出）

public class LinkedQueue<E> {
    private Node<E> head, tail;

    public boolean empty() {
        return head == null;
    }

    public void add(E item) {
        Node<E> oldTail = tail;
        tail = new Node<>();
        tail.setItem(item);
        if (empty()) {
            head = tail;
            return;
        }
        oldTail.setNext(tail);
    }

    public E remove() {
        if (head == null) {
            return null;
        }

        E item = head.getItem();
        head = head.getNext();
        if (empty()) {
            tail = null;
        }
        return item;
    }

    @Override
    public String toString() {
        return ReflectionToStringBuilder.toString(this);
    }
}