前言：

數(shù)據(jù)結(jié)構(gòu)是計算機相關(guān)專業(yè)的基礎(chǔ)課程版扩，不管學什么編程語言，都要學習數(shù)據(jù)結(jié)構(gòu)侄泽。接下來就一起來了解一下吧礁芦。

歡迎大家關(guān)注我的公眾號 javawebkf，目前正在慢慢地將簡書文章搬到公眾號悼尾，以后簡書和公眾號文章將同步更新柿扣，且簡書上的付費文章在公眾號上將免費。

一闺魏、概述

數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)如何在計算機中進行高效的組織和存儲的一門學科未状。數(shù)據(jù)結(jié)構(gòu)有邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)之分，邏輯結(jié)構(gòu)描述的是數(shù)據(jù)與數(shù)據(jù)之間的關(guān)系析桥，主要分為以下幾種：

• 線性結(jié)構(gòu)：數(shù)據(jù)與數(shù)據(jù)之間是一對一的關(guān)系司草。主要有數(shù)組艰垂、棧、隊列埋虹、鏈表猜憎、哈希表等。
• 樹形結(jié)構(gòu)：數(shù)據(jù)與數(shù)據(jù)之間是一對多的關(guān)系搔课。主要有二叉樹胰柑、二分搜索樹、AVL爬泥、紅黑樹柬讨、堆、線段樹急灭、Treap姐浮、Trie、哈夫曼樹等葬馋。
• 圖形結(jié)構(gòu)：數(shù)據(jù)與數(shù)據(jù)之間是多對多的關(guān)系卖鲤。主要有鄰接矩陣和鄰接表。

存儲結(jié)構(gòu)就是數(shù)據(jù)在計算機中是怎樣進行存儲的畴嘶，主要分為：

• 順序存儲：用一組連續(xù)的空間來進行存儲蛋逾，底層用數(shù)組實現(xiàn)。
• 鏈式存儲：存儲空間可以是不連續(xù)的窗悯，底層用鏈表實現(xiàn)区匣。

二、數(shù)組

1. 什么是數(shù)組蒋院？
關(guān)于數(shù)組的概念就不多說了亏钩，大家應(yīng)該都知道。數(shù)組因為有索引欺旧，所以數(shù)組的優(yōu)點就是查詢快姑丑。這里強調(diào)兩點，一是數(shù)組只能存儲同一類型的數(shù)據(jù)辞友，可以是基本類型也可以是引用類型栅哀，二是數(shù)組長度是不可變的。

2. 封裝數(shù)組：
java給我們提供的數(shù)組可以進行的操作有限称龙，我們可以將數(shù)組再次封裝一下留拾，讓其可以進行增刪改查等操作。

public class Array<E>{
    private E[] data;//存儲數(shù)據(jù)的數(shù)組
    private int size;//數(shù)組中元素的個數(shù)
    /** 構(gòu)造函數(shù)鲫尊，capacity表示數(shù)組的容量痴柔，即length */
    public Array(int capacity){
        data = (E[]) new Object[capacity];
        size = 0;
    }
    /** 默認構(gòu)造函數(shù) */
    public Array(){
        this(10);
    }
    /** 獲取數(shù)組中元素的個數(shù) */
    public int getSize(){
        return size;
    }
    /** 獲取數(shù)組的容量，即length */
    public int getCapacity(){
        return data.length;
    }
    /** 判斷數(shù)組是否為空 */
    public boolean isEmpty(){
        return size == 0;
    }
    /** 往數(shù)組末尾添加元素 */
    public void addLast(E e){
        add(size,e);
    }
    /** 往數(shù)組第一個位置添加元素 */
    public void addFirst(E e){
        add(0,e);
    }
    /** 往數(shù)組index索引處添加元素 */
    public void add(int index,E e){
        if (size == data.length)
            throw new IllegalArgumentException("數(shù)組已滿");
        if (index < 0 || index > size)
            throw new IllegalArgumentException("插入位置不合法");
        for (int i = size - 1;i >= index; i --){
            data[i+1] = data[i];//目標位置之后(包括目標位置)的元素后移
        }
        data[index] = e;
        size ++;
    }
    /** 獲取index索引處的元素 */
    public E get(int index){
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("查詢位置不合法");
        return data[index];
    }
    /** 獲取最后一個元素 */
    public E getLast(){
        return get(size - 1);
    }
    /** 獲取第一個元素 */
    public E getFirst(){
        return get(0);
    }
    /** 修改index索引處的元素 */
    public void update(int index,E e){
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("查詢位置不合法");
        data[index] = e;
    }
    /** 查找數(shù)組中是否包含元素e */
    public boolean contains(E e){
        for (int i = 0; i < size; i++){
            if (data[i] .equals(e)) return true;
        }
        return false;
    }
    /** 查找元素e所在的索引 */
    public int find(E e){
        for (int i = 0; i < size; i++){
            if (data[i].equals(e)) return i;
        }
        return -1;
    }
    /** 刪除index索引處的元素 */
    public E remove(int index){
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("位置不合法");
        E temp = data[index];
        for (int i = index + 1;i< size; i++){
            data[i-1] = data[i];//目標位置之后的元素前移
        }
        size --;
        data[size] = null;//這句話可有可無
        return temp;
    }
    /** 刪除數(shù)組中的第一個元素 */
    public E removeFirst(){
        return remove(0);
    }
    /** 刪除數(shù)組中的最后一個元素 */
    public E removeLast(){
        return remove(size-1);
    }
    /** 刪除指定元素e */
    public void removeElement(E e){
        int index = find(e);
        if (index != -1){
            remove(index);
        }
    }
    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append(String.format("size = %d,capacity = %d\n",size,data.length));
        res.append("[");
        for (int i = 0;i < size; i++){
            res.append(data[i]);
            if (i != size -1){
                res.append(", ");
            }
        }
        res.append("]");
        return res.toString();
    }
}

上面就將靜態(tài)數(shù)組再次封裝了一下疫向，可以對數(shù)組元素進行增刪改查等操作咳蔚。但是呢這還是靜態(tài)數(shù)組扛施，也就是說，我們new Array的時候傳入的capacity是多少屹篓，那么這個數(shù)組長度就是多少疙渣，不能再改變了。接下來看看動態(tài)數(shù)組如何實現(xiàn)堆巧。

3. 動態(tài)數(shù)組：
要動態(tài)的改變數(shù)組的長度妄荔，其實是不能直接實現(xiàn)的。但是我們可以創(chuàng)建一個新數(shù)組谍肤，將舊數(shù)組的的元素全都放入新數(shù)組啦租，然后讓舊數(shù)組的引用指向新數(shù)組即可』拇В看代碼實現(xiàn)：

/** 給數(shù)組擴容 */
private void resize(int newCapacity) {
     E[] newData = (E[]) new Object[newCapacity];//新數(shù)組
     for (int i = 0; i< size;i++){
         newData[i] = data[i];//舊數(shù)組的值存入新數(shù)組對應(yīng)的位置
     }
     data = newData;//指向新數(shù)組
}

有了這個方法篷角，就可以對剛才上面的add和remove方法做一些修改。

/** 往數(shù)組index索引處添加元素 */
public void add(int index,E e){
    if (index < 0 || index > size)
        throw new IllegalArgumentException("插入位置不合法");
    if (size == data.length)//數(shù)組已滿
        resize(2 * data.length);//擴容兩倍,如果以前為10系任，現(xiàn)在就是20
    for (int i = size - 1;i >= index; i --){
        data[i+1] = data[i];
    }
    data[index] = e;
    size ++;
}

/** 刪除index索引處的元素 */
public E remove(int index){
    if (index < 0 || index >= size)
        throw new IllegalArgumentException("位置不合法");
    E temp = data[index];
    for (int i = index + 1;i< size; i++){
        data[i-1] = data[i];
    }
    size --;
    if (size == data.length/4 && data.length / 2 != 0){//如果刪除元素后數(shù)組只使用了1/4的容量
        resize(data.length/2);//那就縮小到以前容量的一半
    }
    return temp;
}

小結(jié)：數(shù)組是線性結(jié)構(gòu)的恳蹲，一經(jīng)定義長度就不可變。刪除數(shù)組中元素的思路就是將目標元素之后的元素都前移一位俩滥；添加元素的思路就是將目標位置開始的元素都后移一位嘉蕾，再把目標元素添加到目標位置；給數(shù)組動態(tài)地擴容的思路就是創(chuàng)建一個容量更大的新數(shù)組霜旧，把舊數(shù)組的元素放到新數(shù)組對應(yīng)的位置错忱，最后把舊數(shù)組的引用指向新數(shù)組。

三挂据、鏈表

1. 什么是鏈表以清？
鏈表也是一種線性結(jié)構(gòu)。上面說的動態(tài)數(shù)組崎逃、棧和隊列掷倔，底層都是用靜態(tài)數(shù)組實現(xiàn)的，而鏈表是一種簡單的真正的動態(tài)數(shù)據(jù)結(jié)構(gòu)婚脱。它也可以輔助實現(xiàn)其他的數(shù)據(jù)結(jié)構(gòu)今魔，也就說勺像，像棧和隊列障贸，也可以鏈表來實現(xiàn)。鏈表是用節(jié)點來存儲數(shù)據(jù)的吟宦，節(jié)點中有數(shù)據(jù)域和指針域篮洁，數(shù)據(jù)域存放數(shù)據(jù)，指針域連接下一個節(jié)點殃姓。這就像火車一樣袁波，火車車廂用來搭載乘客瓦阐，同時每一節(jié)車廂又連接著下一節(jié)車廂。靜態(tài)數(shù)組定義時就需要聲明長度篷牌，使用的是計算機中連續(xù)的內(nèi)存空間睡蟋，可以通過索引訪問元素，因此查詢元素是非臣霞眨快的戳杀。而鏈表所使用的空間是不連續(xù)的，長度也是不固定的夭苗，無法通過索引訪問元素信卡，所以查詢慢，而增刪很快题造，因為增刪時只需要改變一個節(jié)點的指針域即可傍菇。

2. 鏈表的實現(xiàn)：
上面說到了鏈表是用節(jié)點來存放數(shù)據(jù)的，同時節(jié)點又連接著下一個節(jié)點界赔。所以先要有一個節(jié)點類Node丢习，Node應(yīng)該要有兩個屬性，一個是用來存放數(shù)據(jù)的淮悼，應(yīng)該定義為泛型泛领，另一個屬性就是Node類型的next，表示的是下一個節(jié)點敛惊。鏈表類就應(yīng)該int類型的size屬性渊鞋，用來記錄鏈表中元素的個數(shù)，Node類型head屬性瞧挤，表示鏈表的頭節(jié)點∥危現(xiàn)在來分析一下鏈表是如何添加和刪除元素的。

• 添加元素：
  有如下鏈表：

  
  
  鏈表
  
  

  現(xiàn)要在鏈表最前面添加一個節(jié)點node特恬，那么應(yīng)該執(zhí)行的操作就是：

node.next = head;
head = node;

添加完成后就成了這樣：

在鏈表頭添加元素

如果是要在鏈表中間的某個位置添加元素执俩，比如在元素 “1” 的后面添加節(jié)點 “666” ,那么首先我們要找到要插入位置之前的那個節(jié)點prev，這里prev就是 “1” 這個節(jié)點癌刽。接下來執(zhí)行的操作就是：

node.next = prev.next;
prev.next = node;

在鏈表指定位置添加元素

在指定位置添加元素我們需要找到目標位置的前一個節(jié)點役首，但是如果目標位置是第一個位置的時候，就沒有前一個節(jié)點了显拜。其實我們可以搞一個虛擬頭節(jié)點衡奥。如下圖。

虛擬頭節(jié)點

• 刪除元素：
  刪除節(jié)點同樣也要先找到需要刪除的元素的前一個節(jié)點prev远荠，需要刪除的節(jié)點假設(shè)叫做delNode矮固。那么刪除delNode要執(zhí)行的操作就是：

prev.next = delNode.next;
delNode.next = null;

刪除元素

有了上面的分析，就用代碼來實現(xiàn)鏈表這種數(shù)據(jù)結(jié)構(gòu)譬淳。

• 代碼實現(xiàn)：

public class MyLinkedList<E> {
    /** 節(jié)點設(shè)計成內(nèi)部類 */
    private class Node {
        public E e;//存放的元素
        public Node next;//下一個節(jié)點
        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }
        public Node(E e) {
            this(e, null);
        }
        public Node() {
            this(null, null);
        }
        @Override
        public String toString() {
            return e.toString();
        }
    }
    private Node dummyhead;//虛擬頭節(jié)點
    private int size;//存儲的元素個數(shù)
    public MyLinkedList() {
        dummyhead = new Node(null, null);
        size = 0;
    }
    /** 獲取鏈表中元素個數(shù) */
    public int getSize() {
        return size;
    }
    /** 判斷鏈表是否為空 */
    public boolean isEmpty() {
        return size == 0;
    }
    /** 在鏈表指定位置添加元素档址，(index是從0開始的) */
    public void add(int index, E e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("位置不合法");
        }
        Node prev = dummyhead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;//找到目標位置的前一個節(jié)點
        }
            /*Node node = new Node(e);
            node.next = prev.next;
            prev.next = node;*/
        prev.next = new Node(e, prev.next);//與上面3行代碼等效
        size++;
    }
    /** 在鏈表末尾添加元素 */
    public void addLast(E e) {
        add(size, e);
    }
    /** 往鏈表頭添加元素 */
    public void addFirst(E e) {
        add(0,e);
    }
    /** 獲取鏈表指定位置的元素(index從0開始) */
    public E get(int index){
        if (index<0 || index>=size){
            throw new IllegalArgumentException("位置不合法");
        }
        Node cur = dummyhead.next;
        for (int i=0;i<index;i++){
            cur = cur.next;
        }
        return cur.e;
    }
    /** 獲取第一個元素 */
    public E getFirst(){
        return get(0);
    }
    /** 獲取鏈表最后一個元素 */
    public E getLast(){
        return get(size -1);
    }
    /** 更新指定位置的元素 */
    public void set(int index,E e){
        if (index<0 || index>=size){
            throw new IllegalArgumentException("位置不合法");
        }
        Node cur = dummyhead.next;
        for (int i=0;i<index;i++){
            cur = cur.next;
        }
        cur.e = e;
    }
    /** 查找鏈表中是否存在元素e */
    public boolean contains(E e){
        Node cur = dummyhead.next;
        while (cur != null){
            if (cur.e.equals(e))
                return true;
            cur = cur.next;
        }
        return false;
    }
    /** 刪除指定位置的元素 */
    public E remove(int index){
        if (index<0 || index>=size){
            throw new IllegalArgumentException("位置不合法");
        }
        Node prev = dummyhead;
        for (int i = 0;i<index;i++){
            prev = prev.next;//找到目標節(jié)點的前一個節(jié)點
        }
        Node delNode = prev.next;
        prev.next = delNode.next;
        delNode.next = null;
        size --;
        return delNode.e;
    }
    /** 刪除鏈表中第一個元素 */
    public E removeFirst(){
        return remove(0);
    }
    /** 刪除鏈表中最后一個元素 */
    public E removeLast(){
        return remove(size -1);
    }
    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        Node cur = dummyhead.next;
        while (cur != null){
            res.append(cur + "-->");
            cur = cur.next;
        }
        res.append("NULL");
        return res.toString();
    }
}

小結(jié)：鏈表也是線性結(jié)構(gòu)的盹兢，是一種不同于數(shù)組的動態(tài)數(shù)據(jù)結(jié)構(gòu)，鏈表的英文翻譯的linkedList守伸，注意和java提供的LinkedList集合區(qū)分開绎秒，LinkedList集合底層正是用鏈表實現(xiàn)的。

四尼摹、棧

1. 什么是棧替裆？
棧就類似于水桶，只有水桶口一個開口窘问，用水桶裝水的時候辆童，最先裝到的水在桶底，而用水桶中的水的時候惠赫，最先用的是最后裝的在最上面的水把鉴。棧也是這樣，只允許在棧頂操作儿咱，元素有后進先出(last in first out庭砍，簡稱LIFO)的特點，添加元素叫入棧混埠，刪除元素叫出棧怠缸。

2. 棧的應(yīng)用：

• 撤銷功能：我們都知道像word記事本等編輯器的撤銷功能，其實就是使用棧來實現(xiàn)的钳宪。你的操作都會記錄在棧中揭北，當你撤銷的時候，你最后的操作就會出棧吏颖，就恢復到之前的狀態(tài)搔体。
• 程序調(diào)用的系統(tǒng)棧：比如有三個方法A、B半醉、C疚俱，A方法執(zhí)行到第三行調(diào)用了B，B執(zhí)行到第四行調(diào)用了C缩多，那么當C執(zhí)行完后呆奕，從哪里開始執(zhí)行呢？其實當執(zhí)行A方法轉(zhuǎn)而去執(zhí)行B方法的時候衬吆，系統(tǒng)棧就會記錄這個位置梁钾，比如這個位置叫A3，執(zhí)行B方法轉(zhuǎn)而去執(zhí)行C方法的時候咆槽，也會記錄這個位置陈轿，比如叫B4圈纺，那么現(xiàn)在系統(tǒng)棧中自頂向下為B4秦忿、A3麦射。當執(zhí)行完C后，發(fā)現(xiàn)系統(tǒng)棧中棧頂元素為B4灯谣，那么計算機就知道接下來就從B方法的第四行開始執(zhí)行了潜秋。
• 括號匹配問題：一般的編輯器都會檢查你輸入的括號是否有效，'(' 以 ')'閉合時為有效胎许，'(' 以 '}' 閉合是為無效峻呛。這就是用棧來實現(xiàn)檢查這個功能的。

3. 棧的實現(xiàn)：
椆家ぃ可以基于數(shù)組實現(xiàn)钩述，也可以使用鏈表實現(xiàn)。先看看基于數(shù)組如何實現(xiàn)穆碎。

• 首先創(chuàng)建一個Stack接口牙勘，提供對棧的一些操作的方法。

public interface Stack<E> {
    /** 獲取棧中元素個數(shù) */
    int getSize();
    /** 棧是否為空 */
    boolean isEmpty();
    /** 添加元素 */
    void push(E e);
    /** 刪除元素 */
    E pop();
    /** 獲取棧頂元素 */
    E peek();
}

• 基于數(shù)組(自己封裝的數(shù)組)實現(xiàn)棧所禀。

public class ArrayStack<E> implements Stack<E> {
    Array<E> array;//自己封裝的動態(tài)數(shù)組
    /** 構(gòu)造方法方面，初始化棧 */
    public ArrayStack(int capacity){
        array = new Array<>(capacity);
    }
    public ArrayStack(){
        array = new Array<>();
    }
    @Override
    public int getSize() {
        return array.getSize();
    }
    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }
    @Override
    public void push(E e) {
        array.addLast(e);//因為只能在棧頂添加，所以是addLast
    }
    @Override
    public E pop() {
        return array.removeLast();//因為只能在棧頂刪除色徘，所以是removeLast
    }
    @Override
    public E peek() {
        return array.getLast();//數(shù)組的最后一個就是棧頂元素
    }
    public int getCapacity(){
        return array.getCapacity();
    }
    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Stack:");
        res.append("[");
        for (int i = 0;i<array.getSize();i++){
            res.append(array.get(i));
            if (i != array.getSize() - 1){
                res.append(", ");
            }
        }
        res.append("] top");
        return res.toString();
    }
}

• 基于鏈表(自己實現(xiàn)的鏈表)實現(xiàn)棧：

public class LinkedListStack<E> implements Stack<E> {
    private MyLinkedList<E> list;//自己實現(xiàn)的鏈表
    public LinkedListStack(){
        list = new MyLinkedList<>();
    }
    @Override
    public int getSize() {
        return list.getSize();
    }
    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }
    @Override
    public void push(E e) {
        list.addFirst(e);
    }
    @Override
    public E pop() {
        return list.removeFirst();
    }
    @Override
    public E peek() {
        return list.getFirst();
    }
    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Stack: top");
        res.append(list);
        return res.toString();
    }
}

上面分別基于數(shù)組和鏈表實現(xiàn)了棧的一些基本操作恭金。為了操作的方便，基于數(shù)組的時候褂策，數(shù)組末尾是棧頂横腿，基于鏈表的時候，鏈表頭是棧頂斤寂。java.util包中也有一個Stack類蔑水，就是java提供的實現(xiàn)好了的棧，它提供的方法也和上面的差不多扬蕊。

• 棧的應(yīng)用例子(括號匹配問題)：
  問題描述：給定一個只包括 '('搀别，')'，'{'尾抑，'}'歇父，'['，']' 的字符串再愈，判斷字符串是否有效榜苫。
  有效字符串需滿足：左括號必須用相同類型的右括號閉合。左括號必須以正確的順序閉合翎冲。

public boolean isValid(String s){
        Stack<Character> stack = new Stack<>();
        for (int i=0;i<s.length();i++){
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{'){
                stack.push(c);//把左括號壓入棧中
            }else {
                if (stack.isEmpty()){
                    return false;
                }
                char topChar = stack.pop();
                if (c == ')' && topChar != '('){
                    return false;
                }
                if (c == ']' && topChar != '['){
                    return false;
                }
                if (c == '}' && topChar != '{'){
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

小結(jié)：棧也是線性結(jié)構(gòu)的垂睬，只允許在棧頂操作，添加元素叫入棧，刪除元素叫出棧驹饺，元素有先進后出的特點钳枕。

五、隊列

1. 什么是隊列赏壹？
隊列也是一種線性結(jié)構(gòu)鱼炒，它只能從隊尾添加元素，從隊首取出元素蝌借，是一種先進先出(first in first out昔瞧，簡稱FIFO)的數(shù)據(jù)結(jié)構(gòu)。就跟生活當中的排隊是一樣的菩佑，要排隊只能從隊尾加入自晰，從隊首離開。

2. 隊列的實現(xiàn)：

• 首先創(chuàng)建一個Queue接口稍坯，提供操作隊列的一些方法缀磕。

public interface Queue<E> {
    /** 獲取隊列中元素的個數(shù) */
    int getSize();
    /** 判斷隊列是否為空 */
    boolean isEmpty();
    /** 入隊 */
    void enqueue(E e);
    /** 出隊 */
    E dequeue();
    /** 獲取隊首元素 */
    E getFront();
}

• 基于數(shù)組(自己實現(xiàn)的動態(tài)數(shù)組)實現(xiàn)隊列：

public class ArrayQueue<E> implements Queue<E> {
    private Array<E> array;
    public ArrayQueue(int capacity){
        array = new Array<>(capacity);
    }
    public ArrayQueue(){
        array = new Array<>();
    }
    @Override
    public int getSize() {
        return array.getSize();
    }
    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }
    public int getCapacity(){
        return array.getCapacity();
    }
    @Override
    public void enqueue(E e) {
        array.addLast(e);
    }
    @Override
    public E dequeue() {
        return array.removeFirst();
    }
    @Override
    public E getFront() {
        return array.getFirst();
    }
    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Queue:");
        res.append("front [");
        for (int i = 0;i<array.getSize();i++){
            res.append(array.get(i));
            if (i != array.getSize() - 1){
                res.append(", ");
            }
        }
        res.append("] tail");
        return res.toString();
    }
}

• 基于鏈表(自己實現(xiàn)鏈表)實現(xiàn)隊列：

public class LinkedListQueue<E> implements Queue<E> {
    private class Node {
        public E e;//存放的元素
        public Node next;//下一個節(jié)點
        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }
        public Node(E e) {
            this(e, null);
        }
        public Node() {
            this(null, null);
        }
        @Override
        public String toString() {
            return e.toString();
        }
    }
    private Node head,tail;//頭節(jié)點和尾節(jié)點
    private int size;//元素個數(shù)
    public LinkedListQueue(){
        head = null;
        tail = null;
        size = 0;
    }
    @Override
    public int getSize() {
        return size;
    }

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

    /** 入隊，在鏈表的尾部進行操作 */
    @Override
    public void enqueue(E e) {
        if (tail == null){
            tail = new Node(e);
            head = tail;
        }else {
            tail.next = new Node(e);
            tail = tail.next;
        }
        size ++;
    }
    /** 出隊劣光，在鏈表頭操縱 */
    @Override
    public E dequeue() {
        if (isEmpty()){
            throw new IllegalArgumentException("隊列為空");
        }
        Node delNode = head;
        head = head.next;
        delNode.next = null;
        if (head == null){
            tail = null;
        }
        size --;
        return delNode.e;
    }
    @Override
    public E getFront() {
        if (isEmpty()){
            throw new IllegalArgumentException("隊列為空");
        }
        return head.e;
    }
    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("queue:front ");
        Node cur = head;
        while (cur != null){
            res.append(cur + "--> ");
            cur = cur.next;
        }
        res.append("NULL  tail");
        return res.toString();
    }
}

基于鏈表的隊列并沒有直接使用上面第三部分實現(xiàn)的鏈表袜蚕，而是重新寫了一下，把虛擬頭節(jié)點去掉了绢涡，同時多維護了一個尾節(jié)點tail牲剃。這樣一來，入隊操作在鏈表尾部進行雄可，出隊操作在鏈表頭部進行凿傅，時間復雜度都是O(1)，如果不維護一個尾節(jié)點数苫，那么入隊和出隊總有一個時間復雜度是O(n)聪舒。基于數(shù)組的隊列出隊這個操作虐急，出隊是刪除隊首元素箱残，對應(yīng)的底層數(shù)組的操作就是刪除數(shù)組中第一個元素，刪除第一個元素的話止吁，那么其他元素都得往前移一位被辑，所以這個時間復雜度是O(n)的。因此就出現(xiàn)了循環(huán)隊列敬惦。

3. 循環(huán)隊列：

• 循環(huán)隊列分析：

上面說到了盼理，出隊的時候會導致底層數(shù)組第二個元素開始都前移一位，這樣性能不是很好俄删。循環(huán)隊列就是用front來記錄隊首的位置宏怔，tail指向隊尾元素的后一個位置奏路。一開始數(shù)組為空時，front和tail同時指向底層數(shù)組的0索引處臊诊，即

front == tail //隊列為空

當有元素入隊時鸽粉，tail++即可，當0索引處的元素出隊后妨猩，front++即可潜叛，后面的元素不用前移秽褒，這樣就性能就提升了壶硅。

image.png

在上圖刪除元素的基礎(chǔ)上繼續(xù)添加元素，當索引為4處也存放有元素了销斟，此時tail指向索引5庐椒，那么tail++就超出索引范圍了，若要往索引5處添加元素蚂踊，此時tail應(yīng)該指向0才對约谈，這才是循環(huán)隊列。

循環(huán)隊列

tail = (當前索引 + 1) % 數(shù)組長度

在上圖，tail指向的0索引處是沒有元素的涝动，如果此時再往0索引處添加元素迈勋，那么tail就等于1，又和front相等了醋粟。上面說了靡菇，front 等于 tail的時候是隊列為空，現(xiàn)在隊列滿又是這種情況米愿，所以不行厦凤。因此規(guī)定：

tail + 1 == front //隊列已滿

所以循環(huán)隊列是浪費了數(shù)組的一個空間的。

• 編碼實現(xiàn)循環(huán)隊列：
  同樣實現(xiàn)Queue接口育苟。

public class LoopQueue<E> implements Queue<E> {
    private E[] data;//存放元素的數(shù)組
    private int front,tail;//隊首和隊尾
    private int size;//隊列中元素個數(shù)
    public LoopQueue(int capacity){
        data = (E[]) new Object[capacity+1];
        front = 0;
        tail = 0;
        size = 0;
    }
    public LoopQueue(){
        this(10);
    }
    /** 獲取隊列容積(數(shù)組長度 - 1 ) */
    public int getCapacity(){
        return data.length - 1;
    }
    @Override
    public int getSize() {
        return size;
    }
    @Override
    public boolean isEmpty() {
        return front == tail;
    }
    @Override
    public void enqueue(E e) {
        if ((tail + 1)% data.length == front){//隊列已滿
            resize(getCapacity() * 2);//給數(shù)組擴容
        }
        data[tail] = e;
        tail = (tail + 1) % data.length;
        size ++;
    }
    /** 給數(shù)組擴容 */
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity + 1];
        for (int i=0;i<size;i++){
            newData[i] = data[(i + front) % data.length];
        }
        data = newData;
        front = 0;
        tail = size;
    }
    @Override
    public E dequeue() {
        if (isEmpty()){
            throw new IllegalArgumentException("空隊列不能執(zhí)行出隊操作");
        }
        E e = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size --;
        if (size == getCapacity() / 4 && getCapacity() /2 != 0){
            resize(getCapacity() / 2);//縮容
        }
        return e;
    }
    @Override
    public E getFront() {
        if (isEmpty()){
            throw new IllegalArgumentException("隊列為空");
        }
        return data[front];
    }
    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append(String.format("loopQueue: size = %d,capacity = %d\n",size,getCapacity()));
        res.append("front:[");
        for (int i = front;i != tail ; i=(i+1)%data.length){
            res.append(data[i]);
            if ((i+1) % data.length != tail){
                res.append(", ");
            }
        }
        res.append("] tail");
        return res.toString();
    }
}

小結(jié)：隊列也是線性結(jié)構(gòu)的较鼓，跟生活中的排隊是一樣的，在隊首刪除元素违柏，隊尾添加元素笨腥，有先進先出的特點。

六勇垛、遞歸

本文本來是講數(shù)據(jù)結(jié)構(gòu)脖母，但這里先說說遞歸，因為接下來的幾種數(shù)據(jù)結(jié)構(gòu)都有用到遞歸算法闲孤。
1. 什么是遞歸谆级？
遞歸烤礁，就是方法里面調(diào)用方法自身。我們直到方法里面也可以調(diào)用其他的方法肥照，調(diào)用其他方法也很容易理解脚仔，其實方法里面也可以調(diào)用方法本身，如下：

public void fun(){
   fun();
}

但是上面這段代碼運行一段時間后會報錯舆绎，因為這個遞歸沒有結(jié)束條件鲤脏，會形成死循環(huán)，一直往棧中壓入fun方法吕朵，最后導致棧內(nèi)存溢出猎醇。所以遞歸一定要有結(jié)束條件。還要注意努溃，如果遞歸太深了硫嘶，即使有結(jié)束條件，也可能會出現(xiàn)棧內(nèi)存溢出錯誤梧税。

2. 遞歸的使用：
需求：求1到n的和沦疾。

• 分析：

/** 使用遞歸求1到n的和 */
public int sum(int n){
 
}

假設(shè)現(xiàn)在傳入的n等于4，那么就是求1到4的和第队。1到4的和就可以寫出如下形式：

4 + 3 + 2 + 1 //sum(4) 求1到4的和

4后面的 3 + 2 + 1 又可以看成是求1到3的和哮塞，因此可以寫成：

4 + sum(3)

sum(3) 其實又可以寫成 3 + sum(2) ，因此整體又變成：

4 + 3 + sum(2)

sum(2) 又可以寫成 2 + sum(1)凳谦，因此又變成：

4 + 3 + 2 + sum(1)

寫到這里忆畅，我們發(fā)現(xiàn)了規(guī)律，其實求1到n的和晾蜘，就可以寫成 n + sum(n-1) 邻眷。那么結(jié)束條件是什么呢？通過上面的分析可知剔交，因為 sum(1) 就是等于1肆饶，所以結(jié)束條件就是當 n等于1 的時候，直接返回一個 1 就行了岖常。

• 遞歸實現(xiàn)1到n的求和：

 /** 使用遞歸求1到n的和 */
 public int sum(int n){
     if (n == 1){
         return 1;
     }
     return n + sum(n-1);
 }

上面分析了一下如何使用遞歸求1到n的和驯镊，并且給出了實現(xiàn)。下面就來看一下這段求和代碼具體的執(zhí)行過程：

遞歸求和的執(zhí)行過程

總結(jié)：

為避免篇幅過長，本文就先聊到這抽兆。本文主要說了一下數(shù)組识补、鏈表、棧和隊列這四種線性結(jié)構(gòu)辫红。數(shù)組和鏈表是最基本的數(shù)據(jù)結(jié)構(gòu)凭涂，可以輔助實現(xiàn)其他數(shù)據(jù)結(jié)構(gòu)，像棧和隊列贴妻，既可以用數(shù)組實現(xiàn)切油，也可以用鏈表實現(xiàn)。用數(shù)組實現(xiàn)的叫順序存儲名惩，用鏈表實現(xiàn)的叫鏈式存儲澎胡。最后還說了一下遞歸，為接下來的學習做準備娩鹉。