隊(duì)列(queue),也是一種特殊的線(xiàn)性表，使用固定的一端來(lái)插入數(shù)據(jù)，另一端用于刪除數(shù)據(jù)

先進(jìn)先出，就像火車(chē)站排隊(duì)買(mǎi)票一樣?。?！，整個(gè)隊(duì)伍向前面移動(dòng)。

分為順序隊(duì)列結(jié)構(gòu)和鏈?zhǔn)疥?duì)列結(jié)構(gòu)

從JDK 5 開(kāi)始，Java集合框架提供了Queue接口，實(shí)現(xiàn)該接口的類(lèi)可以當(dāng)成隊(duì)列使用，如LinkedBlockingQueue，PriorityBlockingQueue。

可以通過(guò)輪詢(xún)和等待-通知機(jī)制實(shí)現(xiàn)阻塞隊(duì)列。

具體Queue實(shí)現(xiàn)：

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());
    }
}

我們?cè)趤?lái)看看用Stack如何實(shí)現(xiàn)Queue，非常不錯(cuò)，《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
    }
}

樹(shù)，也是一種數(shù)據(jù)結(jié)構(gòu)，非線(xiàn)性的，這種結(jié)構(gòu)內(nèi)的元素存在一對(duì)多的關(guān)系。

樹(shù)，尤其是二叉樹(shù)應(yīng)用很廣泛，排序二叉樹(shù)，平衡二叉樹(shù)，紅黑樹(shù)。

二叉樹(shù)，在普通的樹(shù)的基礎(chǔ)上，讓一顆樹(shù)中每個(gè)節(jié)點(diǎn)最多只能包含兩個(gè)子節(jié)點(diǎn)，且嚴(yán)格區(qū)分左子節(jié)點(diǎn)和右子節(jié)點(diǎn)(位置不能變化)
-遍歷二叉樹(shù)，考慮深讀，優(yōu)先遍歷。(先序遍歷、中序遍歷、后續(xù)遍歷)和廣度優(yōu)先遍歷。

哈夫曼樹(shù)，一種帶權(quán)路徑最短的二叉樹(shù)，在信息檢索中非常有用

哈夫曼編碼，假設(shè)需要對(duì)一個(gè)字符串如“abcabcabc”進(jìn)行編碼，將它轉(zhuǎn)化為唯一的二進(jìn)制碼，同時(shí)要求轉(zhuǎn)換出來(lái)的二進(jìn)制碼的長(zhǎng)度最小。可以采用哈夫曼樹(shù)來(lái)解決報(bào)文編碼問(wèn)題

排序二叉樹(shù)：一種特殊的二叉樹(shù)，可以非常方便的對(duì)樹(shù)中的所有節(jié)點(diǎn)進(jìn)行排序和檢索。

二叉樹(shù)，這里采用遞歸和內(nèi)部類(lèi)的思想。

public class BinaryTree {
    private Node root;

    //添加節(jié)點(diǎn)
    public void add(int data) {
        if (root ==null) {
            root = new Node(data);
        }else {
            root.addNode(data);
        }
    }
    //打印節(jié)點(diǎn)
    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) {
            //核心思想就是進(jìn)來(lái)先個(gè)當(dāng)前節(jié)點(diǎn)比，如果如果小于則在左邊添加，如果左邊沒(méi)子節(jié)點(diǎn)，則創(chuàng)建，如果有添加
            if (this.data > data) {
                if (this.left == null) {
                    this.left = new Node(data);
                }else {
                    this.addNode(data);    //這里應(yīng)該是采用遞歸。
                }
            }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();
            }
        }
    }
}
------------------------測(cè)試-----------------------------------------------
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因?yàn)閬y碼，寫(xiě)了一半，無(wú)奈啊，完全坑我，其思想就是根據(jù)索引，涉及到擴(kuò)容，判斷越界了么，。這里先不管了。直接看LinkedList。

public class MyLinkedList {
    protected Node first;    // 鏈表的第一個(gè)節(jié)點(diǎn)
    protected Node last;    // 鏈表的最后一個(gè)節(jié)點(diǎn)
    private int size;    // 節(jié)點(diǎn)的數(shù)量

    // 鏈表中的每一個(gè)節(jié)點(diǎn)
    public class Node {
        public Node(Object ele) {
            this.ele = ele;
        }

        Node prev;                // 上一個(gè)節(jié)點(diǎn)對(duì)象
        Node next;                // 下一個(gè)節(jié)點(diǎn)對(duì)象
        public Object ele; // 當(dāng)前節(jié)點(diǎn)中存儲(chǔ)的數(shù)據(jù)
    }

    public void addFirst(Object ele) {
        Node node = new Node(ele);      //需要保存的節(jié)點(diǎn)對(duì)象
        //進(jìn)來(lái)一個(gè)節(jié)點(diǎn)，如果為空的話(huà)，它可定時(shí)第一個(gè)，也是最后一個(gè)
        if (size == 0) {
            this.first = node;
            this.last = node;
        }else {
            node.next = this.first;                // 把之前第一個(gè)作為新增節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，(進(jìn)來(lái)一個(gè)，當(dāng)前的只能當(dāng)老二了。)
            this.first.prev = node;                // 把新增節(jié)點(diǎn)作為之前第一個(gè)節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)
            this.first = node;                    // 把新增的節(jié)點(diǎn)作為第一個(gè)節(jié)點(diǎn)
        }
        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;            // 新增節(jié)點(diǎn)作為之前最后一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)(因?yàn)槭羌釉诤竺妫援?dāng)前節(jié)點(diǎn)的下一個(gè)才是 新增節(jié)點(diǎn))
            node.prev = this.last;            // 之前最后一個(gè)節(jié)點(diǎn)作為新增節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)
            this.last = node;                // 把新增的節(jié)點(diǎn)作為最后一個(gè)節(jié)點(diǎn)
        }
    }
    //原諒我復(fù)制了
    public void remove(Object ele) {
        // 找到被刪除的節(jié)點(diǎn)
        Node current = this.first;// 確定為第一個(gè)節(jié)點(diǎn),從頭到尾開(kāi)始找
        for (int i = 0; i < size; i++) {
            if (!current.ele.equals(ele)) {// 當(dāng)前為true !true 為false ,說(shuō)明找到當(dāng)前ele,輸出
                if (current.next == null) { // 續(xù)上: 如果false取反為true, 判斷是否最后一個(gè),
                    return;
                }
                current = current.next;
            }
        }
        //刪除節(jié)點(diǎn)
        if(current==first){
            this.first = current.next; //當(dāng)前的下一個(gè)作為第一個(gè)
            this.first.prev = null; //當(dāng)前下一個(gè)對(duì)上一個(gè)的引用設(shè)置為null

        }else if(current==last){
            this.last = current.prev;
            this.last.next = null;
        }else{
            //把刪除當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)作為刪除節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)的next
            current.prev.next =current.next;
            //把刪除節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)作為刪除節(jié)點(diǎn)下一個(gè)節(jié)點(diǎn)的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;// 第一個(gè)節(jié)點(diǎn)
        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; // 獲取自己的下一個(gè)節(jié)點(diǎn)
        }
        return sb.toString();
    }
}

這個(gè)雙向列表有點(diǎn)難理解，還是看圖吧，

線(xiàn)性鏈表：

雙向鏈表：

先到這里吧，gogogo，機(jī)會(huì)是留給有準(zhǔn)備的人，