数据结构分析及其实现(Stack、Queue、Tree、LinkedList)

队列(queue),也是一种特殊的线性表，使用固定的一端来插入数据，另一端用于删除数据

先进先出，就像火车站排队买票一样！！！，整个队伍向前面移动。

分为顺序队列结构和链式队列结构

从JDK 5 开始，Java集合框架提供了Queue接口，实现该接口的类可以当成队列使用，如LinkedBlockingQueue，PriorityBlockingQueue。

可以通过轮询和等待-通知机制实现阻塞队列。

具体Queue实现：

import java.util.*;

public class SimpleQueue implements Iterable {
    private LinkedList storage = new LinkedList();
    public void add(T t){
        storage.offer(t);
    }
    public T get() {
        return storage.poll();
    }
    public Iterator iterator() {
        return storage.iterator();
    }

    public static void main(String[] args) {
        SimpleQueue queue = new SimpleQueue();
        queue.add(8);
        System.out.println(queue.get());
    }
}

我们在来看看用Stack如何实现Queue，非常不错，《Java编程思想》

import java.util.Stack;

 public class MyQueue{
    Stack stack = new Stack();
    Stack stackTmp = new Stack();

    //Push element X to the back of queue
    public void push(int x) {
        stack.push(x);
    }

    //Removes the element form in front of queue
    public void pop() {
        if (stackTmp.isEmpty()) {
            while (!stack.isEmpty()) {
                int tmp = stack.peek();
                stackTmp.push(tmp);
                stack.pop();
            }
        }
        else {
            stackTmp.pop();
        }
    }

    //Get the front element
    public int peek() {
        if (!stackTmp.isEmpty()) {
            int tmp = stack.peek();
            stackTmp.push(tmp);
        }
        return stackTmp.peek();
    }

    //Return whether the queueis empty
    public boolean empty() {
        if (stackTmp.isEmpty() && stack.isEmpty()) {
            return true;
        }else {
            return false;
        }
    }

    public static void main(String[] args) {
        MyQueue queue = new MyQueue();
        queue.push(8);
        System.out.println(queue.empty());     //false
    }
}

树，也是一种数据结构，非线性的，这种结构内的元素存在一对多的关系。

树，尤其是二叉树应用很广泛，排序二叉树，平衡二叉树，红黑树。

二叉树，在普通的树的基础上，让一颗树中每个节点最多只能包含两个子节点，且严格区分左子节点和右子节点(位置不能变化)
-遍历二叉树，考虑深读，优先遍历。(先序遍历、中序遍历、后续遍历)和广度优先遍历。

哈夫曼树，一种带权路径最短的二叉树，在信息检索中非常有用

哈夫曼编码，假设需要对一个字符串如“abcabcabc”进行编码，将它转化为唯一的二进制码，同时要求转换出来的二进制码的长度最小。可以采用哈夫曼树来解决报文编码问题

排序二叉树：一种特殊的二叉树，可以非常方便的对树中的所有节点进行排序和检索。

二叉树，这里采用递归和内部类的思想。

public class BinaryTree {
    private Node root;

    //添加节点
    public void add(int data) {
        if (root ==null) {
            root = new Node(data);
        }else {
            root.addNode(data);
        }
    }
    //打印节点
    public void print() {
        root.printNode();
    }

    private class Node {
        private int data;
        private Node left;
        private Node right;

        public Node(int data) {
            this.data = data;
        }

        public void addNode(int data) {
            //核心思想就是进来先个当前节点比，如果如果小于则在左边添加，如果左边没子节点，则创建，如果有添加
            if (this.data > data) {
                if (this.left == null) {
                    this.left = new Node(data);
                }else {
                    this.addNode(data);    //这里应该是采用递归。
                }
            }else {
                if (this.right == null) {
                    this.right = new Node(data);
                }else {
                    this.right.addNode(data);
                }
            }
        }

        //中序遍历
        public void printNode() {
            if (this.left != null) {
                this.left.printNode();
            }
            System.out.println(this.data + "->");
            if (this.right !=null) {
                this.right.printNode();
            }
        }
    }
}
------------------------测试-----------------------------------------------
public static void main(String[] args) {

  BinaryTree bt = new BinaryTree();
  // 8、3、10、1、6、14、4、7、13
  bt.add(8);bt.add(3);bt.add(10);
  bt.add(1);bt.add(6);bt.add(14);
  bt.add(4);bt.add(7);bt.add(13);
  bt.print();
}
输出：
1->3->4->6->7->8->10->13->14->

ArrayList因为乱码，写了一半，无奈啊，完全坑我，其思想就是根据索引，涉及到扩容，判断越界了么，。这里先不管了。直接看LinkedList。

public class MyLinkedList {
    protected Node first;    // 链表的第一个节点
    protected Node last;    // 链表的最后一个节点
    private int size;    // 节点的数量

    // 链表中的每一个节点
    public class Node {
        public Node(Object ele) {
            this.ele = ele;
        }

        Node prev;                // 上一个节点对象
        Node next;                // 下一个节点对象
        public Object ele; // 当前节点中存储的数据
    }

    public void addFirst(Object ele) {
        Node node = new Node(ele);      //需要保存的节点对象
        //进来一个节点，如果为空的话，它可定时第一个，也是最后一个
        if (size == 0) {
            this.first = node;
            this.last = node;
        }else {
            node.next = this.first;                // 把之前第一个作为新增节点的下一个节点，(进来一个，当前的只能当老二了。)
            this.first.prev = node;                // 把新增节点作为之前第一个节点的上一个节点
            this.first = node;                    // 把新增的节点作为第一个节点
        }
        size++;
  }
     //这里很重要，别忘记
    public void addLast(Object ele) {
        Node node = new Node(ele);
        if (size == 0) {
            this.first = node;
            this.last = node;
        }else {
            this.last.next = node;            // 新增节点作为之前最后一个节点的下一个节点(因为是加在后面，所以当前节点的下一个才是 新增节点)
            node.prev = this.last;            // 之前最后一个节点作为新增节点的上一个节点
            this.last = node;                // 把新增的节点作为最后一个节点
        }
    }
    //原谅我复制了
    public void remove(Object ele) {
        // 找到被删除的节点
        Node current = this.first;// 确定为第一个节点,从头到尾开始找
        for (int i = 0; i < size; i++) {
            if (!current.ele.equals(ele)) {// 当前为true !true 为false ,说明找到当前ele,输出
                if (current.next == null) { // 续上: 如果false取反为true, 判断是否最后一个,
                    return;
                }
                current = current.next;
            }
        }
        //删除节点
        if(current==first){
            this.first = current.next; //当前的下一个作为第一个
            this.first.prev = null; //当前下一个对上一个的引用设置为null

        }else if(current==last){
            this.last = current.prev;
            this.last.next = null;
        }else{
            //把删除当前节点的下一个节点作为删除节点的上一个节点的next
            current.prev.next =current.next;
            //把删除节点的上一个节点作为删除节点下一个节点的prev
            current.next.prev = current.prev;

        }
        size--;
        //System.out.println("current =" + current.ele);
    }

    public String toString() {
        if (size == 0) {
            return "[]";
        }
        StringBuilder sb = new StringBuilder(size * 2 + 1);
        Node current = this.first;// 第一个节点
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(current.ele);
            if (i != size - 1) {
                sb.append(",");
            } else {
                sb.append("]");
            }
            current = current.next; // 获取自己的下一个节点
        }
        return sb.toString();
    }
}

这个双向列表有点难理解，还是看图吧，

线性链表：

双向链表：

先到这里吧，gogogo，机会是留给有准备的人，